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 的功能。