写了个递归的,  又学到了不少 九九同学的交换宏  xzlxzlxzl同学的不要轻易使用全局变量和在函数里定义静态变量

#include<stdio.h>
#include<string.h>
#define SWAP(x,y,n,a){char temp=0;temp=str[x];str[x]=str[y];str[y]=temp;n++;printf("%d:%s\n",n,a);}//定义交换宏
char t;
int n=0;
char str[11]="wrbbrwwrbr";
int fun(char str[], int b, int w, int r)
{
    int i;
    if(w == r)     //如果过w和r索引下标相等,结束 
    {
        return 0;
    }
    
    for(i = 0; i < r-1; i++)   
    {
        if(str[w+i] == 'b' && (str[b]=='b'))   //如果(w)找到的蓝色和准备要交换的(b)位置上(蓝色)一样 
        {
            fun(str, b+1, w, r);              //b的下标加1 
            break;
        }
        
        else if(str[w+i]=='r' && (str[r] == 'r')) //如果(w)找到的红色和准备要交换的(r)位置上(红色)一样 
        {
            fun(str,b,w,r-1);                   //r的下标加1 
            break;
        }
        
        else if(str[w+i] == 'b')            //如果找到蓝色了 
        {
             SWAP(w+i,b,n,str);            //交换 
             fun(str,b+1,w+1,r);          //b， w下标加1 
             break;
        }
        
        else if(str[w+i] == 'r')         //如果找到红色了 
        {
            SWAP(w+i,r,n,str);          //交换 
            fun(str, b, w+1, r-1);       //w加1, r减1 
            break;
        }
    
        else if(str[w+i] == 'w')      //如果找到白色 
        {
            fun(str,b,w+1,r);      //w加1 
            break;
        }
    }
}
int main(void)
{
    int b=0, w=0, r=strlen(str)-1;
    fun(str, b, w, r);
    
    printf("%d:%s",n+1, str);
    
    return 0;
}

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

个人感觉，你这样练习算法是教条、走形式，作用不大。
我觉得，学习算法还是要有自己的思想才能融会贯通（当然，要有较好的数学基础，否则有的算法你就是啃100遍，记住了，你也不会灵活应用的）。比如，今天看到你提到汉诺塔算法，我下午没事，就在http://mybatis.tk/hanoi/  里看了近一个小时的汉诺塔移动动画，慢慢地就升腾出一个“只要数据结构设计得当可不用递归应该可以做的出来”的感觉，听说谭教授的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编辑过]

那个链表代码修改一下不用递归也能做全组合~以前写的~也许写得没有那么严谨~

#include<stdio.h>
#include<stdlib.h>
#define LEN sizeof(Node)
int count=0;
#define N 5
typedef struct Node
{
    int num;
    struct Node *next;
    struct Node *back;
}Node;
Node *head=NULL;
Node *back=NULL;
Node *p[5];
void set()
{
    int i=0;
    p[i]=head;

    while (i<N-1)
    {
        p[i+1]=p[i]->next;
        i++;
    }
}
void creat()
{
    Node *p1,*p2;
    int i=0,n=N;

    head=NULL;    

    p1=p2=malloc(LEN);
    p1->back=NULL;
    p1->num=1;

    while (--n)
    {
        if (n==N-1)
            head=p1;
        else
            {
                p2->next=p1;
                p1->back=p2;
            }
        p2=p1;
        p1=malloc(LEN);
        p1->num=N-n+1;
    }
    p2->next=p1;
    p1->back=p2;
    p1->next=NULL;
}
void print()
{
    Node *p=head;
    while (p)
    {
        printf("%d ",p->num);
        p=p->next;
    }
    printf("\n");
}
void print_p(int M)
{
    int i;
    for (i=0;i<M;i++)
        printf("%d ",*p[i]);
    printf("\n");
    count++;
}
void fun_1(int M)
{
    while(p[M-1]->next!=NULL)
    {
        print_p(M);
        p[M-1]=p[M-1]->next;
    }
    print_p(M);
}
int fun_2(int M)
{
    int i=1;

    if (M==1)
        return 0;

    while (p[M-i]->back==p[M-i-1])
        {
            i++;
            if (i==M)
                   return 0;
        }
        p[M-i-1]=p[M-i-1]->next;
     while (i)
    {
        p[M-i]=p[M-i-1]->next;
        i--;
    }
    return 1;
}
void my_free()
{
    Node* p=head;

    if (head==NULL)
        return ;

    while (p->next)
    {
        Node* p2=p;
        p=p->next;
        free(p2);
    }

    free(p);
    head=NULL;
}
int main()
{
    int M=0; 
    printf("NULL\n");

    for (M=1;M<=N;++M)
    {
        creat();
        set();
        do
        {
            fun_1(M);
        }while(fun_2(M));
        my_free();
    }
    printf("\n共有%d种组合\n",count+1);
    return 0;
}

你...这思维太跳跃了吧！和组合相关吗？即使相关，你想想，最终完成汉诺塔的移动其实只有唯一的一种路径，要从几亿的排列组合中筛选出唯一的那条路径，是不是太笨了？
另：没有全组合一说，如果有，也只能说任何集合的全组合只有一种。在算法里，排列组合经常一起提及，但实际上组合只是排列的一个子集，排列总数的公式：A(n,m)=n!/(n-m)!(0!=1),组合总数的公式：C(n,m)=n!/(m!*(n-m)!)(0!=1),显然，当n=m时为全组合，C(n,m)=1,全组合只有一种组合。

这个和排列组合没有直接关系~我只是通过排列组合引用了汉诺塔的递归结构~说明汉诺塔的递归结构不用递归还是有可能完成的~

PS:其实我是看见13楼x版主说不用递归去弄汉诺塔于是我就敲了16楼的代码~那递归结构和汉诺塔的很类似~然后17楼就用非递归写法实现类似于16楼的功能~就是为了说明不用递归结构也有可能做出来~

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

宏这个东西，坑太多，能不用就不用。