【数据结构】汉诺塔和菲波那切数列--递归

待我称王封你为后i 2022-09-30 00:51 197阅读 0赞

# 汉诺塔 #

![图示][SouthEast]

<?php
    $i=1;//记录移动次数
    function move($n,$from,$to){
        
        global $i;//获取全局变量
        echo "第{$i}步：将第{$n}号盘子从{$from}移到{$to}上<br>";
        $i++;
    }
    function hanno($n,$from,$depend_on,$to){
        
        if($n==1){
            move($n,$from,$to);//如果只剩下一个盘子，直接移到C上
        }else{
            hanno($n-1,$from,$to,$depend_on);//将n-1个盘子借助C从A移到B上
            move($n,$from,$to);//将第n个盘子从A移到C上
            hanno($n-1,$depend_on,$from,$to);//将n-1个盘子借助A从B移到C上
        }
    }
    
    hanno(3,"A","B","C");//4个盘子，A，B，C三个柱子

运行结果如下：

第1步：将第1号盘子从A移到C上  
第2步：将第2号盘子从A移到B上  
第3步：将第1号盘子从C移到B上  
第4步：将第3号盘子从A移到C上  
第5步：将第1号盘子从B移到A上  
第6步：将第2号盘子从B移到C上  
第7步：将第1号盘子从A移到C上

# 斐波那契数列 #

斐波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368……..

这个数列从第3项开始，每一项都等于前两项之和。

有趣的是，这样一个完全是自然数的数列，通项公式却是用无理数来表达的。而且当n趋向于无穷大时，前一项与后一项的比值越来越逼近黄金分割0.618，所以又称为黄金分割数列。

<?php
    function Fibonacci($n){
        
        if($n==1||$n==2){
       //如果n=1或者n=2直接返回1
            return 1;
        }
        return Fibonacci($n-1)+Fibonacci($n-2);//递归求第n-1和n-2的和
    }
    
    for($i=1;$i<=10;$i++){
        echo Fibonacci($i)." ";
    }

[SouthEast]: /images/20220708/444a82392fcb48eabc77858b2b073864.png