线性表应用：约瑟夫问题（猴子选大王）（循环链表，数组，递归）

  1 描述:一群猴子要选新猴王。新猴王的选择方法是：让N只候选猴子围成一圈，从某位置起顺序编号为1~N号。从第1号开始报数，每轮从1报到3，凡报到3的猴子即退出圈子，接着又从紧邻的下一只猴子开始同样的报数。
  2 如此不断循环，最后剩下的一只猴子就选为猴王。请问是原来第几号猴子当选猴王？
  3 //用循环链表
  4 #include<stdio.h>
  5 #include<stdlib.h>
  6 
  7 typedef struct node
  8 {
  9     int data;
 10     struct node *next;
 11 }node;
 12 
 13 node *create(int n)
 14 {
 15     node *head;
 16     node *p = NULL;
 17     head = (node *)malloc(sizeof(node));
 18     p = head;  //p为指向当前结点的指针 
 19     node *s;
 20     int i = 1;
 21     
 22     if(n != 0)
 23     {
 24         while(i <= n)
 25         {
 26             s = (node *)malloc(sizeof(node));   //临时的结点 
 27             s->data = i++;  //第一个结点的值为1 第二个结点的值为2 先给值i才++ 
 28             p->next = s;  //头结点的指针域指向第一个结点 
 29             p = s; //把第一个结点给当前结点  为了下一次p->next; 
 30         } 
 31         s->next = head->next; //s为插入的最后一个结点 让它指向头结点的下一个结点即第一个结点 
 32     }
 33     
 34     free(head);  //已经是一个环了 把头结点释放 
 35     
 36     return s->next; //s为最后一个结点它指向第一个结点 
 37     
 38 }
 39 
 40 int main(void)
 41 {
 42     int n；
 43     int m = 3;
 44     node *p;
 45     node *temp; //临时 
 46     scanf("%d",&n);
 47     p = create(n);
 48     m %= n; //m == 2 
 49     while(p != p->next)  //当自己指向自己时 就说明已经空了 
 50     {
 51         for(int i=1; i<m-1; i++)
 52         {
 53             p = p->next; //p原来指向第一个结点 p->next便是第二个结点 
 54         }
 55         
 56         //printf("%d->",p->next->data); //输入第三个结点  过程 
 57         
 58         temp = p->next;//开始删除结点 
 59         p->next = temp->next;
 60         free(temp);
 61         
 62         p = p->next;//从当前开始继续数 
 63     }
 64     
 65     printf("%d",p->data); //结果
 66     return 0;
 67 }
 68 
 69 
 70 //普通用数组
 71 #include<stdio.h>
 72 
 73 #define N 1000
 74 
 75 int main(void)
 76 {
 77     int monkey[N];
 78     int index = 0; //当下标 
 79     int i = 1;
 80     int counter; //记录猴子总数 
 81     
 82     int num;
 83     
 84     scanf("%d",&num); 
 85     counter = num; 
 86     
 87     while(counter > 1)
 88     {
 89         if(monkey[index] != -1)
 90         {
 91             if(i == 3)
 92             {
 93                 monkey[index] = -1;  //将数到3的猴子退出圈，并标志为-1
 94                 counter--; 
 95             }
 96             
 97             i++;
 98             
 99             if(i > 3) //如果i>3了 再回到1 
100             {
101                 i = 1;
102             }
103         }
104         
105         index++;   
106         if(index >= num)
107         {
108             index = 0;  //回到0 
109         }
110         
111     }
112     
113     for(int i = 0; i < num; i++)
114     {
115         if(monkey[i] != -1)
116         {
117             printf("%d",i+1);
118         }
119     }
120     
121     return 0;
122 }
123 
124 
125 
126 //用递归（强的一批）
127 #include<stdio.h>
128 
129 int fun(int n)
130 {
131     if(n == 1)
132     return 0;
133     
134     return (fun(n-1)+3)%n;
135 }
136 
137 int main(void)
138 {
139     int num;
140     scanf("%d",&num);
141     
142     printf("%d",fun(num)+1);
143     
144     return 0;
145 }