三色旗问题
最后更新于：2022-04-01 10:11:39
假设有一根绳子，上面有一些红、白、蓝色的旗子。起初旗子的顺序是任意的，现在要求用最少的次数移动这些旗子，使得它们按照蓝、白、红的顺序排列。注意只能在绳子上操作，并且一次只能调换两个旗子。
分析：其实要移动旗子得到要求的结果很简单，但是需要注意的是需要移动最少的次数这个限制条件。
网上的一种解法：
从绳子开头进行，遇到蓝色往前移，遇到白色留在中间，遇到红色往后移，如下所示：
只是要让移动次数最少的话，就要有些技巧：
如果图中W所在的位置为白色，则W+1，表示未处理的部份移至至白色群组。
如果W部份为蓝色，则B与W的元素对调，而B与W必须各+1，表示两个群组都多了一个元素。
如果W所在的位置是红色，则将W与R交换，但R要减1，表示未处理的部份减1。
注意B、W、R并不是三色旗的个数，它们只是一个移动的指标；什幺时候移动结束呢？一开始时未处理的R指标会是等于旗子的总数，当R的索引数减至少于W的索引数时，表示接下来的旗子就都是红色了，此时就可以结束移动，如下所示：
该程序选自：经典算法大全 老奔整理 Email: [ben0133@163.com](#)
~~~
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define BLUE 'b'
#define WHITE 'w'
#define RED 'r'
using namespace std;
int times = 0;
char color[] = {'r', 'w', 'b', 'w', 'w', 'b', 'r', 'b', 'w', 'r', '\0'};
//#define SWAP(x, y) { char temp; \
// temp = color[x]; \
// color[x] = color[y]; \
// color[y] = temp; }
void printArr()
{
cout<<"第"<<times<<"次的排序结果为：";
for (int i =0; i<strlen(color);i++)
{
cout<<color[i];
}
cout<<endl;
}
void SWAP(int x, int y)
{
char temp;
temp = color[x];
color[x] = color[y];
color[y] = temp;
times++;
printArr();
};
int main() {
int wFlag = 0;
int bFlag = 0;
int rFlag = strlen(color) - 1;
int i;
cout<<"移动前：";
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--;
}
}
cout<<"移动后："<<endl;
for(i = 0; i < strlen(color); i++)
printf("%c", color[i]);
printf("\n");
cout<<"cost time is :"<<times<<endl;
system("pause");
return 0;
}
~~~
程序执行结果为：
注意观察打印出来的结果，可以发现有一些冗余的移动，导致移动次数比较大改进的解法如下：进行两趟遍历，首先对于成对的顺序相反的红色和蓝色旗子，交互其位置其次对前后的蓝色和红色旗帜进行整理，使其聚集到一起
~~~
//三色旗问题改进
//可大体分为三步，首先交换b和r的位置，直到所有b都在r之前；
//然后整理前半部分的b，使其都靠前
//最后整理后半部分的r，使其都靠后
#include <iostream>
using namespace std;
int g_nExchangeNum = 0;
char szFlagInput[1024] = {'r','w','b','w', 'w', 'b', 'r', 'b', 'w', 'r', '\0'};
//char szFlagInput[1024] = {"rwwwwrbbbrrwrrbbrrrbbbbwwwbrr"};
void ExchangeColor(char *pSour, char *pDes)
{
char szTemp;
g_nExchangeNum++;
szTemp = *pSour;
*pSour = *pDes;
*pDes = szTemp;
cout<<"第"<<g_nExchangeNum<<"次移动，结果为： "<<szFlagInput<<endl;
}
//r和b互换
void ScanFrist()
{
char *pBlue = szFlagInput;
char *pRed = szFlagInput + strlen(szFlagInput) - 1;
while (pRed > pBlue)
{
while (pBlue < szFlagInput + strlen(szFlagInput) - 1 && *pBlue != 'r' )
{
pBlue++;
}
while(pRed > szFlagInput && *pRed!= 'b')
pRed--;
if(pRed > pBlue)
ExchangeColor(pBlue, pRed);
}
}
//蓝色旗帜调整完毕后，调整红色旗帜
void ScanSecond()
{
char *pWhite = NULL;
char *pBlue = NULL;
char *pRed = NULL;
//调整蓝色旗帜
pRed = szFlagInput ;
while (pRed < szFlagInput+ strlen(szFlagInput))
{
if (*pRed != 'r')
{
pRed++;
}
else
break;
}
if (pRed != szFlagInput) //有蓝色的旗帜
{
if(pRed == szFlagInput + strlen(szFlagInput) )
pBlue = szFlagInput + strlen(szFlagInput) -1;
else
pBlue = pRed - 1;
pWhite = szFlagInput;
while(pWhite < pBlue)
{
while(pWhite< szFlagInput + strlen(szFlagInput) - 1 && *pWhite != 'w')
pWhite++;
while(pBlue > szFlagInput && *pBlue!= 'b')
pBlue--;
if (pWhite < pBlue)
{
ExchangeColor(pWhite,pBlue);
}
}
}
//调整红色旗帜
if(pRed == szFlagInput + strlen(szFlagInput))
return;
pWhite = szFlagInput + strlen(szFlagInput) -1;
while (pWhite > pRed)
{
while(pRed< szFlagInput + strlen(szFlagInput) - 1 && *pRed != 'r')
pRed++;
while( pWhite> szFlagInput && *pWhite!= 'w')
pWhite--;
if (pWhite > pRed)
{
ExchangeColor(pWhite,pRed);
}
}
}
int main()
{
cout<<"未移动前结果为： "<<szFlagInput<<endl;
ScanFrist();
ScanSecond();
cout<<"the color list of the result is :"<<endl;
cout<<" "<<szFlagInput<<endl;
cout<<"总共的交换次数为："<<g_nExchangeNum<<endl;
system("pause");
return 1;
}
~~~
程序执行结果为3，无冗余移动步骤：
