斐波那契数列与帕斯卡三角形教程文件.pptVIP

斐波那契数列与 帕斯卡三角形 一、斐波那契数列 1.斐波那契 “斐波那契数列”的发明者，是意大利数学家列昂纳多·斐波那契。他被人称作“比萨的列昂纳多”。1202年，他撰写了《珠算原理》(Liber Abaci)一书。他是第一个研究了印度和阿拉伯数学理论的欧洲人。他的父亲被比萨的一家商业团体聘任为外交领事，派驻地点相当于今日的阿尔及利亚地区，列昂纳多因此得以在一个阿拉伯 老师的指导下研究数学。他还曾在 埃及、 叙利亚、希腊、西西里和 普罗旺斯研究数学。 2.斐波那契数列来源 根据高德纳的《计算机程序设计艺术》，1150年印度数学家Gopala和Hemachandra在研究箱子包装物件长宽刚好为1和2的可行方法数目时，首先描述这个数列。 斐波那契这个数列来自他的《算盘书》中一道并不出名的问题 一個很有趣的數學問題: 假設每一對新生的小兔子,两个月後便會長大,且每一个月都生一對小兔子。已知每次新生的一對兔子都是一雄一雌,而所有兔子都沒有死去,且隔代的兔子不會互相交配。 若現有一對小兔子,問一年後共有兔子多小對呢? month 1 2 3 4 5 233 144 89 55 34 21 13 8 5 3 2 1 1 兔子總 對數 144 89 55 34 21 13 8 5 3 2 1 1 0 大兔子 對數 89 55 34 21 13 8 5 3 2 1 1 0 1 小兔子 對數 13 12 11 10 9 8 7 6 5 4 3 2 1 月數 一年後兔子的總數為 233 對 3.斐波那契數列 斐波那契数列指的是这样一个数列：1、1、2、3、5、8、13、21、…… 数列中的每一项被称为斐波那契数(Fibonnaci Number) 以符号Fn 表示。 F1 = F2 = 1 ，而 Fn = Fn-1 + Fn-2 (n2) 这个数列从第三项开始，每一项都等于前两项之和。它的通项公式为：(1/√5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}（又叫“比内公式”，是用无理数表示有理数的一个范例。）（√5表示根号5） 有趣的是：这样一个完全是自然数的数列，通项公式居然是用无理数来表达的。 （5）斐波那契数列（f(n)，f(0)=0，f(1)=1，f(2)=1，f(3)=2……）的其他性质： 　　1.f(0)+f(1)+f(2)+…+f(n)=f(n+2)-1 　　2.f(1)+f(3)+f(5)+…+f(2n-1)=f(2n) 　　3.f(2)+f(4)+f(6)+…+f(2n) =f(2n+1)-1 　　4.[f(0)]^2+[f(1)]^2+…+[f(n)]^2=f(n)·f(n+1) 　　5.f(0)-f(1)+f(2)-…+(-1)^n·f(n)=(-1)^n·[f(n+1)-f(n)]+1 　　6.f(m+n)=f(m-1)·f(n-1)+f(m)·f(n) 　　利用这一点，可以用程序编出时间复杂度仅为O（log n）的程序。 　　7.[f(n)]^2=(-1)^(n-1)+f(n-1)·f(n+1) 　　8.f(2n-1)=[f(n)]^2-[f(n-2)]^2 　　9.3f(n)=f(n+2)+f(n-2) 　　10.f(2n-2m-2)[f(2n)+f(2n+2)]=f(2m+2)+f(4n-2m) [ n〉m≥-1,且n≥1] 5.相关的数学问题 1.排列组合 　　有一段楼梯有10级台阶,规定每一步只能跨一级或两级,要登上第10级台阶有几种不同的走法? 　　这就是一个斐波那契数列：登上第一级台阶有一种登法；登上两级台阶，有两种登法；登上三级台阶，有三种登法；登上四级台阶，有五种登法…… 　　1，2，3，5，8，13……所以，登上十级，有89种走法。 2.求递推数列a(1)=1，a(n+1)=1+1/a(n)的通项公式 　　由数学归纳法可以得到：a(n)=F(n+1)/F(n)，将斐波那契数列的通项式代入，化简就得结果。 3.数列与矩阵 对于斐波那契数列1,1,2,3,5,8,13…….有如下定义F(n)=f(n-1)+f(n-2) F(1)=1 F(2)=1对于以下矩阵乘法 它的运算就是F(n+1)=F(n)+F(n-1)F(n)=F(n)可见该矩阵的乘法