首页 > 编程知识 正文

约瑟夫环问题思路流程图,约瑟夫环遇到的问题有哪些

时间:2023-05-04 17:56:38 阅读:182387 作者:3410

问题说明:

编号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; }执行结果:

版权声明:该文观点仅代表作者本人。处理文章:请发送邮件至 三1五14八八95#扣扣.com 举报,一经查实,本站将立刻删除。