題目描述
為了縮短領(lǐng)救濟(jì)品的隊(duì)伍，NNGLRP決定了以下策略：每天所有來申請救濟(jì)品的人會被放在一個大圓圈，面朝里面。選定一個人為編號 1 號，其他的就從那個人開始逆時針開始編號直到 N。一個官員一開始逆時針數(shù)，數(shù) k 個申請者，然后另一個官員第 N 個始順時針方向數(shù) m 個申請者，這兩個人就被送去再教育。如果兩個官員數(shù)的是同一個人，那個人則被送去從政，然后2個官員再在剩下的人里面繼續(xù)選直到?jīng)]人剩下來，注意兩個被選 中的人是同時走掉的，所以就有可能兩個官員選中一個人。
[編輯]Input
輸入含有多組測試資料，每組測試資料一列含有三個數(shù) N，k 和 m（k, m > 0，0<N<20）。 當(dāng)輸入為 0 0 0 代表輸入結(jié)束。
[編輯]Output
對每組測試資料輸出一列。輸出被選中的申請者的編號順序（一對一對的）。每個數(shù)的寬度為 3 。每一對前面的那個編號為逆時針數(shù)的官員選出的，后面的那個編號為順時針數(shù)的官員選出的（但是如果這2個官員選出同一個人，那就只會有一個編號）。每一對 之間以逗號分開。格式請參考Sample Output。
[編輯]Sample Input
10 4 3
13 17 42
7 8 47
0 0 0
[編輯]Sample Output
4 8, 9 5, 3 1, 2 6, 10, 7
4 11, 10 1, 8 6, 13 7, 3, 5 12, 9 2
1 3, 5 7, 2 4, 6
這道題目有點(diǎn)繞，也講得不嚴(yán)密。這里主要說下幾個容易錯的地方。
首先是你每次在寫程序之前，都要十分清除規(guī)則，題目中的人是圍著一圈，而且第一個的左邊是第N個人，也就是它是逆時針標(biāo)號的。這個十分關(guān)鍵。
其次是go函數(shù)的實(shí)現(xiàn)，go函數(shù)是數(shù)過L個人，返回最后一個的位置。我并不贊同，某些版本數(shù)組是從1開始計(jì)數(shù)，因?yàn)檫@樣對于表達(dá)式的表達(dá)十分不方便。你可以
自己嘗試用1來做，會很不方便。就是因?yàn)間o函數(shù)是這樣一個函數(shù)，所以當(dāng)我們在下一次迭代的時候的開始位置，一定是為那個人出去的位置，也就是a[i]=0的位置。
所以我們第一次迭代的位置，原本A是應(yīng)該在位置0，B在位置n-1。這時候只能是A在n-1和B在0.（你可以用數(shù)學(xué)歸納法理解）。
1 #include <stdio.h>
2
3 #define MAXN 25
4 int n,k,m;
5 int a[MAXN];
6 int go(int p, int d, int k);//數(shù)過k個人，開始位置p必須是數(shù)1時候的前一個位置。
7 int main() {
8 while (scanf("%d%d%d", &n, &k, &m) == 3 && n) {
9 for (int i = 0; i < n; i++) {
10 a[i] = i + 1;
11 }
12 int left = n;
13 int pA = n-1, pB = 0;
14 int pANext,pBNext;
15 while (left) {
16 pA = go(pA, 1, k);//1表示逆時針，因?yàn)樗悄鏁r針標(biāo)號
17 pB = go(pB, -1, m);//-1表示順時針
18 printf("%3d", pA + 1); left--;
19 if (pA != pB) { printf("%3d", pB + 1); left--;}
20 a[pA] = a[pB] = 0;
21 if (left) printf(",");
22 }
23 printf("\n");
24 }
25 return 0;
26 }
27 int go(int p, int d, int L) {
28 while (L--) {
29 do { p = (p+n+d)%n;} while(a[p] == 0);
30 }
31 return p;
32 }
解析:至于下一個位置為什么是p = (p+n+d)%n.其實(shí)很簡單。因?yàn)槲覀兪且徊讲阶叩?，所以只有兩種邊界情況。假設(shè)當(dāng)前位置是p(0=<p<n),
第一種邊界：p + 1 > n - 1，即 p + 1此時應(yīng)該是到達(dá)0位置，但此時p + 1 = n，如果我們?nèi)∮鄶?shù)，則 （p+1)%T = 0,T = n(T表示這個圓圈的周期大小)。
剛好能符合，又因?yàn)門 = n，所以(P+T+1)%T還是不變的。
第二種邊界: p - 1 < 0, 即 p - 1此時的值是-1，對于這種情況可以反過來看，它是向后退后1個單位，可以看成向前走T - 1個單位即p -1 等效于 p + T - 1
，我們要等到此時的位置，再去余，(P+T-1)%T。
對于情況一、二?？梢詺w納為(P+T+d)%T,當(dāng)為順時針是d取1，否則-1.