正文

python算法（2）兔子产子（斐波那切数列）

IP云
IP云V管理员/0 阅读
11/30
小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

兔子产子

1.问题描述

有一对兔子,从出生后的第3个月起每个月都生一对兔子。小兔子长到第3个月后每个月又生一对兔子,假设所有的兔子都不死,问30个月内每个月的兔子总对数为多少？

2.问题分析

兔子产子问题是一个有趣的古典数学问题,我们画一张表来找下兔子数的规律,如下表所示

月数 小兔子对数 中兔子对数 老兔子对数 兔子总对数
1 1 0 0 1
2 0 1 0 1
3 1 0 1 2
4 1 1 1 3
5 2 1 2 5
6 3 2 3 8
7 5 3 5 13

说明：不满1个月的兔子为小兔子，满1个月不满2个月的为中兔子，满3个月以上的为老兔子。

可以看出，每个月的兔子总数依次为1,1,2,3,5,8,13...这就是 Fibonacci 数列。总结数列规律即为从前两个月的兔子对数可以推出第3个月的兔子对数

3.算法设计

本题目是典型的迭代循环,即是个不断用新值取代变量的旧值,然后由变量旧值递推出变量新值的过程。这种选代与这些因素有关: 初值 、 迭代公式 和 选代次数 。经过问题分析,算法可以描述为

fib n-1 = fiib n-1 = 1(n<3) 初值

fib n = fib n-1 + fib n-2 (n≥3) 迭代公式



用 Python 语言來描述迭代公式即为 fib=fibl+fib2 ,其中 fib 为当前新求出的免子对数, fibl 为前一个月的兔子对数, fib2 为前两个月的免子对数,然后为下一次选代做准备,fib②给fib1①给fib2,进行如下的赋值 fib2=fib1 , fibl=fib ,要注意赋值的次序;选代次数由循环变量控制,为所求的月数。

4.完整程序 
if __name__=="__main__":

    fib1 = 1

    fib2 = 1

    i = 1

    while i <= 15:  #每次求两个，因此循环变量循环到15

        print("%8d    %8d" %(fib1, fib2), end="      ")

        if i % 2 == 0:

            print()

        fib1 = fib1 + fib2  # 最新一个月的兔子数

        fib2 = fib1 + fib2  # 第4个月的兔子数

        i += 1

相关阅读

目录[+]