UVA133

題目的意思是把一對(duì)人圍成一圈, 隨機(jī)選一個(gè)作為標(biāo)號(hào)1, 并且逆時(shí)針(count-clockwise)編號(hào)，也就是說(shuō)1位于左邊，N位于右邊。然后有兩個(gè)官員，一個(gè)從編號(hào)1開(kāi)始計(jì)數(shù)，計(jì)數(shù)為k，到達(dá)后停下。一個(gè)從N開(kāi)始計(jì)數(shù)，計(jì)數(shù)為m，到達(dá)后停下。在所停下的這個(gè)人面前離開(kāi)隊(duì)列。接著繼續(xù)計(jì)數(shù)直到?jīng)]有人為止。因?yàn)閮蓚€(gè)人是同時(shí)開(kāi)始的，所以可能會(huì)遇到同時(shí)達(dá)到同一個(gè)位置。這時(shí)候一個(gè)人出隊(duì)列就行。

分析

思維很簡(jiǎn)單, 編寫(xiě)walk(start, stepSize, direct)函數(shù)，實(shí)現(xiàn)從start位置開(kāi)始，該位置為無(wú)效位置(既下一個(gè)有效位置的最近的無(wú)效位置, direc為方向)。因?yàn)槟鏁r(shí)針的時(shí)候，數(shù)字是增加的，順時(shí)針的時(shí)候數(shù)字是減小的，所以direct = 1表示逆時(shí)針。

實(shí)現(xiàn)walk的方式更為簡(jiǎn)單， 每次走一步， 判斷邊界條件(=0和>N), 并且判斷該位置是否有效，有效則stepSize-1, 直到stepSize==0，停下的位置就是出隊(duì)列的位置。

總結(jié)

任何復(fù)雜的問(wèn)題, 都可以通過(guò)抽象的定義來(lái)屏蔽復(fù)雜的細(xì)節(jié)。就如通過(guò)walk方法, 先定義好該方法，然后根據(jù)定義實(shí)現(xiàn)該方法即可。

//
// Created by sixleaves on 2016/11/23.
//

#include <cstdio>
#include <cstring>

// direct == 1 表示逆時(shí)針, 起點(diǎn)從N開(kāi)始
// direct == -1 表示順時(shí)針, 起點(diǎn)從1開(kāi)始
// 表示從start位置開(kāi)始走, 走stepSize步, start位置是最靠近下一個(gè)有效位置的無(wú)效位置.(start, start + stepSize]
int n, k, m;
int applicant[26];
int walk(int start, int stepSize, int direct);
int main() {

    while (scanf("%d%d%d", &n, &k, &m) == 3 && n && k && m) {

        for (int i = 0; i<=n; i++) applicant[i] = i;
        int left = n;
        int p1 = n;
        int p2 = 1;
        while (left) {

            p1 = walk(p1, k, 1);
            p2 = walk(p2, m, -1);
            applicant[p1] = 0;
            left--;
            if (p1 != p2) {
                applicant[p2] = 0;
                printf("%3d%3d", p1, p2);
                left--;
            }else {
                printf("%3d", p1);
            }

            if (left) printf(",");
        }
        printf("\n");
    }
    return 0;
}

int walk(int start, int stepSize, int direct) {

    int index = -1;

    while (true) {

        start = start + direct;

        if (start > n) start = 1;
        if (start == 0) start = n;

        if (applicant[start] == 0) continue;

        if (applicant[start])
            stepSize--;

        if (stepSize <= 0) break;
    }

    index = applicant[start];
    return index;
}