每日一算法:三色旗问题

问题描述

三色旗的问题最早由E.W.Dijkstra所提出，他所使用的用语为Dutch Nation Flag(Dijkstra为荷兰人)，而多数的作者则使用Three-Color Flag来称之。
假设有一条绳子，上面有红、白、蓝三种颜色的旗子，起初绳子上的旗子颜色并没有顺序，
您希望将之分类，并排列为蓝、白、红的顺序，要如何移动次数才会最少，注意您只能在绳子上进行这个动作，而且一次只能调换两个旗子。

 
我们可以定义三个指针 a、b、c 。a和b指向第一个元素，c指向最后一个元素。
a的作用是确保蓝色的旗子移到左边，而c的作用是确保红色的旗子移到右边。b则用于顺序访问各个旗子。

 思路如下：查看b所指向的旗子的颜色，如果是白色的，则不移动任何旗子（因为要求白色的旗子在中间，所以不去动它），将b往后移一位。
 如果是红色的，此时将b所指向的旗子和c所指向的旗子交换位置，同时c往前移一位。（如果交换前c指向的是红色旗帜，则需要将c前移到不是红色旗帜处）。
 如果是蓝色的，此时将b所指向的旗子和a所指向的旗子交换位置，同时a往后移一位。（交换后a指向的已经是蓝色的旗子了，所以可以往后移一位了）。
 这里要注意的是b也要后移一位。（这里我也没有弄得很清楚。大概是b不能在a的后面）

 那么什么时候停止交换呢？显然是c都跑到b的后面去的时候，即b>c

      #include <stdio.h>
      #include <stdlib.h>
      #include <string.h>
      #define BLUE 'b'
      #define WHITE 'w'
      #define RED 'r'
      #define SWAP(x, y) {char t; t = x; x = y; y = t;}
      int count = 1;
      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<(int)strlen(color); i++)
      	{
     		printf("%c",color[i]);//打印排序前的字符串
      	}
     	printf("\n");
     	while (wflag <= rflag)
      	{//结束标志 rflag >= wflag
     		if (color[wflag] == WHITE)
      		{//如果当前为白色旗帜，wflag往后移
      			wflag++;
      		}
     		else if(color[wflag] == BLUE)
      		{//如果当前是蓝色旗帜
      			SWAP(color[bflag],color[wflag]);//交换
     			printf("第%d次交换: %s\n",count, color);
      			count++;
      			bflag++;//蓝色旗帜游标后移
      			wflag++;白色旗帜游标后移
      		}
     		else
      		{//如果当前是红色旗帜
     			while (wflag < rflag && color[rflag] == RED)
      			{//红色旗帜游标前移，直到不是红色旗帜
       rflag--;
      			}
      			SWAP(color[rflag],color[wflag]);//交换
     			printf("第%d次交换: %s\n",count, color);
      			count++;
      			rflag--;//红色旗帜游标前移
      		}
      	}
     	for (i=0; i<(int)strlen(color); i++)
      	{
     		printf("%c",color[i]);
      	}
     	printf("\n");
     	return 0;
      }
  
 

文章来源: blog.csdn.net，作者：悦来客栈的老板，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/qq523176585/article/details/14001597