荷蘭國旗問題

上方的圖片便是一個荷蘭國旗，從圖中我們可以很清楚的看出它的特點,它有三個區域組成，即紅，白，藍。

好，現在我們的問題出來了。現在我們面前有一張桌子，桌子上整齊的擺放著紅色，白色，藍色三種線條，但他們的順序是凌亂的。

要求是：用一個算法把這些線條挑出來重新擺放順序，最后的結果就像上圖的荷蘭國旗，紅色在上，白色在中間，藍色在最下面。

另外，要求在O(n)的復雜度下，使移動次數最少。

算法分析如下：

荷蘭國旗問題其實是一個排序問題。可以將紅，白，藍3種顏色分別用數字0、1和2表示，并使用一個數組來存儲它們。將相同顏色

的線條歸為一類就相當于將數組中的數組按大小進行排序，只不過數組里存儲的數值只有3種而已。其解題的基本策略是遍歷兩個顏色區域，

如果顏色條不屬于所在區域，則交換一個屬于該區域的顏色條。這樣，每一次都是必要的交換，從而實現最少交換次數。

代碼如下：

#include <iostream>
using namespace std;
const int N=10;
int flag[N]; //國旗顏色條數組
int pre[N]; //記錄該白條的前白條位置
int split1; //區域分割1
int split2; //區域分割2
int blue_red; //紅條在藍色區域的標記
int white_red; //紅條在白色區域的標記
int counts = 0;

void out()
{
for (int i=0;i<N;i++)
{
cout<<flag[i];
}
cout<<endl;
}

void swap(int& x,int& y)
{
int temp=x;
x=y;
y=temp;

counts++;
}

void work()
{
for (int i=0;i<split1;i++) //紅色區域：交換非紅條
{
if (flag[i]!=0) //如果不屬于該區域
{
if(blue_red>=split2)
{
swap(flag[i],flag[blue_red]);
blue_red = pre[blue_red];
}
else{
swap(flag[i],flag[white_red]);
white_red = pre[white_red];
}
}
}
int b=N-1; //白、藍區域
for ( i=split1;i<split2;i++)
{
if (flag[i] != 1)
{
while (flag[b]==2) b--;
swap(flag[i],flag[b]);
b--;
}
}
}

//初始化
void init()
{
int red_num = 0; //統計紅色條數
int white_num = 0; //統計白色條數
int preI = -1;
for (int i=0;i<N;i++)
{
flag[i] = rand()%3;
if (flag[i]==0)
{
red_num++;
pre[i] = preI;
preI=i;
}
else
if (flag[i]==1)
{
white_num++;
}
}

//將國旗分成3個顏色區域：
//0~split-1(紅)，split1~split2-1(白),split2~N-1(藍）
split1=red_num;
split2=red_num+white_num;
blue_red=preI;
i=split2-1;
while (flag[i] !=0) i--;
white_red = i;
}

int main()
{
init();
cout<<"原始:"<<endl;
out();

work();
cout<<"移動"<<counts<<"次："<<endl;
out();

return 0;

}

總結

以上是生活随笔為你收集整理的荷兰国旗问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。