约瑟夫环问题_C++

约瑟夫环问题_C++ 湖南大学 计算机与通信学院 实验一 约瑟夫环问题 背景 约瑟夫问题(Josephus Problem)据说著名犹太历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。 然而Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。 原题: 用户输入M,N值，N个人围成一个环，从0号人开始数,数到M,那个人就退出游戏，直到最后一个人 求最后一个剩下的人是几号, 基本 需要基于线性的基本操作来实现约瑟夫问题 需要利用数组来实现线性表 输入输出格式 输入格式:n，m 输出格式1:在字符界面上输出这n个数的输出序列 输出格式2:将这n个数的输出序列写入到文件中 一、 实验目的 1. 熟悉线性表的操作和应用; 2. 利用顺序表的存储结构解决约瑟夫环问题。 二、 实验原理 1. 问题描述 设编号为1-n的n(n>0)个人按顺时针方向围成一圈(首先第1个人从1开始顺时针报数(报m的人(m 为正整数)(令其出列。然后再从他的下一个人开始，重新从1顺时针报数，报m的人，再令其出列。如此下去，直到圈中所有人出列为止。求出列编号序列。 2. 实现:利用数组构成线性表，并对每个人排序。利用函数找到要踢出的人，当第L个人出圈之后，报数，并在用后面的人依次填充。 3. 程序思路: ?定义一个数组，初始化对每个人赋值排序; ?利用while()函数判断最后结束条件 ?输出踢出的人，后面人数次序加一，总人数减一。 ?输出胜出，结束。 三、 实验程序 //======================================================== #in#include using namespace std; int main() { int A[100],n,,m; cout<<"please input boynumber ， intervalnumber:\n"; cin>>n>>m; int i,j,k=n; for(i=0;i0) { for(j=1;j