Algorithm Gossip:三色旗问题

本文主要是介绍Algorithm Gossip:三色旗问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【问题】假设有一条绳子，上面有红白蓝三种颜色的旗子，开始时旗子的颜色并没有顺序，现将其分类，排成蓝白红的顺序，每次只能调换两个旗子，问怎样移动次数最少？

【算法分析】排列顺序是b、w、r，定义三个指针：

1、b永远指向第一个不是b的元素；

2、w是遍历的指针，向前移动，并判断指向元素，如果指向w则继续前进，如果指向b则与b指向的元素交换,b、w各向前方移动一位，，如果是r则与r指向的元素交换,b、r各向中间移动一位；

3、r从结尾开始永远指向第一个不是r的元素。

【代码实现】

#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 wFlag=0;
    int bFlag=0;
    int rFlag=strlen(color)-1;
    int i;
    for(i=0;i<strlen(color);i++)
    {
        printf("%c ",color[i]);
    }
    printf("\n");
    while(wFlag<=rFlag)
    {
        if(color[wFlag]==WHITE)
        {
            wFlag++;
        }
        else if(color[wFlag]==BLUE)
        {
            SWAP(bFlag,wFlag);
            bFlag++;
            wFlag++;
        }
        else
        {
            while(wFlag<rFlag&&color[rFlag]==RED)
            {
                rFlag--;
            }
            SWAP(rFlag,wFlag);
            rFlag--;

        }
    }
    for(i=0;i<strlen(color);i++)
    {
        printf("%c ",color[i]);
    }
    printf("\n");
    return 0;}