7-28 猴子选大王

一群猴子要选新猴王。新猴王的选择方法是：让N只候选猴子围成一圈，从某位置起顺序编号为1~N号。从第1号开始报数，每轮从1报到3，凡报到3的猴子即退出圈子，接着又从紧邻的下一只猴子开始同样的报数。如此不断循环，最后剩下的一只猴子就选为猴王。请问是原来第几号猴子当选猴王？

输入格式

输入在一行中给一个正整数N（≤1000）。

输出格式

在一行中输出当选猴王的编号。

输入样例

11

输出样例

7

分析与答案

用一个单链表记录最开始的猴子编号，然后开始执行报数（移动指针），每移动两次就删除一个节点，直到只剩下一个节点，其next指针指向自身，输出这个节点记录的猴子编号即可。

#include <stdio.h>
#include <stdlib.h>

typedef struct List{
    int num;
    struct List * next;
}list;

int main(){
    int n;
    scanf("%d",&n);
    int i;
    list * monkey = (list*)malloc(sizeof(list));
    list * start = monkey;
    for(i=1;i<n;i++){
        monkey->num = i;
        monkey->next = (list*)malloc(sizeof(list));
        monkey = monkey->next;
    }
    monkey->num = i;
    monkey->next = start;
    list * end = monkey;
    monkey = monkey->next;
    while(monkey->next!=monkey){
        for(i=1;i<=2;i++){
            monkey = monkey->next;
            end = end->next;
        }
        end->next = monkey->next;
        monkey=monkey->next;
    }
    printf("%d",monkey->num);
    return 0;
}