描述:约瑟夫问题:有n只猴子,按顺时针方向围成一圈选大王(编号从1到n),从第1号开始报数,一直数到m,数到m的猴子退出圈外,剩下的猴子再接着从1 开始报数。就这样,直到圈内只剩下一只猴子时,这个猴子就是猴王,编程求输入n,m后,输出最后猴王的编号。
输入:每行是用空格分开的两个整数,第一个是 n, 第二个是 m ( 0 < m, n < 300)。最后一行是: 0 0
输出:对于每行输入数据(最后一行除外),输出数据也是一行,即最后猴王的编号
input:
6 2
12 4
8 3
0 0 output:
5
1
7
分析:猴子可以用一个数组来表示,数组的值为猴子的编号,当某只猴子出局即把该编号改为0
说明该猴子出局,当最后只剩下一个不为0的值时该值即为猴王编号。
1 #include<iostream>
2 using namespace std;
3
4 int main()
5 {
6 int n, m;
7 int a[300];
8 while ((cin >> n >> m) && !(n == 0 && m == 0))
9 {
10 for (int i = 0; i < n; i++)
11 a[i] = i + 1;
12 int k = n;//标记剩下的猴子
13 int j = 0;//标记报数m
14 while (k>1)
15 {
16
17 for (int i = 0; i < n; i++)
18 {
19 if (a[i] == 0)
20 continue;
21 else
22 j++;
23 if (j == m) //退出圈外的猴子编号变为0
24 {
25 a[i] = 0; j = 0; k--;
26 }
27 }
28 }
29 for (int i = 0; i < n; i++)
30 {
31 if (a[i] != 0)
32 cout << a[i] << endl;
33 }
34 }
35 system("pause");
36 return 0;
37 }
评论中的算法更简洁
1 #include<iostream>
2 using namespace std;
3
4 int Joseph (int n,int m)
5 {
6 int i, s=0;
7 for (i=2; i<=n; i++)
8 s=(s+m)%i;
9 return (s+1);
10 }
11 int main()
12 {
13 int m,n;
14 cin>>n>>m;
15 cout<<Joseph(n,m)<<endl;
16 return 0;
17 }