递推解决约瑟夫环问题

￡神魔★判官ぃ 2022-05-31 05:30 123阅读 0赞

**\[cpp\]** [view plain][] [copy][view plain]

[print][view plain] [?][view plain]

1.  \#include <iostream>  
2.  \#include <list>  
3.  using std::cout;  
4.  using std::endl;  
5.  using std::cin;  
6.  using std::list;  
7.     
8.  int main()  
9.  \{  
10.     int total  = 0;  
11.     cout << "Please input total number of people : ";  
12.     cin >> total;  
13.    
14.     int number = 0;  
15.     cout << "Please input selected number : ";  
16.     cin >> number;  
17.    
18.     /\* If number = 3 
19.      \* f(1) = 0 
20.      \* f(2) = 1 = (f(1) + 3) % 2 
21.      \* f(3) = 1 = (f(2) + 3) % 3 
22.      \* f(4) = 0 = (f(3) + 3) % 4 
23.      \* f(5) = 3 = (f(4) + 3) % 5 
24.      \* ... 
25.      \* f(n) = x = (f(n-1) + 3) % n 
26.      \* \*/  
27.    
28.     int last = 0; // f(1) = 0  
29.     for(int i = 2; i <= total; ++i)  
30.     \{  
31.         last = (last + number) % i;  
32.     \}  
33.     cout << "The last one is : " << last + 1 << endl;  
34.    
35.     return 0;  
36. \}

[view plain]: http://blog.csdn.net/qq_35916858/article/details/79239025#

发表评论取消回复

表情：

评论列表（有 0 条评论，123人围观）

还没有评论，来说两句吧...

相关阅读

相关约瑟夫环——公式法（递推公式）

约瑟夫问题约瑟夫问题是个著名的问题：N个人围成一圈，第一个人从1开始报数，报M的将被杀掉，下一个人接着从1开始报。如此反复，最后剩下一个，求最后的胜利者。例如只有

痛定思痛。/ 2024年04月01日 09:42/ 0 赞/ 59 阅读

相关约瑟夫环问题

题目：n 个数字（0,1,…,n-1）形成一个圆圈，从数字 0 开始，每次从这个圆圈中删除第 m 个数字（第一个为当前数字本身，第二个为当前数字的下一个数字）。当一个

分手后的思念是犯贱/ 2022年08月08日 00:57/ 0 赞/ 48 阅读

相关约瑟夫环问题

约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的

╰半橙微兮°/ 2022年08月02日 06:12/ 0 赞/ 32 阅读

相关递推解决约瑟夫环问题

\[cpp\] [view plain][] [copy][view plain] [print][view plain] [?][view plain] 1.

￡神魔★判官ぃ/ 2022年05月31日 05:30/ 0 赞/ 124 阅读

相关约瑟夫环问题

list1 = [1 for _ in range(30)] 用1代表活人,0代表死人,先创建一个30个活人的列表 index = 0 索引,用来遍历

青旅半醒/ 2022年05月30日 10:39/ 0 赞/ 233 阅读

相关约瑟夫环问题

问题描述： N个人围成一圈，从第一个开始报数，第M个将淘汰，退出圈外，重复上述过程n-1次，最后剩下一个，最后留下来的人获胜。求出最后获胜者的编号。 if __n

╰+哭是因爲堅強的太久メ/ 2022年05月17日 01:20/ 0 赞/ 220 阅读

相关约瑟夫环问题

/ 约瑟夫环问题(Josephus) 用户输入M,N值，从1至N开始顺序循环数数，每数到M输出该数值，直至全部输出。写出C程序。（约瑟夫环问题 Joseph

青旅半醒/ 2022年03月27日 14:54/ 0 赞/ 301 阅读

相关约瑟夫环问题

先贴着慢慢研究： [https://www.cnblogs.com/cmmdc/p/7216726.html][https_www.cnblogs.com_cmmdc_

àì夳堔傛蜴生んèń/ 2022年03月17日 14:14/ 0 赞/ 262 阅读

相关约瑟夫环问题

转载自[https://my.oschina.net/jack90john/blog/1791110?p=1][https_my.oschina.net_jack90john_

拼搏现实的明天。/ 2022年03月01日 04:12/ 0 赞/ 307 阅读

相关约瑟夫环问题

问题描述 1 - n 个人围坐一圈，约定编号为k的人开始报数，数到m的那个人出列，直到所有人出列，由此产生一个队编号的序列问题分析 1. 先构造一个环形的单向

叁歲伎倆/ 2021年11月01日 22:40/ 0 赞/ 377 阅读