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','\0'};
    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 的功能。