C語言三色旗問題

有一根繩子，上面有紅、白、藍三種顏色的旗子。繩子上旗子的顏色並沒有順序，現在要對旗子進行分類，按照藍色、白色、紅色的順序排列。只能在繩子上進行移動，並且一次只能調換兩面旗子，怎樣移動才能使旗子移動的次數最少？

演算法思想

旗子在繩子上移動，而且一次只能調換兩面旗子，因此只要保證在移動旗子時，從繩子的開頭開始，遇到藍色旗子向前移動，遇到白色旗子則留在中間，而遇到紅色的旗子則向後移動。要使移動次數最少，可以使用三個指標 b、w、r 分別作為藍旗、白旗和紅旗的指標。

若 w 指標指向的當前旗子為白色，則 w 指標增加 1，表示白旗部分增加一面。若 w 指標指向的當前旗子為藍色，則將 b 指標與 w 指標所指向的旗子交換，同時 b 指標與 w 指標都增加 1，表示藍旗和白旗部分都多了一個元素。若 w 指標指向的當前旗子為紅色，則將 w 指標與 r 指標所指向的旗子交換，同時 r 指標減 1，即 r 指標向前移動，未處理的部分減 1。剛開始時，r 指向繩子中最後一個旗子，之後 r 指標不斷前移，當其位於 w 指標之前，即 r 的值小於 w 的值時，全部旗子處理完畢，可以結束比較和移動旗子操作。

在程式中通過宏定義用大寫字母 'B' 'W' 'R' 分別代表藍色、白色和紅色；字元陣列 “char color[]”表示繩子上的各種顏色的旗子；旗子移動時通過一個 while 迴圈判斷移動過程是否結束，在 while 迴圈中根據旗子的不同顏色進行不同的處理。

程式程式碼

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define BLUE 'B'
#define WHITE 'W'
#define RED 'R'
#define swap(x,y){char temp;
        temp=color[x];
        color[x]=color[y];
        color[y]=temp;}

int main()
{
    char color[]={'R','W','B','W','W','B','R','B','W','R',''};
    int w=0;
    int b=0;
    int r=strlen(color)-1;
    int i;

    for(i=0;i<strlen(color);i++)
        printf("%c ",color[i]);
    printf("n");
    while(w<=r)
    {
        if(color[w]==WHITE)
            w++;
        else
        {
            if(color[w]==BLUE)
            {
                swap(b,w);
                b++;
                w++;
            }
            else
            {
                while(w<r&&color[r]==RED)
                    r--;
                swap(r,w);
                    r--;
            }
        }
    }
    for(i=0;i<strlen(color);i++)
        printf("%c ",color[i]);
    printf("n");
    return 0;
}

偵錯執行結果

交換前旗子顏色排列順序及按順序最少次數移動旗子後的排列順序如下所示：

R W B W W B R B W R
B B B W W W W R R R

總結

在該範例中，分別用語句“int w=0;”“int b = 0;”“int r=strlen(color)-1;”定義並初始化白旗、藍旗、紅旗的指標 w、b、r。在交換不同顏色旗子時，通過旗子的指標實現交換函數 swap 的功能。