昨天去面試，結果中間還插了一個小時的上機(給個laptop，Windows+VC環(huán)境，用慣Vim結果好不習慣^_^)，其中一題如下：
有N個人按照1到N編號圍成一個圈做游戲
從第一個人開始從1報數,數到M的人退出游戲,他后面的人接著重新從1開始報數，一直持續(xù)到所有人都退出．
要求輸出退出游戲的人的順序.
這題以前看過，記得貌似有些數學規(guī)律的，忘了，所以只能當場用模擬的方法來做。
當時用的是循環(huán)數組來模擬，結果花了半個小時才編譯、測試搞定，面試我的人(挺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;
}