C language classic example: monkey chooses King

Question: there are n monkeys numbered in sequence. Report the number from the first monkey. All the monkeys who report m quit, and the last monkey is elected Monkey King

Input: n, m

Output: Monkey King number

The first method is to use array to realize: (it is relatively simple to omit steps)

```#include <stdio.h>
int main()
{
int n;
scanf("%d",&n);
int a[n];
for(int i=0;i<n;i++)
a[i]=1;
int i=1;
int j=0;
int k=0;
while(k<n-1)
{
if(i==3)
{
a[j]=0;
i=1;
j++;
k++;
}
else
{
i++;
j++;
}
}
for(int g=0;g<n;g++)
{
if(a[g]==1)
printf("%d",g+1);
}
return 0;
} */

return 0;
} ```

The second method is to use circular single chain table to realize:

Step 1: create a circular single chain table, and pay attention to freeing the space of the header nodes. Each node includes the number and pointer fields

Step 2: start from the first node p to cycle the number reporting node to the previous node where the node needs to be deleted, then delete the node behind the number reporting node and update the number reporting node (P = P - > pnext)

The third part: when p = P - > pnext, the cycle stops, and the number of the remaining node, i.e. Monkey King, is output

```#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
typedef struct Node
{
int number;//Save number
struct Node *pNext;
}NODE,*PNODE;
PNODE create_list(int len);
void function(PNODE p,int baoshu);
int main()
{
int len;//Number of monkeys
int baoshu;
printf("Please enter the number of monkeys:");
scanf("%d",&len);
printf("Please enter the size of the report:");
scanf("%d",&baoshu);
PNODE p=NULL;
p=create_list(len);
function(p,baoshu);
}
PNODE create_list(int len)
{
int i;
{
printf("Dynamic memory allocation failed!");
exit(-1);
}
PNODE pTail=pHead;//Create a pointer that always points to the end node
for(i=0;i<len;++i)
{
PNODE p=(PNODE)malloc(sizeof(NODE));
if(NULL==p)
{
printf("Dynamic memory allocation failed!");
exit(-1);
}
p->number=i+1;
pTail->pNext=p;
p->pNext=NULL;
pTail=p;
}
return pTail->pNext;//Return the address of the first node
}
void function(PNODE p,int baoshu)
{
int i=0;
int j=0;
for(p;p!=p->pNext;p=p->pNext)
{
i++;
if(i==baoshu-1)
{
j++;
PNODE q=p->pNext;
p->pNext=q->pNext;
printf("The first%d The number of exiting monkeys is:%d\n",j,q->number);
free(q);
i=0;
}
}
printf("The number of Monkey King finally selected is:%d\n",p->number);
return;
}```

Keywords: C

Added by phui_99 on Thu, 02 Jan 2020 18:02:05 +0200