已知n个人围成一圈(编号:1,2,3,…,n),从编号为1的人开始报数,报数为m的那个人出列;从他的下一个人又从1开始数,同样报数为m的人出列;依此循环下去,直到剩余一个人。求最后这一个人在最开始的序列中编号是几号?
将这n个人从0~n-1编号(1是习惯从0开始;2是如果m大于等于n时,第一个出列的人编号是m%n,m%n可能等于0,简化后续序列的模式化处理),则报数为m-1的人出列,最后结果加1就为原问题的解,以下,我们来分析出列的过程:
第一次出列-n阶约瑟夫环的问题(n个人)
0,1,2,3,4,5,…,n-2,n-1
第一次出列的人的编号为**(m-1)%n1**(记n1为第一次编号的总人数),从他的下一个人又开始从0开始报数,为了方便我们记k1=m%n1,如下:
0,1,2,3,4,5,…,k1-1(第一次出列人的编号(m-1)%n1),k1,k1 1,…,n-2,n-1
由于第二次出列是是从k1开始,又从0开始报数,为了便于模式化我们将第一次出列后的序列排序如下:
k1,k1 1,k1 2,…,n-2,n-1,0,1,2,3,4,5,…,k1-3,k1-2(k1-1第一次已经出列)
第二次出列-n-1阶约瑟夫环问题(n-1个人)
对上述序列重新编号:
0,1,2,3,4,5,…,n-2
第二次出列的人的编号为**(m-1)%n2**(记n2为第一次编号的总人数),从他的下一个人又开始从0开始报数,为了方便我们记k2=m%n2,如下:
0,1,2,3,4,5,…,k2-1(第二次出列人的编号(m-1)%n2),k2,k2 1,…,n-2
同样重新排序如下:
k2,k2 1,k2 2,…,n-2,n-1,0,1,2,3,4,5,…,k2-3,k2-2(k2-1第二次已经出列)
第三次出列-n-2阶约瑟夫环问题(n-2个人)
对上述序列重新编号:
0,1,2,3,4,5,…,n-3
…
第N-1次出列-2阶约瑟夫环问题(2个人)
k(n-1),k(n-1) 1
重新编号:
0,1
第n-1次出列的人的编号为:m%n(n-1),记下一个人的为k(n-1)=m%n2
k(n-1)
第N次出列-1阶约瑟夫环问题(1个人)
对上述序列重新编号:
0
直接得出结果为0。
以上我们将问题转换为模式相同且规模逐渐缩小的问题,当规模最小即只有一个人n=1时,报数为m-1的人出列,最后出列的人编号为0;当n=2时,报数为m-1的人出列,最后出列人的编号是多少?应该是只有一个人时得到最后出列的序号加上m(因为报数为m-1的人已经出列,剩下那个人才最后出列所以才加上m)
n=1时,f(1)=0;
n=2时,f(2)=[f(1) m]%2;
n=2时,f(3)=[f(2) m]%3;
验证结果:2个人围成一圈,数到3的那人出列,求最后那个人的编号?n=2,m=3
f(2)=[f(1) m]%2=[0 3]%2=1
最后结果加1,则result=2;
f(1)=0;//递归出口
f(n)=[f(n-1) m]%n;//递归体`
#include<stdio.h>int josephus(int n,int m);int main(){ int n,m; scanf("%d %d",&n,&m); int ret=josephus(n,m); printf("%d",ret 1); return 0;} int josephus(int n,int m){ if(n==1) return 0; else return (josephus(n-1,m) m)%n;}
由于递归的空间复杂度不太友好,进行数学归纳,数学解法如下:
#include<stdio.h>int main(){ int n,m=3; scanf("%d",&n); int ans=0,i=0; for(i=1;i<=n;i ){ ans=(ans m)%i; } printf("%d",ans 1); return 0;}
来源:http://www.icode9.com/content-4-147301.html
联系客服