昨天去面试，结果中间还插了一个小时的上机(给个laptop，Windows+VC环境，用惯Vim结果好不习惯^_^)，其中一题如下：
有N个人按照1到N编号围成一个圈做游戏
从第一个人开始从1报数,数到M的人退出游戏,他后面的人接着重新从1开始报数，一直持续到所有人都退出．
要求输出退出游戏的人的顺序.
这题以前看过，记得貌似有些数学规律的，忘了，所以只能当场用模拟的方法来做。
当时用的是循环数组来模拟，结果花了半个小时才编译、测试搞定，面试我的人(挺Nice的)看了之后说，答案输出是对的，其实更自然的模拟是用链表。
刚才用链表试了下，果然简单好多，大概五分钟就可以搞定。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
int n, m;
struct Item {
int number;
struct Item *next;
};
void
solve(int n, int m)
{
int i, j;
assert(n>0 && m<=n);
struct Item *items = (struct Item *)malloc(sizeof(struct Item) * n);
assert(items != NULL);
/* init */
for(i=0; i<n-1; ++i) {
items[i].number = i+1;
items[i].next = items+i+1;
}
items[n-1].number = n;
items[n-1].next = items;
/* simulate */
struct Item *cur, *prev = NULL;
cur = items;
while(n--) {
j = m;
while(--j) {
prev = cur;
cur = cur->next;
}
printf("%d\n", cur->number);
prev->next = cur->next;
cur = cur->next;
}
free(items);
}
int
main(int argc, char **argv)
{
while(scanf("%d %d", &n, &m) != EOF) {
printf("Result of (N=%d, M=%d)\n", n, m);
solve(n, m);
}
return 0;
}