问题说明:
编号1,2,…,n的n个人顺时针走一圈,将任意正整数作为通报数上限m,从第一个人开始顺时针从1开始依次通报,在报道m的时候通报数停止。通报m个人,从顺时针的下一个人再次从1开始通报,直到全员通报为止,将最后一个人的号码保持原样
输入输出说明:
m和n由用户输入,并确保m和n的范围为【1,1000000】,输出最后列出的号码。
分析问题:
为了简化说明,试着稍微变换一下吧。 假设标签从0到n-1,报告数量从0到m-1。 (这样的转换对于以后的运算很有用,因为主要是m%n可能为0。 (无论如何,只要在最后的结果上加1就可以了。
假设当前序列的人数为n,首先出发的人的号码为(m-1 ) % n,接下来报告数字的人的号码为m(n,k=m ) n,重新组织剩下的n-1人,得到如下对应关系。
中小学
k 1-1
k 2-2
k 3-3
k 4-4
…… .
中小学教师
中小学n-3
中小学n-2
中小学教师
这个过程实际上是n个约瑟夫环问题下降为n-1个约瑟夫环问题。 用同样的方法,可以从n-2个约瑟夫环问题,到一个约瑟夫环问题。 从缩小这一规模的过程中,可以发现号码的对应关系。 在n-1人的情况下,如果某人的号码是x,则该人的n人的情况下的号码一定是(x k ) (n )
同样,如果求出t人玩的时候最后出局的人的标签为f(t ),则t 1人玩的时候出局的号码为(f ) t (k ) % ) t 1 )
最终总结为递归关系的是
f(n )=) f ) n-1 ) k ) n=) f(n-1 ) m%n ) n=) f ) n-1 ) m ) %n
PS :
如果要求出这个约瑟夫林出场顺序的话,请参考我的另一篇文章:
3358 blog.csdn.net/yi _ Ming _ he/article/details/72859577
参考代码:
# include stdio.hint main ((intans=0,I,n,m; scanf_s('%d%d ',n,m ); for(I=1; i=n; I ) ans=(ansm ) % i; //开始从0开始,因为要还原原来的问题,所以输入1printf('%dn ',ans 1); 返回0; }执行结果: