C語(yǔ)言三色旗問(wèn)題

有一根繩子，上面有紅、白、藍(lán)三種顏色的旗子。繩子上旗子的顏色并沒有順序，現(xiàn)在要對(duì)旗子進(jìn)行分類，按照藍(lán)色、白色、紅色的順序排列。只能在繩子上進(jìn)行移動(dòng)，并且一次只能調(diào)換兩面旗子，怎樣移動(dòng)才能使旗子移動(dòng)的次數(shù)最少？

算法思想
旗子在繩子上移動(dòng)，而且一次只能調(diào)換兩面旗子，因此只要保證在移動(dòng)旗子時(shí)，從繩子的開頭開始，遇到藍(lán)色旗子向前移動(dòng)，遇到白色旗子則留在中間，而遇到紅色的旗子則向后移動(dòng)。要使移動(dòng)次數(shù)最少，可以使用三個(gè)指針 b、w、r 分別作為藍(lán)旗、白旗和紅旗的指針。

若 w 指針指向的當(dāng)前旗子為白色，則 w 指針增加 1，表示白旗部分增加一面。若 w 指針指向的當(dāng)前旗子為藍(lán)色，則將 b 指針與 w 指針?biāo)�指向的旗子交換，同時(shí) b 指針與 w 指針都增加 1，表示藍(lán)旗和白旗部分都多了一個(gè)元素。若 w 指針指向的當(dāng)前旗子為紅色，則將 w 指針與 r 指針?biāo)�指向的旗子交換，同時(shí) r 指針減 1，即 r 指針向前移動(dòng)，未處理的部分減 1。剛開始時(shí)，r 指向繩子中最后一個(gè)旗子，之后 r 指針不斷前移，當(dāng)其位于 w 指針之前，即 r 的值小于 w 的值時(shí)，全部旗子處理完畢，可以結(jié)束比較和移動(dòng)旗子操作。


在程序中通過(guò)宏定義用大寫字母 'B' 'W' 'R' 分別代表藍(lán)色、白色和紅色；字符數(shù)組 “char color[]”表示繩子上的各種顏色的旗子；旗子移動(dòng)時(shí)通過(guò)一個(gè) while 循環(huán)判斷移動(dòng)過(guò)程是否結(jié)束，在 while 循環(huán)中根據(jù)旗子的不同顏色進(jìn)行不同的處理。

程序代碼

#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;
}
調(diào)試運(yùn)行結(jié)果
交換前旗子顏色排列順序及按順序最少次數(shù)移動(dòng)旗子后的排列順序如下所示：
R W B W W B R B W R
B B B W W W W R R R
總結(jié)
在該實(shí)例中，分別用語(yǔ)句“int w=0;”“int b = 0;”“int r=strlen(color)-1;”定義并初始化白旗、藍(lán)旗、紅旗的指針 w、b、r。在交換不同顏色旗子時(shí)，通過(guò)旗子的指針實(shí)現(xiàn)交換函數(shù) swap 的功能。