首页 > 代码库 > 三色旗问题
三色旗问题
说明
三色旗的问题最早由 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 }
三色旗问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。