约瑟夫(josephus)环是这样的:假设有n个小孩坐成一个环,假如从第一个小孩开始数,如果数到m个小孩,则该小该离开,问最后留下的小孩是第几个小孩?例如:总共有6个小孩,围成一圈,从第一个小孩开始,每次数2个小孩,则游戏情况如下: 小孩序号:1,2,3,4,5,6 离开小孩序号:2,4,6,3,1 最后获胜小孩序号:5
这样的问题,我可以先考虑输入的内容有哪些?输出内容有哪些? 要求用户输入的内容有: 1、是小孩的个数,也就是n的值; 2、是离开小孩的间隔是多少?也就是m的值。 3、所有小孩的序号要求存在数组或者链表中,所以需要定义一个指针,这里我们用数组来存放小孩的序号。 而要求输出的内容是: 1、离开小孩的序号; 2、最后留下小孩的序号; 所以,根据上面分析输入输出参数,我们考虑离开小孩的序号可以直接输出,这样可以使函数的复杂性。那么函数定义如下: //输入参数: //Childs为指向一个整形指针,指向保存小孩数组的首地址; //n为小孩的个数; //m为数小孩的个数; int Josephus(int *Child,int n,int m) { int i=-1,j=0,k=1; //开始数小孩,只到留下一个小孩 while(1) { //数m个小孩 for(j=0;j<m;) { i=(i+1)%n; //取下标加1的模,当i的值在0到n-1之间循环 if(Child[i]!=-1) //小孩在环中则数数有效; j++; }
if(k==n) //如果k==n则表示,此时数组中只留下一个小孩, break; //序号为Child[i]中的值,跳出循环; cout<<Child[i]<<","; //输出离开小孩的序号;
Child[i]=-1; //离开的小孩用-1作标记 k=k+1;
} cout<<endl; return(Child[i]); //返回最获胜小孩的序号 }
完整的程序,在VC6中调试通过。 //----------------------------------------------------------- #include<iostream.h> int Josephus(int *Child,int n,int m); void main() { int *allChild,j,k,l; cin>>j>>k; if((allChild= new int[j])!=NULL) { for(l=0;l<j;l++) { cout<<l+1<<","; allChild[l]=l+1; } cout<<endl; cout<<Josephus(allChild,j,k); } }
int Josephus(int *Child,int n,int m) { int i=-1,j=0,k=1; while(1) { for(j=0;j<m;) { i=(i+1)%n; if(Child[i]!=-1) j++; }
if(k==n) break; cout<<Child[i]<<",";
Child[i]=-1; k=k+1;
} cout<<endl; return(Child[i]); }
|