描述: 一群猴子要选新猴王. 新猴王的选择方法是: 让 N 只候选猴子围成一圈, 从某位置起顺序编号为 1~N 号. 从第 1 号开始报数, 每轮从 1 报到 3, 凡报到 3 的猴子即退出圈子, 接着又从紧邻的下一只猴子开始同样的报数.
如此不断循环, 最后剩下的一只猴子就选为猴王. 请问是原来第几号猴子当选猴王?
- // 用循环链表
- #include<stdio.h>
- #include<stdlib.h>
- typedef struct node
- {
- int data;
- struct node *next;
- }node;
- node *create(int n)
- {
- node *head;
- node *p = NULL;
- head = (node *)malloc(sizeof(node));
- p = head; //p 为指向当前结点的指针
- node *s;
- int i = 1;
- if(n != 0)
- {
- while(i <= n)
- {
- s = (node *)malloc(sizeof(node)); // 临时的结点
- s->data = i++; // 第一个结点的值为 1 第二个结点的值为 2 先给值 i 才 ++
- p->next = s; // 头结点的指针域指向第一个结点
- p = s; // 把第一个结点给当前结点 为了下一次 p->next;
- }
- s->next = head->next; //s 为插入的最后一个结点 让它指向头结点的下一个结点即第一个结点
- }
- free(head); // 已经是一个环了 把头结点释放
- return s->next; //s 为最后一个结点它指向第一个结点
- }
- int main(void)
- {
- int n;
- int m = 3;
- node *p;
- node *temp; // 临时
- scanf("%d",&n);
- p = create(n);
- m %= n; //m == 2
- while(p != p->next) // 当自己指向自己时 就说明已经空了
- {
- for(int i=1; i<m-1; i++)
- {
- p = p->next; //p 原来指向第一个结点 p->next 便是第二个结点
- }
- //printf("%d->",p->next->data); // 输入第三个结点 过程
- temp = p->next;// 开始删除结点
- p->next = temp->next;
- free(temp);
- p = p->next;// 从当前开始继续数
- }
- printf("%d",p->data); // 结果
- return 0;
- }
- // 普通用数组
- #include<stdio.h>
- #define N 1000
- int main(void)
- {
- int monkey[N];
- int index = 0; // 当下标
- int i = 1;
- int counter; // 记录猴子总数
- int num;
- scanf("%d",&num);
- counter = num;
- while(counter> 1)
- {
- if(monkey[index] != -1)
- {
- if(i == 3)
- {
- monkey[index] = -1; // 将数到 3 的猴子退出圈, 并标志为 - 1
- counter--;
- }
- i++;
- if(i> 3) // 如果 i>3 了 再回到 1
- {
- i = 1;
- }
- }
- index++;
- if(index>= num)
- {
- index = 0; // 回到 0
- }
- }
- for(int i = 0; i <num; i++)
- {
- if(monkey[i] != -1)
- {
- printf("%d",i+1);
- }
- }
- return 0;
- }
- // 用递归 (强的一批)
- #include<stdio.h>
- int fun(int n)
- {
- if(n == 1)
- return 0;
- return (fun(n-1)+3)%n;
- }
- int main(void)
- {
- int num;
- scanf("%d",&num);
- printf("%d",fun(num)+1);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3460832.html