# The fourth linear table of C/C + + -- four monkeys choose King

``````<span style="font-family:KaiTi_GB2312;font-size:14px;">/*
*Copyright(c)2017,School of computer science, Yantai University
*All right reserved.
*File name: main.cpp list.h list.cpp
*Author: Huang Shisheng
*Completion date: September 27, 2017
*Version number: v1.0
*
*Problem Description: as follows
*Enter Description: enter M and N
*Program output: what is the monkey number of the king
*/</span> ``````

Problem Description:

A group of monkeys, numbered 1,2,3...M, sit in a circle in the order of 1-M. Count from the first one. Every time you count to the nth one, the monkey will leave the circle. In this way, it will come down in turn until there is only the last monkey left in the circle. Then the monkey is the king.

The code is as follows:

``````#include <iostream>
using namespace std;
struct Monkey
{
int num;  //Monkey number
struct Monkey *next; //Next monkey
};

int main()
{
int m,n,i,j,king;
cout<<"Input the number of monkeys and the number of monkeys N:";
cin>>m>>n;
if(n==1)
{
king=m;
}
else
{
//Create a circle of monkeys
p1=p2=new Monkey;
p1->num=1;
for(i=1; i<m; i++)  //Other m-1 monkeys
{
p1=new Monkey;  //p1 is new
p1->num=i+1;
p2->next=p1;
p2=p1;          //p2 always last
}
p2->next=head;      //The last one points to the first one again and becomes a circle

//Now it's time to count
for(i=1; i<m; i++)  //Cycle m-1 times, eliminate m-1 monkeys
{
//Starting from p1, count n-1 to find the nth one
for(j=1; j<n-1; j++)  //Actually find the n-1 first, and the next one will be eliminated
p1=p1->next;    //In a circle, you may start counting from the first one again, if it has not been eliminated

//Eureka,
p2=p1->next;  //p2 will be deleted
//Cout < < No. < I < < round elimination < < P2 - > num < < endl; / / the intermediate results can be observed in this way
p1->next=p2->next;  //p2 is thus "elevated"
p1=p2->next;  //A new starting point for the next round of counting
}
king=p1->num;
delete p1;
}
cout<<"The monkey king's number is:"<<king<<endl;
return 0;
}
``````

Operation result:

Learning experience:

The difficulty of this project is very high. It uses the Joseph problem that I learned in my freshman semester. Your code can't be written correctly, but most of your code awareness should be understood.

Published 34 original articles· Zan Zan 9. 10000 visitors+

Added by RosieisSweet on Wed, 01 Apr 2020 23:36:11 +0300