有n人围成一个圆圈,分别编号1~n,从第1人到m循环报数,凡是报到m者离开圆圈,求n个人离开圆圈的次序。
时间: 2023-05-02 11:05:33 浏览: 299
hh.rar_M?n
根据题意,有n个人围成一个圆圈,编号分别编成1到n,从第1人到m报数,报到m的人离开圆圈,求n个人离开圆圈的顺序。
这是经典的约瑟夫问题,可以用数学公式解决。假设第一次报数后第m个人出圈,那么剩下的n-1个人就组成了一个新的圆圈,并且从第m+1个人开始重新编号,问题就转化成了一个n-1的约瑟夫问题。
设f(n,m)表示n个人围成一个圆圈,每报到m的人出圈,最后剩下的人的编号。
当n=1时,只有一个人,直接出圈,得f(1,m)=0。
当n>1时,第一次报数后第m个人出圈,剩下的人再组成一个新的圆圈,设新圆圈的最终编号是x,则原来的圆圈最终编号是(x+m-1)%n+1。
因此,有f(n,m)=(f(n-1,m)+m)%n。
根据上述公式,可以得到n个人离开圆圈的顺序。
阅读全文