C++：利用C++语言实现约瑟夫环问题——利用函数嵌套+交互式实现n只猴子选猴王

1. 
2. #include<iostream>    //头文件，识别大部分预处理命令，编译器才会合法识别后边使用的关键字
3. using namespace std;  //T1、命名空间，包括cout、cin、endl等
4. 
5. /*
6. 函数的嵌套：约瑟夫环问题——n只猴子选猴王的问题
7. }
8. */
9. 
10. 
11. //void可知，此函数没有使用返回值
12. void NextPosition(int &p,int tail)     //p是当前猴子的下标，执行函数之后得到下一个下标，tail表示最后一只猴子的下标
13. {
14.   p = (p < tail ? p + 1 : 0);        //暂时不考虑被淘汰掉的猴子
15. }
16. 
17. int NextNumber(int n, int tail)        //当前要报的数字、要报的最大数字
18. {
19.   return n == tail ? 1 : n + 1;      //
20. }
21. 
22. int MonkeyKing(int total, int cycle)   //参数输入猴子总数、所报最大数字
23. {
24.   bool*failure = new bool[total];         //建立total只猴子，为bool型，识别为是否被淘汰
25.   memset(failure, 0, sizeof(bool)*total);  //所有猴子初始化为0即false，即没有被淘汰
26.   //menset函数对数组进行归0，如果要统一赋其他值，可用for循环
27.   int position = total - 1;                //当前位置确定为最后一只猴子，
28.   int said = 0;                            //所报数字
29.   int i;
30.   int remained = total;                    //剩下的猴子个数
31.   while (remained > 1)
32.   {
33.     NextPosition(position,total-1);      //从当前猴子移动到下一只去
34.     if (failure[position] = false)       //假如该猴子尚未被淘汰
35.     {
36.       said = NextNumber(said, cycle);             //被轮到的猴子应该报到的数
37.       cout << "第" << position + 1 << "只猴子报" << said;
38.       if (said==cycle)                            //判断这只猴子报出的数是否为最大值，如果是，则要将其淘汰
39.       {
40.         failure[position] = true;               //将这只猴子淘汰出去
41.         cout << "，被淘汰。剩下" << --remained << "个\n";
42.       }
43.       else cout<<"。\n";
44. 
45.     }
46.   }
47.   //for (int i = 0; i < total; i++) if (failure[i] == false) break;  //T1、判断猴子是不是没有被汰淘
48.   for (i = 0; failure[i]; i++);                                  //T2、最简单的一句话
49.   delete []failure;
50.   return i;      //返回没有被淘汰的猴子下标
51. }
52. 
53. // void   return;     int return 0;
54. void main()
55. {
56.   cout << "Hello,world！欢迎来到《一个处女座程序猿》的博客！\n";
57.   int total,cycle;           //定义猴子总数、所报最大数字
58.   cout <<"请输入猴子总数：";          // << endl
59.   cin >> total;
60.   cout << "请输入猴子所报最大数：" ;
61.   cin >> cycle;
62.   cout << "第" << MonkeyKing(total, cycle)+1 <<"个猴子是猴王。\n";
63. 
64.   system("pause");
65.   return;
66. }