java难吗 约瑟夫问题:M个人围成一圈，从第一个人开始依次从1到N循环报数，每当报数为N时此人出圈，直到剩一人为止？
约瑟夫问题:M个人围成一圈，从第一个人开始依次从1到N循环报数，每当报数为N时此人出圈，直到剩一人为止？
这个问题可以用数学方法解决。有n个人（编号为0~（n-1）），他们从0开始计数并从（m-1）退出，剩下的人继续从0开始计数（在使用数学方法时，我们应该注意从0开始计数，因为余数将得到0的解）本质上是一个递归。n-1人数与n-1人数之间存在递归关系。假设第K个人被删除，那么0，1，2，3，…，K-2，K-1，K，…，n-1//原始序列（1）0，1，2，3，…，K-2，K，…，n-1//第K个人被删除，即序列号为K-1的人被删除。（2） k，k 1，…，n-1，0，1，…，k-2//从序列号k开始，报告0（3）0，1，…，n-k-1，n-k from k 1，…，n-2//进行数字转换。此时，排队的是n-1人。经过（4）转换，完全成为（n-1）个数报告的子问题。注意，（1）和（4）是同一个问题，唯一的区别是数字。比较（4）和（3）不难看出，（3）中“0”之后的数字（（n-3）k）%n=k-3，（（n-2）k）%n=k-2，对于（3）中“0”之前的数字，由于它小于n，也可以看作（0 k）%n=k，（1 k）%n=k 1，因此我们可以得到这样一个规则：设（3）中的某个数为x”，而（4）中相应的数为x，然后是：X “=（X）k）%n。当X是最后一个剩下的人数时，当队列中只剩下一个人时，很明显X=0。这时，当有两个人的时候，我们可以回到X对应的数字，当有三个人到n个人的时候，我们可以回到X对应的数字，X的序列号就是这个数字。递归表达式如下：#include<stdio。H>int main（）{int m，N，s=0 scanf（%d%d”，&m，&n）for（int i=2I<=mi）s=（s N）%i printf（%dN”，s 1）返回0}
版权声明：本文内容由互联网用户自发贡献，本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。
