2032 猴子选大王
Description
有N只猴子，从1~N进行编号。它们按照编号的顺时针方向排成一个圆圈，然后从第一只猴子开始报数。第一只猴子报的第一个数字为1，以后每只猴子报的数字都是它们前面猴子所报数字加1。如果一个猴子报的数字是M，则该猴子出列，下一个猴子重新从1开始报数，直到所有猴子都出列为止，最后一个出列的猴子胜出。你的任务是对于给定猴子数量和报数上限值M，确定出能够被选作大王的猴子的编号。
Input
第一行为一个整数N，表示测试数据的组数，接下来的N行中每行包含两个整数，第一个数是猴子的个数，第二个数是报数上限值M（M>1）,两数之间由空格分隔。
Output
输出共N行，每行为对应输入行获胜猴子的编号。
Sample Input
2
8 5
5 8
Sample Output
3
1
#include <stdio.h>
#include <stdlib.h> /* 定义链表节点类型 */
typedef struct node
{
int data;
struct node *next;
}linklist; int creat(int n, int m)
{
linklist *head, *p, *s, *q;
int i, total;
/* 创建循环链表，头节点也存信息 */
head = (linklist*) malloc(sizeof(linklist));
p = head;
p->data = 1;
p->next = p;
/* 初始化循环链表 */
for (i = 2; i <= n; i++)
{
s = (linklist*) malloc(sizeof(linklist));
s->data = i;
s->next = p->next;
p->next = s;
p = p->next;
} p = head; /* 保存节点总数 */
total = n; q = head;
/* 只剩一个节点时停止循环 */
while (total != 1)
{
/* 报数过程，p指向要删除的节点 */
for (i = 1; i < m; i++)
{
p = p->next;
} /* q 指向 p 节点的前驱 */
while (q->next != p)
{
q = q->next;
}
/* 删除 p 节点 */
q->next = p->next;
/* 保存被删除节点指针 */
s = p;
/* p 指向被删除节点的后继 */
p = p->next;
/* 释放被删除的节点 */
free(s);
/* 节点个数减一 */
total--;
}
//free(p);
/* 打印最后剩下的节点序号 */
int vsdata=p->data;
free(p);
return vsdata; }
int main()
{
int n[10], m[10];
/* 读入问题条件 */
int k; scanf("%d", &k); for (int i=0;i<k;i++)
{
scanf("%d%d",&n[i],&m[i]);
}
for (int ii=0;ii<k;ii++)
{
printf("%d\n",creat(n[ii],m[ii]));
} return 0;
}