首页 > 代码库 > 三色旗问题

三色旗问题

说明

三色旗的问题最早由 E.W.Dijkstra 所提出,他所使用的用语为 Dutch Nation

Flag(Dijkstra 为荷兰人),而多数的作者则使用 Three-Color Flag 来称之。

假设有一条绳子,上面有红、白、蓝三种颜色的旗子,起初绳子上的旗子颜色并没

有顺序,您希望将之分类,并排列为蓝、白、红的顺序,要如何移动次数才会最少,注意您只

能在绳子上进行这个动作,而且一次只能调换两个旗子。

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<string.h>
 4 #define BLUE ‘b‘
 5 #define WHITE ‘w‘
 6 #define RED ‘r‘
 7 void swap(char color[],int x,int y);
 8 int main(){
 9     char color[]={r,w,b,w,w,b,r,b,w,r,\0};//初始化color数组
10     int wFlag=0;//记录白旗颜色 
11     int bFlag=0;//记录蓝旗颜色 
12     int rFlag=strlen(color)-1; //记录红旗颜色 =9
13     printf("color 数组的长度:%d\n",strlen(color));//color数组的长度
14     int i;//控制循环的变量i
15     for(i=0;i<strlen(color);i++)
16        printf("%c",color[i]);//将数组先输出一遍
17     printf("\n");
18     //以下程序段完成字符的交换 
19     while(wFlag<=rFlag){  
20         if(color[wFlag]==WHITE)
21            wFlag++;
22         else if(color[wFlag]==BLUE){
23             swap(color,bFlag,wFlag);
24             bFlag++;wFlag++;//因为wFlag从0开始遍历,当
25             //wFlag遍历的结果是蓝色时,bFlag加1,
26              //wFlag要到下一个位置,所以也要加1 
27         }
28         else{
29             //注意这里是循环 ,并且注意循环条件 
30             while(wFlag<rFlag&&color[rFlag]==RED)
31                  rFlag--;
32             swap(color,rFlag,wFlag);//每执行一次交换,将红色旗交换到后面,所以最
33             //后几个肯定是红色旗
34             rFlag--; 
35         }
36     } 
37     for(i=0;i<strlen(color);i++){
38         printf("%c",color[i]);
39     }
40     printf("\n");
41     return 0;
42 }
43 void swap(char color[],int x,int y){//交换函数 
44     char temp;
45     temp=color[x];
46     color[x]=color[y];
47     color[y]=temp;
48 }

技术分享

三色旗问题