约瑟夫环小学解法,约瑟夫环小学奥数

约瑟夫环的算法原理

约瑟夫环运作如下：

1、一群人围在一起坐成 环状（如：N）

2、从某个编号开始报数（如：K）

3、数到某个数（如：M）的时候，此人出列，下一个人重新报数

4、一直循环，直到所有人出列 ，约瑟夫环结束

约瑟夫环问题(基本和进阶)

每一个结点,都要走m步,所有时间复杂度为O(m*n),进阶解法要求做到时间复杂度O(n)

当给定结点的数量和报的数就可以确定最后幸存的结点

base case:当只有一个结点时,结点的编号为1,所以只要确定f(i)和f(i-1)的关系,就可以得出f(N)的结果(即在节点个数为n的情况下的幸存的结点的编号)

}

约瑟夫环的问题

#include stdio.h

int main()

{

int n, m, i, s=0;

printf ("N M = ");

scanf("%d%d", n, m);

for (i=2; i=n; i++) s=(s+m)%i;

printf ("The winner is %d\n", s+1);

}

下面是运行结果

N M = 4 3

The winner is 1

有n个人围成一圈，顺序排号。凡报到3的人退出圈子，问最后留下的是原来第几号的那位？

这是约瑟夫环的数学解法(迭代法)的公式,我们可以这样理解

把n个人想成标号从0开始到n-1的n个人,报到3的人退出圈子,

那么退出圈子的人在0到n-1的标号为(k+3)%n(其中k为n-1个人时退出圈子的人的标号)

因为有一个人退出了圈子,所以还剩下n-1个人,我们对剩下的人重新从0到n-2编号,

同样有公式(k1+3)%n(其中k1为n-2个人时退出圈子的人的标号)得出n-1个人时退出圈子人的标号,

以此类推直到n等于1时kn-1=0也就是1个人时留下的就是标号为0的人

以此有递推公式f(1)=0,f(i)=(f(i-1)+3)%i f(i)为第i次退出圈子的人

我们用for循环从2个人时开始反推,经过n-1次迭代,去除退出圈子的人,

从而可以得到n个人时最后一个退出的人的标号为几,也就是最后留下的人的标号是几,

因为我们每次标号都是从0开始所以最后退出的人的实际编号=标号+1.

有了上述分析我们就不难得出程序(见图)