解题思路:
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;
}
如有不对不懂,望提出。或者自行查阅资料。
0.0分
0 人评分
【金明的预算方案】 (C++代码)浏览:940 |
The 3n + 1 problem (C语言代码)浏览:554 |
C语言程序设计教程(第三版)课后习题12.1 (C语言代码)浏览:647 |
排序算法(选择,插入,冒泡)浏览:775 |
筛排处理 (C语言代码)浏览:787 |
简单的a+b (C语言代码)浏览:558 |
用筛法求之N内的素数。 (C语言代码) 详解………………浏览:1021 |
Manchester-汽水瓶问题浏览:4161 |
C语言程序设计教程(第三版)课后习题1.6 (C语言代码)浏览:876 |
回文数字 (C++代码)浏览:891 |