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

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

目录

输出结果

实现代码

输出结果

实现代码

  

   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      #include<iostream> //头文件，识别大部分预处理命令，编译器才会合法识别后边使用的关键字
     
    
   

    

     

    
    

     

      using namespace std;  //T1、命名空间，包括cout、cin、endl等
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      /*
     
    
   

    

     

    
    

     

      函数的嵌套：约瑟夫环问题——n只猴子选猴王的问题
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      */
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //void可知，此函数没有使用返回值
     
    
   

    

     

    
    

     

      void NextPosition(int &p,int tail) //p是当前猴子的下标，执行函数之后得到下一个下标，tail表示最后一只猴子的下标
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

      	p = (p < tail ? p + 1 : 0); //暂时不考虑被淘汰掉的猴子
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int NextNumber(int n, int tail) //当前要报的数字、要报的最大数字
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	return n == tail ? 1 : n + 1; //
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int MonkeyKing(int total, int cycle) //参数输入猴子总数、所报最大数字
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	bool*failure = new bool[total]; //建立total只猴子，为bool型，识别为是否被淘汰
     
    
   

    

     

    
    

     
	memset(failure, 0, sizeof(bool)*total);  //所有猴子初始化为0即false，即没有被淘汰
     
    
   

    

     

    
    

     
	//menset函数对数组进行归0，如果要统一赋其他值，可用for循环
     
    
   

    

     

    
    

     
	int position = total - 1; //当前位置确定为最后一只猴子，
     
    
   

    

     

    
    

     
	int said = 0; //所报数字
     
    
   

    

     

    
    

     
	int i;
     
    
   

    

     

    
    

     
	int remained = total; //剩下的猴子个数
     
    
   

    

     

    
    

     
	while (remained > 1)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     

      		NextPosition(position,total-1); //从当前猴子移动到下一只去
     
    
   

    

     

    
    

     
		if (failure[position] = false) //假如该猴子尚未被淘汰
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     

      			said = NextNumber(said, cycle); //被轮到的猴子应该报到的数
     
    
   

    

     

    
    

     
			cout << "第" << position + 1 << "只猴子报" << said;
     
    
   

    

     

    
    

     
			if (said==cycle) //判断这只猴子报出的数是否为最大值，如果是，则要将其淘汰
     
    
   

    

     

    
    

     

      			{
     
    
   

    

     

    
    

     

       failure[position] = true; //将这只猴子淘汰出去
     
    
   

    

     

    
    

     
 cout << "，被淘汰。剩下" << --remained << "个\n";
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     
			else cout<<"。\n";
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	//for (int i = 0; i < total; i++) if (failure[i] == false) break; //T1、判断猴子是不是没有被汰淘
     
    
   

    

     

    
    

     
	for (i = 0; failure[i]; i++); //T2、最简单的一句话
     
    
   

    

     

    
    

     
	delete []failure;
     
    
   

    

     

    
    

     
	return i; //返回没有被淘汰的猴子下标
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      // void return; int return 0;
     
    
   

    

     

    
    

     

      void main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	cout << "Hello,world！欢迎来到《一个处女座程序猿》的博客！\n";
     
    
   

    

     

    
    

     
	int total,cycle; //定义猴子总数、所报最大数字
     
    
   

    

     

    
    

     
	cout <<"请输入猴子总数："; // << endl
     
    
   

    

     

    
    

     
	cin >> total;
     
    
   

    

     

    
    

     
	cout << "请输入猴子所报最大数：" ;
     
    
   

    

     

    
    

     
	cin >> cycle;
     
    
   

    

     

    
    

     
	cout << "第" << MonkeyKing(total, cycle)+1 <<"个猴子是猴王。\n";
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      	system("pause");
     
    
   

    

     

    
    

     
	return;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: yunyaniu.blog.csdn.net，作者：一个处女座的程序猿，版权归原作者所有，如需转载，请联系作者。

原文链接：yunyaniu.blog.csdn.net/article/details/103330046