算法练习4~三色棋~
其实算法练习还有1、2、3~不过我对练习4较为感兴趣~所以按照参考资料弄了一遍代码~代码是九九借鉴参考资料的~原本没有注释~是九九自己消化后加上去的~可以拿来看看~
程序代码：/*说明
三色棋的问题最早由E.W.Dijkstra所提出,
他所使用的用语为Dutch Nation
Flag(Dijkstra为荷兰人),而多数的作者则使用Three-Color Flag来称之。
假设有一条绳子,上面有红、白、蓝三种颜色的旗子，起初绳子上的旗
子颜色并没有顺序,您希望将之分类,并排列为蓝、白、红的顺序,要如何
移动次数最少,注意您只能在绳子上进行这个动作,而且一次只能调换两个旗子。
解法
在一条绳子上移动,在程式中也就意味往后移,如下所示:
只是要让移动次数最少的话,就要有些技巧:
如果图中W所在的位置为白色,则W+1,表示未处理部份移至至白色群组。
如果W部份为蓝色,则B与W的元素对调,而B与W必须各+1,表示两个群组都多了一个元素。
如果W所在的位置是红色,则将W与R交换,但R要减1,表示未处理的部份减1。
注意B、W、R并不是三色棋的个数,它们只是一个移动的指标;什么时候移动
结束呢?一开始时未处理的R指标会是等于旗子的总数,当R的索引数减至少于W的
索引数时,表示接下来的旗子就都是红色了,此时就可以结束移动,如下所示:
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define BLUE 'b'
#define WHITE 'w'
#define RED 'r'
#define SWAP(x,y){char temp=0;temp=color[x];color[x]=color[y];color[y]=temp;}//定义交换宏
int main()
{
char color[]={"rwbwwbrbwr"};
int wFlag=0;//初始化处理白色群组标记为0
int bFlag=0;//初始化处理蓝色群组标记为0
int rFlag=strlen(color)-1;//初始化红色群组标记为尾部
int i=0;
for (i=0;i!=(int)strlen(color);++i)
putchar(color[i]);//输出初始化数据
putchar('\n');
while (wFlag<=rFlag)//当白色群组标记<=红色群组标记时
{
while (wFlag<rFlag&&color[wFlag]==WHITE) //当白色群组标记棋子为白色时
++wFlag;//就把白色群组标记移动至非白色棋子
if (color[wFlag]==BLUE&&bFlag!=wFlag)//如果白色群组标记棋子为蓝色时--并且白色群组标记和蓝色群组标记不相同
{
SWAP(bFlag,wFlag);//就交换蓝色棋子和白色棋子
++bFlag;//蓝色棋子标记+1
++wFlag;//白色群组标记+1
continue;
}
if (color[wFlag]==BLUE)//如果白色群组标记棋子为蓝色时--并且白色群组标记和蓝色群组标记(默认)相同
{
++bFlag;//蓝色棋子标记+1
++wFlag;//白色群组标记+1
continue;
}
while (wFlag<rFlag&&color[rFlag]==RED)//移动红色群组标记到非红色棋子(此时默认白色群组标记棋子为红色)
--rFlag;
SWAP(rFlag,wFlag);//就交换白色棋子和红色棋子
--rFlag;//红色棋子标记-1
}
for (i=0;i!=(int)strlen(color);++i)
putchar(color[i]);//输出数据
putchar('\n');
return 0;
}[此贴子已经被作者于2017-2-15 01:11编辑过]
