748:约瑟夫问题
问题描述
约瑟夫问题：有ｎ只猴子，按顺时针方向围成一圈选大王（编号从１到ｎ），从第１号开始报数，一直数到ｍ，数到ｍ的猴子退出圈外，剩下的猴子再接着从1开始报数。就这样，直到圈内只剩下一只猴子时，这个猴子就是猴王，编程求输入ｎ，ｍ后，输出最后猴王的编号。
输入
每行是用空格分开的两个整数，第一个是 n, 第二个是 m ( 0 < m,n <=300)。最后一行是：0 0
输出
对于每行输入数据（最后一行除外)，输出数据也是一行，即最后猴王的编号
样例输入
6 2
12 4
8 3
0 0
样例输出
5
1
7
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
using namespace std;
//所用的全部函数
listnode createlist(int n);
int run(int n,int m);
int cinn();
typedef struct node
{
int number;
struct node *next;
}node,*listnode;
int main()
{
int i=0,x[3000]; //由于要保证一直输入，所以我们以数组X来存放约瑟夫环的值
while(1) //保证以至能输入
{
x[i]=cinn();
if(x[i]==0) //当输入0 0时跳出输入循环，即输入截至
{
break;
}
i++;
}
for(int j=0;j<i;j++)//输出值
{
cout<<x[j]<<endl;
}
return 0;
}
listnode createlist(int n) //很简单的创建单链表，在这里我们没有直接创建为循环链表，因为当m=1时单链表更好操作
{
int number=1;
node*pre,*curr;
listnode l=new node;
l->next=NULL;
l->number=number;
pre=l;
while(--n)
{
curr=new node;
curr->number=++number;
pre->next=curr;
curr->nexy=NULL;
pre=curr;
}
return l;
}
int run (int n,int m)
{
listnode l=createlist(n);
listnode x=1;
node*pre=NULL;
int number=1,temp=0;
if(m==1)
{
while(l->next!=null) //当m=1时单独处理
{
l=l->next;
}
temp=l->next;
}
else //这里就是当m！=1时，讲单链表变为循环链表
{
while(l->next!=NULL)
{
l=l->next;
}
l->next=x; //变换成功
while(x->next!=x) //约瑟夫环运行主要操作
{
for(int i=0;i<m-1;i++) //重点：是m-1
{
pre=x;
x=x->next;
}
pre->next=x->next;
x=pre->next;
}
temp=x->number;
}
return temp;
}
int cinn()
{
int n,m,x;
cin>>n>>m;
if(n==0&&m==0)
{
return 0;
}
else
{
x=run(n,m);
return x;
}
}