2-1 设n个人围坐在一个圆桌的周围,现在从第s个人开始报数,数到第m个人,就让他出局;然后从出局的下一个人重新开始报数,数到第m个人,再让他出局,……,如此反复直到所有的人全部出局为止。下面要解决的Josephus问题是:对于任意给定的n,s和m,求出这n个人的出局序列。请以n=9,s=1,m=5为例,人工模拟Josephus的求解过程以求得问题的解。

解:1,2,3,4,5,6,7,8,9
第一轮5 1.2.3.4.'6'.7.8.9
第二轮1 '2'.3.4.6.7.8.9
第三轮7 2.3.4.6.'8'.9
第四轮4 2.3.'6'.8.9
第五轮3 2.'6'.8.9
第六轮6 2.'8'.9
第七轮9 '2'.8
第八轮2 '8'
第九轮8

2-2 试编写一个求解Josephus问题的函数。用整数序列1,2,3……,n表示顺序围坐在圆桌周围的人,并采用数组表示作为求解过程中使用的数据结构。然后使用n=9,s=1,m=5,以及n=9,s=1,m=0,或者n=9,s=1,m=10作为输入数据,检查你的程序的正确性和健壮性。最后分析所完成算法的时间复杂度。
其实参考答案已经很好了,只是想给出一种不同的方法练习一下。
利用table[1]=2,table[2]=3,table[3]=4,...,将table表串起来,每次报数淘汰后,比如3号淘汰,那么修改table[2]=4,继续报数。
同时引入table[0]=3,表示第一个淘汰的人,然后再将淘汰的人存入table[3],则最后在输出出局顺序时可以比较方便。当然也可以让table[3]=1,表示第一轮被淘汰的,可以让数组直观的表示该人是第几局出局的。视程序需要而定。这两种方法在输出结果和程序的直观性方面要比参考答案的好一点,而且不需要用%运算.
接下来的程序里使用table[0]的方法。

void jparray(int n,int s,int m){
if(m==0||s>n||s==0||n==0){ //参数检查
cerr << "参数无效!要求m,n,s为自然数,且开始人序号s要小于等于n!" << endl;
return;
}
int i,k,j=0;
int table[n+1];
for (i=0;i < n;i++)table[i]=i+1; //把人链起来
table[n]=1; //让尾回到第一个人
int pre=n; //指向前一个人
for (i=s;){ //开始报数的人
for(k=1;k < m;k++){
pre=i;
i=table[i]; //向后走m-1步,报数从1到m.i为报数到m的人。
}
j=table[j]=i; //j为从table[0]开始的出局顺序表。
i=table[pre]=table[i]; //删掉原i,并重建下一轮开始报数人i。
if (i == pre) { //剩下最后一个人了。
table[j]=i; //链上最后一个人
table[i]=0; //结束标志。
return;
}
//以下输出出局顺序。
cout << "圆桌" << n << "个人,从第" << s << "个人开始报数" << m << "的出局顺序是:/n" << endl;
for (i=0;table[i]!=0;i=table[i])cout << table[i] << " " << endl;
}


算法的时间复杂度,n×m+n 为O(nm),这个方法比较适合在n大,m小的时候,此时比参考答案的方法要小很多。

Comments (0)