C++编程：约瑟夫环问题。

用C++编写如下约瑟夫环问题~

#include
using namespace std;
int main()
{
int n,s,m;
cout<<"please input the valuse of n,m,s"<<endl;
cin>>n>>m>>s;
if(n<=0||s<=0||m<=0)
{
cout<<"error"<<endl;
}
int i,j,k,temp;//k为次数
int A[100];
for(i=0;i<n;i++)
{
A[i]=i+1;
}//建立数组
i=s-1;//设定开始报数的起始位置
for(k=n;k>1;k--)
{
i=((i+m-1)%k);//计算要报数人序号
if(i!=k-1)
{
temp=A[i];
for(j=i;j<k-1;j++)
A[j]=A[j+1];//将i位置一直到k-1位置元素向前移一位
A[k-1]=temp;//将报数的人移动至数组最后
}
}
cout<<"the jodephus order is"<<endl;
for(k=n-1;k>=0;k--)
{

cout<<A[k]<<" ";//反向输出输出数组元素即为所求数列
}

return 0;
}

假设有n个人的一个小组，按顺时针围坐一圈，一开始任选一个正整数作为报数的上限m，从第一个人开始按顺时针方向自1开始报数，报到m的人出圈，然后从他下一个开始从1重新开始报数，报到m的人出圈。如此下去，知道所有人都出圈为止。
（1） 出圈游戏一：使用动态数组来接收输入，参加的人数和报数上限可变
（2） 出圈游戏二：使用循环链表来接受输入，参加的人数和报数上限可变
（3） 参加游戏者的编号和姓名存入文件play.txt中，按出圈顺序将出圈者的编号和姓名存入文件result.txt中。
（4） 利用菜单提供用户界面，菜单格式如下：
1. 出圈游戏一
2. 出圈游戏二
3. 输出出圈游戏一结果
4. 输出出圈游戏二结果
5. 退出
选择1，2时分别进行出圈游戏，且将结果保存在文件中，选择3，4时，在屏幕上输出相应结果

