作者 徐镜春
单位 浙江大学
一群猴子要选新猴王。新猴王的选择方法是：让N只候选猴子围成一圈，从某位置起顺序编号为1~N号。从第1号开始报数，每轮从1报到3，凡报到3的猴子即退出圈子，接着又从紧邻的下一只猴子开始同样的报数。如此不断循环，最后剩下的一只猴子就选为猴王。请问是原来第几号猴子当选猴王？
输入格式：
输入在一行中给一个正整数N（≤1000）。
输出格式：
在一行中输出当选猴王的编号。
输入样例：
11
输出样例：
7
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
C程序如下：
#include<stdio.h>
#include<stdlib.h>
//定义数据结构体
typedef int monkeynums;
typedef struct Node {
monkeynums Data;
struct Node* Next;
}node, * List;
List creatNode();//创建一个空链表
void InsertNode(List L, monkeynums x);//向链表中添加数据
void chosemonkeyking(List L);//选出猴王
int main() {
monkeynums num;//定义一个num变量表示输入的猴子个数
List L = creatNode();//创建一个哑结点
scanf("%d", &num);//输入猴子的个数
InsertNode(L, num);//将每个猴子的数据存储到单链表中
chosemonkeyking(L);//选出猴王
}
List creatNode() {
List newNode = (List)malloc(sizeof(node));//向内存申请一片空间
newNode->Next = NULL;//将新结点的Next域赋值为NULL
return newNode;//返回该链表
}
void InsertNode(List L, monkeynums x) {
List pTail = L;//定义一个指针用于存储单链表的头结点
for (int i = 1; i <= x;i++) {//给单链表的每个结点赋值
List list = creatNode();
list->Data = i;
pTail->Next = list;
pTail = list;
}
pTail->Next = L->Next;//闭合该单链表
//使该单链表的最后一个结点指向第一个数据域完成闭环
//形成单向循环链表
}
void chosemonkeyking(List L) {
List p = L->Next;//定义一个指针p指向单链表的第一个数据域
List q = L->Next;//定义一个指针q也指向单链表的第一个数据域
while (1)//一直循环
{
if (q->Next == p) {
break;//当只剩一个数结点时退出循环
}
for (int i = 1;i < 3;i++) {
p = q;//p指针始终在q指针前，用于链接删除结点前后的结点，防止链表断链
q = p->Next;//q指针从当前结点向后指两个结点，该结点就是要删除的结点
}
p->Next = q->Next;//链接要删除结点的前后结点
free(q);//删除结点，释放内存
q = p->Next;//q指针从删除结点的下一个结点开始计数
}
printf("%d", p->Data);//输出选出的MonkeyKing的序号
}
