其实算法练习还有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编辑过]

不过九九有一个小问题~
这样的定义宏九九还是第一次使用~不知道这样定义宏和定义一个void SWAP(int* x,int* y);有什么不同呢~

九九最近在忙算法代码~也许没这么多时间了~九九也是根据资料敲出来的~这个你可以试试跟踪变量wFlag bFlag rFlag来理解一下~有时间我再讲解一下(事实上也许没有那么多时间了)~~~

等下九九去把测试数据打印出来~这个还是有必要讲解一下的~

这个是测试代码~是在资料提供的基础上添加修改内容的~

#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;}//定义交换宏
void print(char color[])
{
    static int n=0;
    int i=0;

    printf("第%d次交换:",n);
    for (i=0;i!=(int)strlen(color);++i)
        putchar(color[i]);

    putchar('\n');

    ++n;
}
int main()
{

    char color[]={"rwbwwbrbwr"};

    int wFlag=0;//初始化处理白色群组标记为0
    int bFlag=0;//初始化处理蓝色群组标记为0
    int rFlag=strlen(color)-1;//初始化红色群组标记为尾部

    int i=0;

    print(color);

    while (wFlag<=rFlag)//当白色群组标记<=红色群组标记时
    {
        while (wFlag<rFlag&&color[wFlag]==WHITE) //当白色群组标记棋子为白色时
            ++wFlag;//就把白色群组标记移动至非白色棋子

        if (color[wFlag]==BLUE&&bFlag!=wFlag)//如果白色群组标记棋子为蓝色时--并且白色群组标记和蓝色群组标记不相同
        {
            SWAP(bFlag,wFlag);//就交换蓝色棋子和白色棋子
            print(color);
            ++bFlag;//蓝色棋子标记+1
            ++wFlag;//白色群组标记+1
            continue;
        }

        while (color[wFlag]==BLUE)//如果白色群组标记棋子为蓝色时--并且白色群组标记和蓝色群组标记(默认)相同
        {
            ++bFlag;//蓝色棋子标记+1
            ++wFlag;//白色群组标记+1
        }

        while (wFlag<rFlag&&color[rFlag]==RED)//移动红色群组标记到非红色棋子(此时默认白色群组标记棋子为红色)
            --rFlag;

        SWAP(rFlag,wFlag);//就交换白色棋子和红色棋子
        print(color);
        --rFlag;//红色棋子标记-1
    }

    return 0;
}

不在调用函数里用静态变量也好~简单改改就行了~

#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;}//定义交换宏
void print(char color[],int n)
{
    int i=0;

    printf("第%d次交换:",n);
    for (i=0;i!=(int)strlen(color);++i)
        putchar(color[i]);

    putchar('\n');
}
int main()
{

    char color[]={"rwbwwbrbwr"};

    int wFlag=0;//初始化处理白色群组标记为0
    int bFlag=0;//初始化处理蓝色群组标记为0
    int rFlag=strlen(color)-1;//初始化红色群组标记为尾部

    int i=0;
    int n=0;

    print(color,n++);

    while (wFlag<=rFlag)//当白色群组标记<=红色群组标记时
    {
        while (wFlag<rFlag&&color[wFlag]==WHITE) //当白色群组标记棋子为白色时
            ++wFlag;//就把白色群组标记移动至非白色棋子

        if (color[wFlag]==BLUE&&bFlag!=wFlag)//如果白色群组标记棋子为蓝色时--并且白色群组标记和蓝色群组标记不相同
        {
            SWAP(bFlag,wFlag);//就交换蓝色棋子和白色棋子
            print(color,n++);
            ++bFlag;//蓝色棋子标记+1
            ++wFlag;//白色群组标记+1
            continue;
        }

        while (color[wFlag]==BLUE)//如果白色群组标记棋子为蓝色时--并且白色群组标记和蓝色群组标记(默认)相同
        {
            ++bFlag;//蓝色棋子标记+1
            ++wFlag;//白色群组标记+1
        }

        while (wFlag<rFlag&&color[rFlag]==RED)//移动红色群组标记到非红色棋子(此时默认白色群组标记棋子为红色)
            --rFlag;

        SWAP(rFlag,wFlag);//就交换白色棋子和红色棋子
        print(color,n++);
        --rFlag;//红色棋子标记-1
    }

    return 0;
}

看到x版主写的输出格式用%s而参考代码却用循环%c~~有一种被糊弄的感觉看来有时间九九还是要根进一下才行~还有感觉炎版主的递归写法较为清晰易懂~赞一个~

我也感觉是走形式~不过我需要巩固基础~有兴趣可以尝试去弄个非递归的汉诺塔版试试~

受炎版主的递归算法影响~再次提供九九自己写的三色棋代码~

/*说明
    三色棋的问题最早由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<string.h>
#define WHILE 'w'
#define BLUE 'b'
#define RED 'r'
#define SWAP(x,y,c,n){x^=y;y^=x;x^=y;printf("第%d次交换:%s\n",n,c);};
void fun(char s[],int a,int b,int c,int n)
{
    if (a>c)
        return;

    if (s[a]==WHILE)
        return fun(s,a+1,b,c,n);

    if (s[a]==BLUE&&a!=b)
    {
        SWAP(s[a],s[b],s,n);
        return fun(s,a+1,b+1,c,n+1);
    }

    if (s[a]==BLUE)
        return fun(s,a+1,b+1,c,n);

    if (s[c]==RED)
        return fun(s,a,b,c-1,n);

    SWAP(s[a],s[c],s,n);
    fun(s,a,b,c-1,n+1);
}
int main()
{
    char color[]={"wrbbrwwrbr"};

    printf("初始化数据:%s\n",color);

    fun(color,0,0,strlen(color)-1,1);

    return 0;
}

[此贴子已经被作者于2017-2-15 21:37编辑过]

汉诺塔的递归结构可以说是一种深度遍历~像汉诺塔那类递归n个盘子需要移动2^n-1次~这个数让我想到了全组合~可以用非递归的全组合算法(以前写过~想到用链表)来模拟递归来遍历每一种可能~不过这样代码就会显得繁琐很多~当然~递归主要还是用来优化程序结构的~

PS：
这个代码是用来遍历全组合的~

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 15
void print(int a[],int n)
{
    int i=0;

    for (i=0;i<n;++i)
            printf("%d ",a[i]);

    printf("\n");
}
void fun(int a[],int n,int s)
{
    if (n)
    {
        a[n-1]=!a[n-1];
        fun(a,n-1,s);

        print(a,s);

        a[n-1]=!a[n-1];
        fun(a,n-1,s);
    }
}
int main()
{
    int n=0;
    int* a=NULL;
    scanf("%d",&n);

    if (n<1||n>MAX)
        exit(0);

    a=(int* )malloc(n*sizeof(a));
    memset(a,0,n*sizeof(a));

    fun(a,n,n);
    print(a,n);

    free(a);

    return 0;
}

[此贴子已经被作者于2017-2-16 01:02编辑过]