# include
# include
struct stu
{
int num;
struct stu *next;
};
int m,n;struct stu *p,*q,*s;
struct stu *create()
{
struct stu *head,*s1,*r;
int i;

head=NULL;
for(i=1;i<=n;i++)
{
s1=(struct stu *)malloc(sizeof(struct stu));
s1->num =i;
if(head==NULL)head=s1;
else r->next =s1;
r=s1;
}
if(r) r->next =head;
return head;
}
struct stu * get_index(struct stu *head,int k)
{
int j=1;
if (k<1)
{
printf ("输入错误
");
return NULL;
}
s=head;
while (s && j<k)
{
s=s->next ;j++;
}
return s;
}
void f1 (struct stu *head,struct stu *h)
{
int x,i;
x=m/2;
p=h;
i=1;printf ("依次出列的人的编号为:");
while (p->next!=p)
{
q=p->next;
for (i=1;i<x;i++)
{p=q->next;q=p->next;}
p->next =q->next ;
printf ("%d ",q->num);
free(q);
p=p->next ;
}
printf ("最后剩下的人的编号为%d
",p->num );
}
void f2 (struct stu *head,struct stu *h)
{
int i,x;
x=m/2;
i=1;
p=h;
printf ("依次出列的人的编号为:");
do
{
for (i=1;i<=x;i++)
{q=p->next ;p=q->next ;}
q->next =p->next ;
printf ("%d ",p->num);
free(p);
p=q->next ;
}
while (q->next!=q);
printf ("
最后剩下的人的编号为%d
",q->num);
}
void main ()
{
int k;
struct stu *head,*h;
printf ("请输入总人数：");
scanf ("%d",&n);
printf ("请输入退出圈子的人的编号：");
scanf("%d",&m);
printf ("请输入开始报数的人的编号:");
scanf ("%d",&k);
head=create ();
h=get_index(head,k);
if (m%2==0) f1(head,h);
else f2(head,h);
}

绝对可以运行！

/*
【基本要求】
基本的约瑟夫的描述：
古代某法官要判决N个犯人的死刑，他有一条荒唐的法律，将犯人站成一个圆圈，
从第S个人开始数起，每数到第D个犯人，就拉出来处决，然后再数D个，数到的人再处决，
直到剩下的最后一个可赦免。

发展的约瑟夫的描述：
古代某法官要判决N个犯人的死刑，
但这N个人每人持有一个密码，他有一条荒唐的法律，将犯人站成一个圆圈，
法官先给出一个密码M，从第S个人开始数起，每数到第M个犯人，就拉出来处决，
再根据这个人所持有的密码F，然后再数F个，数到的人再处决，
以此类推直到剩下的最后一个可赦免。

【测试数据】
数据请自己添加。
*/
#include <iostream>
using namespace std;

// 表示一个犯人的结构体
struct Prisoner
{
// 编号
int id;
// 密码
int pass;
// 用于链表的指针
struct Prisoner * pre;
struct Prisoner * next;
};

class JosephCircle
{
public:
// 基本的约瑟夫构造函数
JosephCircle(int N,int S,int D);
// 发展的约瑟夫构造函数
JosephCircle(int N,int S,int M,int password[]);

// 输出约瑟夫环
void print();
// 开始处决犯人
void start();
private:
// 约瑟夫环的头指针
struct Prisoner * head;
// 第一个被处决的犯人的节点指针
struct Prisoner * firstPunishedPrision;
};

JosephCircle::JosephCircle(int N,int S,int D)
{
struct Prisoner * p , *pr;
// 约瑟夫环的头指针初始化为空
this->head = NULL;
// 构造一个由 N 个犯人组成的约瑟夫环
for(int i=1;i<=N;i++)
{
// 当前添加的犯人是第一个犯人，要特殊处理一下
if(this->head == NULL)
{
// 新增一个犯人
p = new struct Prisoner();
// 犯人编号
p -> id = i;
// 犯人密码
p -> pass = D;
// 紧挨着的下一个犯人（因为是环状的，每个人都会有紧挨着的其他犯人）
p -> pre = p;
p -> next = p;
// 约瑟夫环的头指针
this->head = pr = p;
}
else
{
p = new struct Prisoner();
p -> id = i;
p -> pass = D;
p -> pre = pr;
p -> next = pr->next;

pr -> next -> pre = p;
pr -> next = p;

pr = p;
}
}

// 寻找约瑟夫环里面第一个被处决的犯人的【节点指针】
firstPunishedPrision = head;
for(int i=2;i<=(S+D-1);i++)
{
this->firstPunishedPrision = this->firstPunishedPrision -> next;
}
}

JosephCircle::JosephCircle(int N,int S,int M,int password[])
{
struct Prisoner * p , *pr;
// 约瑟夫环的头指针初始化为空
this->head = NULL;
// 构造一个由 N 个犯人组成的约瑟夫环
for(int i=1;i<=N;i++)
{
// 当前添加的犯人是第一个犯人，要特殊处理一下
if(this->head == NULL)
{
// 新增一个犯人
p = new struct Prisoner();
// 犯人编号
p -> id = i;
// 犯人密码
p -> pass = password[i-1];
// 紧挨着的下一个犯人（因为是环状的，每个人都会有紧挨着的其他犯人）
p -> pre = p;
p -> next = p;
// 约瑟夫环的头指针
this->head = pr = p;
}
else
{
p = new struct Prisoner();
p -> id = i;
p -> pass = password[i-1];
p -> pre = pr;
p -> next = pr->next;

pr -> next -> pre = p;
pr -> next = p;

pr = p;
}
}

// 寻找约瑟夫环里面第一个被处决的犯人的【节点指针】
firstPunishedPrision = head;
for(int i=2;i<=(S+M-1);i++)
{
this->firstPunishedPrision = this->firstPunishedPrision -> next;
}
}
// 输出约瑟夫环
void JosephCircle::print()
{
struct Prisoner * p = this->head;
if(p != NULL)
{
do
{
cout << "[编号：" << p->id << "，密码：" << p->pass << "]" ;
if(p->next != this->head)
{
cout<<" -> ";
}
p = p->next;
}while(p != this->head);
}
cout << endl << endl;
}

// 开始处决犯人
void JosephCircle::start()
{
struct Prisoner * p = this->firstPunishedPrision,*pr,*q;
int counter = 1;
/*
因为约瑟夫环是一个循环链表（也就是一个圈），
当 p->next != p 的时候，说明圈里面还有多余一个的节点（犯人），
继续数数并处决犯人
*/
while(p->next != p)
{
// q 向当前被处决的犯人
q = p;
// 从约瑟夫环里面删除被处决掉的犯人
q -> pre -> next = q -> next;
q -> next -> pre = q -> pre;
p = p -> next;
// 输出被处决的犯人的信息
cout << "第 "<< (counter++) << " 个被处决的犯人编号：" << q->id <<endl;
// 寻找下一个将要处决的犯人
for(int i=1;i<=(q->pass-1);i++)
{
p = p->next;
}
// 释放内存（被处决掉的犯人）。
free(q);
}

// 输出被赦免的犯人的信息
cout << "被赦免的犯人的编号：" << p->id << endl << endl;;
}

int main(int argc, char *argv[])
{
// 基本的约瑟夫环： JosephCircle(int N,int S,int D);
JosephCircle j1 = JosephCircle(3,1,2);
j1.print();
j1.start();
// 发展的约瑟夫环： JosephCircle(int N,int S,int M,int password[]);
int pass[]={1,5,3};
JosephCircle j2 = JosephCircle(3,1,2,pass);
j2.print();
j2.start();
return 0;
}

#include <iostream>
#include <list>
using namespace std;

// 数学推理方法
int circle_math( int n, int m )
{
int ans = 0;
for( int i = 2; i <= n; i ++ )
ans = ( ans + m ) % i;
return ans + 1 ;
}

// 链表模拟方法
int circle( int n, int m )
{
list<int> data;
list<int>::iterator it, temp;

for( int i = 0; i < n; i ++ )
data.push_back(i);

it = data.begin();

while( data.size() > 1 )
{
for(int i = 1; i < m; i ++ )
{
it ++ ;
if( it == data.end() ) it = data.begin();
}
temp = it;
it ++;
if( it == data.end() ) it = data.begin();
data.erase( temp );
}
return *data.begin() + 1 ;
}

int main()
{
int n, m;
while( n != 0 )
{
cin >> n >> m;
cout << circle_math( n, m ) << endl;
cout << circle( n, m ) << endl;
}
return 0;
}

修改后的版本，解决初始m为1的情况。

#include<stdio.h>
#include<malloc.h>

typedef struct node{
int num;
int val;
struct node* next;
}listnode;
//两个结构体可以合并以减少程序复杂度
typedef listnode* linklist;

int main(){
int n,i,b,m,j;
linklist q=(listnode*)malloc(sizeof(listnode));
q->next=q;//即使只有一个元素，他也是个循环链表
listnode *p;
printf("请输入总人数:");
scanf("%d",&n);
p=q;
for(j=1;j<=n;j++){
printf("请输入第 %d 学生的密码: ",j);
scanf("%d",&b);
q->val=b;
q->num=j;
if(j!=n){
q->next=(listnode*)malloc(sizeof(listnode));
q=q->next;
}
q->next=p;
}//循环结束后，q->next就是链表头
printf("last: num-%d val-%d\n",q->num,q->val);
printf("请输入初值: ");
scanf("%d",&m);
if(m<=0){
printf("错误！\n");
return(1);
}
m=m-1;//提前使q停下，p=q->next，p就是目标。
printf("结果是:\n");
printf("出列顺序是： ");
//使用q为起始点
do{
i=0;//避免m减一后为零的问题
while(i!=m){
q=q->next;
i++;
}
p=q->next;
q->next=p->next;
printf(" %d",p->num);
m=p->val;//你少了这一步。
m=m-1;//提前使q停下，p=q->next，p就是目标。
free(p);
}while(q->next!=q);
printf(" %d\n",q->num);
free(q);
//free(head); //此时head也许已经被free掉
getchar();
getchar();
return(0);
}


解决初始m为1的情况。

#include<stdio.h>
#include<malloc.h>

typedef struct node{
int num;
int val;
struct node* next;
}listnode;
//两个结构体可以合并以减少程序复杂度
typedef listnode* linklist;

int main(){
int n,i,b,m,j;
linklist q=(listnode*)malloc(sizeof(listnode));
q->next=q;//即使只有一个元素，他也是个循环链表
listnode *p;
printf("请输入总人数:");
scanf("%d",&n);
p=q;
for(j=1;j<=n;j++){
printf("请输入第 %d 学生的密码: ",j);
scanf("%d",&b);
q->val=b;
q->num=j;
if(j!=n){
q->next=(listnode*)malloc(sizeof(listnode));
q=q->next;
}
q->next=p;
}//循环结束后，q->next就是链表头
printf("last: num-%d val-%d\n",q->num,q->val);
printf("请输入初值: ");
scanf("%d",&m);
if(m<=0){
printf("错误！\n");
return(1);
}
m=m-1;//提前使q停下，p=q->next，p就是目标。
printf("结果是:\n");
printf("出列顺序是： ");
//使用q为起始点
do{
i=0;//避免m减一后为零的问题
while(i!=m){
q=q->next;
i++;
}
p=q->next;
q->next=p->next;
printf(" %d",p->num);
m=p->val;//你少了这一步。
m=m-1;//提前使q停下，p=q->next，p就是目标。
free(p);
}while(q->next!=q);
printf(" %d\n",q->num);
free(q);
//free(head); //此时head也许已经被free掉
getchar();
getchar();
return(0);
}

谢谢楼主采纳，希望可以帮助到您，不懂得追问。

不好搞

---

南川市15640495308： 一个C++约瑟夫环的问题一群人围坐一圈,每人一个密码,一开始人选一个正整数作为报数上线M,丛第一个人开始顺时针方向自1开始报数,报道M停止,... - ？
於魏小金：[答案] #include /*结构体*/ struct node { int num,secret; struct node *next; }; /*建造循环链表,并返回头指针*/ node *creatlinklist(int m) { node *head,*p,*q; head=p=(node *)malloc(sizeof(node)); int j; printf(＂输入第1个密码:＂); scanf(＂%d＂,&j); p->...

南川市15640495308： C++ 约瑟夫问题: 求源代码 及 说明约瑟夫问题:M个人围成一圈,从第一个人开始报数,数到N的人出圈;再由下一个人开始报数,数到N的人出圈;…….... - ？
於魏小金：[答案] #include＂stdio.h＂int main(void){ int a[100] = {0}; int b[100] = {0}; int m = 0,n = 0; int i = 0,/...

南川市15640495308： C++解决约瑟夫环？
於魏小金： #include <iostream.h> int Josephus(int Child[],int n,int m); void main () { const int num=6; int persons[num],winner; for(int i=0;i<num;i++) persons[i]=i+1; winner=Josephus(persons,num,2); cout<<＂最后一个留下的成员:＂<<winner<<endl; } int ...

南川市15640495308： C++ 约瑟夫环问题 代码求解释~ - ？
於魏小金： 首先,这个代码输出的是,约瑟夫环到达的最后位置.输出结果是15. //把iostream这个文件中的内容复制到这个地方. #include<iostream> using namespace std; int main() {//定义一个常量的整形100,表示人的个数.const int n=100;...

南川市15640495308： 约瑟夫环问题？
於魏小金： #define N 50 // 排队人数(可任意更改) #define CAL 5 //凡报3的人出列(可任意更改) //下面是排队编号函数:从h 开始的n个人依次编号1到n void stdline(int *h,int n) { int i; for(i=1;i<n+1;i++) *(h+i-1)=i; } /*下面函数表示从指针h处开始的人数为...

南川市15640495308： 利用C++解决约瑟夫问题. - ？
於魏小金： 这里补充一下约瑟夫问题的描述:N个人围成一圈,从第一个开始报数,数到M的人出队,然后他的下一位继续从1开始报数,数到M的出队,如此循环直到剩下一个人,求最后剩下的那个人最初是队伍中的第几位.解决这道题可以采用模拟报数...

南川市15640495308： 数组实现约瑟夫环问题,用C++编写？
於魏小金： #include &lt;iostream&gt; using namespace std; int main() { int m, n; while (cin &gt;&gt; n &gt;&gt; m) { int* a = new int[n]; for (int i = 0; i &lt; n; i++) a[i] = i + 1; int j = 1; //用于报数 int k = 0; //遍历数组 int l = n; //跟踪剩余人数 while (l &gt; 1) {//剩余...

南川市15640495308： 帮忙用C++或C编写约瑟夫环的程序 - ？
於魏小金： /* joseph */#include<stdio.h>#include<stdlib.h> typedef struct Node { int password; int num; struct Node *next; }Node,*Link; Link joseph(int n) { Link p,r,q; int i; q=(Node *)malloc(sizeof(Node)); for( i=1;i<=n;i++) { p=(Node *)malloc(sizeof(Node)); if(!p) exit...

南川市15640495308： 用c++数组解决约瑟夫环问题 - ？
於魏小金： #include<stdio.h> int main() { int num[50],n,m,i,j; int len,start = 0,counter = 1; printf(＂总数 报数\n＂); scanf(＂%d%d＂,&n,&m); if(n < 0 || n > 50 ) n = 50; if(m < 1 || m > n) m = n/2; printf(＂人数:%d,报数:%d\n＂,n,m); for(i = 0; i < n; ++i) ...

南川市15640495308： 约瑟夫环问题的C++算法,求用链表和递归两种方法,尽量详细! - ？
於魏小金： #include typedef struct node { //结点类型定义,每个结点表示一个孩子 int data; //用于存放结点(孩子)编号 node *next; node(int _data = 0, node *_next = NULL) //带缺省参数的结点构造函数 : data(_data),next(_next) {} }*PNode, Node, *...