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