递推数列与递归算法.docx

文档介绍：递推数列与递归算法(问题】怎样用讣算机程序解泱裴波那契数列中的计算问题分••••••••••....4°a®［目的］认诅和了解计算机处理问题时的递推与递归算法的实现方法。
【预备知识】
工一)装波那契数列.•了•iwr•、0.•.
在
递推数列与递归算法(问题】怎样用讣算机程序解泱裴波那契数列中的计算问题分••••••••••....4°a®［目的］认诅和了解计算机处理问题时的递推与递归算法的实现方法。
【预备知识】
工一)装波那契数列.•了•iwr•、0.•.
在数学史上，有一个著名的关于兔子生儿育女的问题，
假是兔子在出生两个月后就有生育能力俨并且每一对有生育能力的兔子每个月生1对・兔子气那么从一对有生育能力的兔子开始，整整―年之后,兔子的总数将有多少对?
有一位意大利数学家，菊叫裴波那契(Fibonacci,约1170-1250),在他1228年的手稿中，详细研究了上面送个有趣的问题。
他用按月盘点的方法解答这道复杂问题*
第一个月的月底";1对:小的，有2对兔充
第二个月的月底，老兔子生下1对小兔丑1对新兔予，加上原来已有的2对，1+2=3,
衫三个为做麻材日球生下L林于?.而虹f月出室林F海源寥噩SWB
发育成熟八开始生儿育女；，加上原来已有的3对！2珍=§有了5对兔壬
，可以算出，在这一年中旷每个月的月底'成对兔子的数目4以缆对曦为单位，分别是32/,13,初，34请55i89,144,233/
所以宥何题的答案是,从一对有生殖能力的兔子开始*整整一年之后,.兔子的总数将有377对,
裴波那契爰现，这一连串数目之间有一个简单的规律f将其中任何1个数与它启面一・个数相加,•结果等于再后面的一个数•
例如人2+3=53+5=85+8=13
等等，他指出，：利用这个规律,.可以无限继续推算下表心如果另外一户人家，.,
.•f•0...•••••••成对兔子的数目排成的数列是
L1*》3e5,M13,21t34"55,89,；144,233,377mi数列①叫做斐波那契数列，可用公式.
J。］,尹1*色=.1服=+J=3Q二)求该数列的每一项.
（二）递推与迭我
斐波那契数列的中求每一项的公式建绐出的是数列中的一小递推式，从中可以看出,所谓“递推、是指在前面f或几个结果的基础上推出下一个结果意解决递推问题必须具备两个要求！（1）初始余件;Q）递推关系（或递推公式）『在上面的问题中,初始条件为••.•••••.4、•••.
=1,%=1
递推关系为.
■.♦.■■a
合起来就表示为公或a】==14=%+%一2伽=345•)1L
数列中有许多问题没有现成的公式直接求出结果，而必须采用递推的方法一步一步地推出最后的结果或:在斐波那契数列中当徐时因为没有任何现成的公式能直接求出第n不数,.用循环程序来处理这个向题是比较容易的©al=l
a2=l
PRINTal,a2sINPUTWS;i=3tona3=al-Fa2PRINTa3,al=a2a2F&
NEXTiEND
【说明】设3个变最al,&1,：：点的值