您的位置:首页 > 教程资讯 > 网络编程 > C语言 > 经典递归——斐波那契数列,汉诺塔

经典递归——斐波那契数列,汉诺塔

发布于:2016-03-05 14:31:31   分享到:

斐波那契

汉诺塔

0 1 1 2 3 5 8 13 21

int fibonacci(int a){
    if(a==0)
        return 0;
    else if(a==1)
        return 1;
    else
        return fibonacci(a-1)+fibonacci(a-2);
}

我也来搞一下这个 汉诺塔的调调:

先来讲一下这个 东西怎么玩儿

需要做的事情是把 1针上的盘子都放到3针上面。

要求每次只能移动一个盘子,并且只能是大盘子在下,小盘子在上,对于每两个盘子来说。

所以为了实现这一目的

Step1: 把1针上的最后一个盘子放到3针上面。//移动

【前提:这样就需要先把n-1盘子放到2针上面。 也就是Step0:】

Step0:这样就需要先把n-1盘子放到2针上面。//逻辑

 

//对于代码,这句话本质上相当于 2针是目标,也就是 2针上是需要盛盘子的针。所以2针是目的针,要把n-1个盘子从1针放到2针上,借助3针,所以abc三根针的关系在hanoi(n,a,b,c)的本质是:a作为移出针,b作为借助针,c作为目标针。所以 这里面这句话应该写作:hanoi(n-1,a,c,b);

Step1:

Step2:前提把n-2个盘子放到1针上。//逻辑

所以从2针出来,放到1针上,借助,3针。这几个参数就是213.

Step3:把2针上的最后一个盘子放到3针上。//移动

 

然后 把n-3个盘子放到2针上面,也就是 Step0:

然后再 Step1

所以 大概是这样的:

void hanoi(int n,int a,int b,int c){    
    if(n==1) 
        printf("%d -> %d \n",a,c);//移动 
    else{
        hanoi(n-1,a,c,b);
        printf("%d -> %d \n",a,c);//移动 
        hanoi(n-1,b,a,c);
    }
}

运行结果:

代码:

/**

#include 


int fibonacci(int);
void hanoi(int n ,int a,int b, int c);

int main(int argc, char** argv) {
    
    //printf("%d",fibonacci(1));
    hanoi(3,1,2,3);
    
    
    return 0;
}

void hanoi(int n,int a,int b,int c){
    
    
    if(n==1) 
        printf("%d -> %d \n",a,c);//移动 
    else{
        hanoi(n-1,a,c,b);
        printf("%d -> %d \n",a,c);//移动 
        hanoi(n-1,b,a,c);
    }
    
}
/**
    返回第a个数的大小,从0开始。 
*/
int fibonacci(int a){
    if(a==0)
        return 0;
    else if(a==1)
        return 1;
    else
        return fibonacci(a-1)+fibonacci(a-2);
}

*/

试试4个的:

 

大概那眼睛移动了一下,应该是没有问题的。

再来回顾一下代码:

/**
    n代表要移动的盘子的个数。 
    a 代表从哪跟针往外移出。  移出针 
    b代表借助哪跟针。         借助针 
    c代表要移动到哪根针。     目的针 
*/
void hanoi(int n,int a,int b,int c){
    if(n==1) 
        printf("%d -> %d \n",a,c);//移动 
    else{
        hanoi(n-1,a,c,b);//逻辑 
        printf("%d -> %d \n",a,c);//移动 
        hanoi(n-1,b,a,c);//逻辑 
    }
}

 

如果只有一个盘子,就把盘子直接从1移动到3.

否则就把n-1个盘子移动到2.

然后把盘子放到3上。

再把剩下的盘子从2移到3上。

 

应该可以开始默写了

Hanoi(int n,int from,int rent,int destination){
    If(n==1) 
    printf("%d -> %d",from,destination);
    Else{
    Hanoi(n-1,from,destination,rent);
    Printf("%d ->%d",from,destination);
    Hanoi(n-1,rent,from,destination);
}

不看还是会忘的。总之这就是这么个事儿,算法么~大都是背下来的。哪有那么多真正会的人。。。

 

以下源代码:

#include 


int fibonacci(int);
void hanoi(int n ,int a,int b, int c);

int main(int argc, char** argv) {
    
    //printf("%d",fibonacci(1));
    hanoi(4,1,2,3);
    
    
    return 0;
}

/**
    n代表要移动的盘子的个数。 
    a 代表从哪跟针往外移出。  移出针 
    b代表借助哪跟针。         借助针 
    c代表要移动到哪根针。     目的针 
*/
void hanoi(int n,int a,int b,int c){
    if(n==1) 
        printf("%d -> %d \n",a,c);//移动 
    else{
        hanoi(n-1,a,c,b);//逻辑 
        printf("%d -> %d \n",a,c);//移动 
        hanoi(n-1,b,a,c);//逻辑 
    }
}

/**
    返回第a个数的大小,从0开始。 
*/
int fibonacci(int a){
    if(a==0)
        return 0;
    else if(a==1)
        return 1;
    else
        return fibonacci(a-1)+fibonacci(a-2);
}

标签:

C语言 递归

上一篇:二级指针与多级指针

下一篇:递归练习

关于我们  加入我们  版权声明  商务合作  友情链接  网站地图  站长统计

脚本大全-脚本语言之家-版权所有 

Copyright (C) 2016 jiaoben.net, All Rights Reserved