C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

解题思路:

1、约瑟夫环问题，利用公式法求解——f(n,m)=(f(n-1,m)+m)%n。此题中m=3。

2、f(n,m)表示n个人，每数到m出局的游戏最后的胜利者的编号。

3、公式推导：用数组存储，假设有11个人时，编号为1、2……11。最后的胜利者编号是7，此时7的数组下标是6。下一轮10个人的时候，胜利者编号可以推导出是4，下标是3。因为第一轮删掉编号为4的人后，之后的人都往前面移动了3位，胜利者也往前移动了3位，所以他的下标位置由6变成3。同理，可以通过10人时的胜利者编号下标位置3逆推出11人时胜利者编号下标位置为6。

4、现在取不确定的n,m。每出局一个人，下一个人成为头，相当于把数组向前移动m位。若已知n-1个人时，胜利者的下标位置为f(n−1,m)，则n个人的时候，就是往后移动m，即f(n,m)=(f(n-1,m)+m)%n。

注意事项:

1、注意递推思想。

2、因为有可能数组越界，超过的部分会被接到头上，所以还要模n。

3、理解这个递推式的核心在于关注胜利者的下标位置是怎么变的。每出局一个人，其实就是把这个数组向前移动了m位。然后逆过来，就可以得到这个递推式。

参考代码:

#include <stdio.h>

int main()

{

    int n, i, m=3;

    int p = 0;  //胜利者的下标位置

    scanf("%d", &n);

    for(i = 2; i <= n; i++)//i=1时就是胜利者。所以从2开始循环

        p = (p+m)%i;

    printf("%d\n", p+1);//要求编号，所以+1

    return 0;

}

如有不对不懂，望提出。或者自行查阅资料。