使用php了解9大算法思想

递推法

递推法是按照一定的规律来计算序列中的每个项，通常是通过计算机前面的一些项来得出序列中的指定项的值。

递归法分两类：

• 顺推法：从已知条件出发，逐步推算出要解决的方法；
• 逆推法：从已知的结果出发，用迭代表达式逐步推算出问题开始的条件，即顺推法的逆过程。

1. 斐波那契数列(兔子数列)：有一对兔子，从出生后第三个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔。假设所有兔子都不死，问每个月的兔子总数为多少？

<?php
/**
 * 列举出兔子对数
 * (f1)1,(f2)1,(f3)2,(f4)3,(f5)5,(f6)8,(f7)13,(f8)21,(f9)34....(fn)x
 * 可以看出规律，除了前两个月，后面每个月都是前两个月之和
 * f1=1 
 * f2=1
 * f3=f(3-1)+f(3-2)=f2+f1=2
 * ...
 * fn=f(n-1)+f(n-2)
 * 这里我们求第九个月的兔子对数，根据递推法-顺推法，根据已知条件，逐步（循环）求出结果
 */

// n：月数
function rabbit($n)
{
    if ($n<3) {
        return 1;
    }
    $data=array();
    $data[1]=1;
    $data[2]=1;
    for ($i=3; $i <= $n; $i++) { 
        $data[$i]=$data[$i-1]+$data[$i-2];
        // echo $data[$i]."<br />";
    }
    return $data[$n];
}

echo rabbit(9);

php在线面试题集：http://cainiaophp.com/
php面试讨论群：536633782