斐波那契数列递归和迭代&循环链表队列初始化实验报告

第一篇：斐波那契数列递归和迭代&循环链表队列初始化实验报告

第一次实验实验报告

班级：2009211307 姓名：吕博文 学号：09211297 分工情况：个人一组 完成日期：11月5日

斐波那契数列递归和迭代算法

一、问题描述

分别写出下列函数的递归算法和迭代算法，并求出n=10时的函数值。Fib(n)= n

当n=0或n=1 Fib(n-2)+ Fib(n-1)当n>=2

二、算法思想

用递归算法求解时，若输入的n的值为0或1，根据问题描述中Fib(n)的递归定义，算法直接返回n作为输出结果。当输入的n的值大于等于2时，根据Fib(n)的递归定义，算法将调用自身计算Fib(n-2)和Fib(n-1)的值，然后返回二者的和。

用迭代算法求解时，先初始化Fib(0)和Fib(1)的值，用两个变量curValue和preValue存储，curValue存储较大的数值，preValue存储较小的数值。若输入的n的值为0或1，算法直接返回n。若输入的n的值大于等于2，循环n-1次，每次循环将curValue和preValue的值相加存入curValue中，并用preValue存储原来curValue的值，为下一次循环做好准备。最终的curValue的值即为Fib(n)的值。

三、设计描述

先提示输入n的值，然后调用递归算法计算Fib(n)，输出，再调用迭代算法计算Fib(n)，输出。

递归算法

int ShowFib_1(int n){

if(n == 0 || n == 1)//初始条件 return n;

else//不符合初始条件时，用递推关系计算 return ShowFib_1(n-2)+ ShowFib_1(n-1);}

迭代算法

int ShowFib_2(int n){ preValue = 0;curValue = 1;//设定第一、第二项的值作为初始条件

if(n == 0 || n == 1)//第一、第二项可直接输出结果 return n;else

{

for(i = 2;i <= n;i++)//其余各项从前往后逐项相加

{ temp = curValue;curValue = curValue + preValue;preValue = temp;

} returncurValue;

} }

四、源程序

#include using namespace std;

int ShowFib_1(int n);//定义递归函数 int ShowFib_2(int n);//定义迭代函数

int main(){ int n;

cout<< “N=?:”;cin>> n;

//递归算法

cout<< “用递归算法计算” <

//迭代算法

cout<< “用迭代算法计算” <

//递归算法

int ShowFib_1(int n){

if(n == 0 || n == 1)//判定初始条件 return n;else//

return ShowFib_1(n-2)+ ShowFib_1(n-1);}

//迭代算法

int ShowFib_2(int n){ intpreValue = 0, curValue = 1;//设定第一、第二项的值 if(n == 0 || n == 1)// return n;else

{

for(int i = 2;i <= n;i++)//其余项从前往后逐项相加

{ int temp;temp = curValue;curValue = curValue + preValue;preValue = temp;

} returncurValue;

} }

五、测试结果

N=40时利用递归求算时计算机反应速度较慢

N=10时

六、心得体会

在N=40时，等待递归算法算出结果时间较长，可见递归算法计算斐波那契数列的效率不高。但使用迭代算法则想法，可见虽然迭代算法的思路稍难于递归算法，但时间复杂度与空间复杂度均优于递归算法。故更应推荐迭代算法。

另外，本题难度低，过程中没什么问题，故无太多感想。

第二题

一、问题描述

假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点而不设头指针，试编写相应的队列初始化、入队列、出队列和判断队列状态的算法。

利用上述算法完成下面的各操作，并在每一操作后输出队列状态。

1)下列元素逐一入队：5,7,3,8,55 状态：5个元素

2)3个元素出队

状态：２个元素

3)再２个元素出队

状态：队空

4)再１个元素出队

状态：队空（指示下溢）

二、算法思想

主函数中新建一个队列的对象，然后调用其成员函数进行队列的操作。将5,7,3,8,55 入队→5,7,3出队→8,55出队→在队列为空时出队 每次操作后均输出当前队列状态。

三、设计描述

class Queue{

//建立一个队列类 public: Queue(){}

~Queue();

intInit();

//初始化队列 int Insert(int);

//入队 int Delete(int&);

//出队 intQState();

//判断状态 private:

typedefstruct node { int data;struct node *next;}Node;Node *rear;};

四、源程序

#include using namespace std;

class Queue { public: Queue(){} ~Queue();

intInit();//初始化队列

int Insert(int);//入队

int Delete(int&);//出队

intQState();//判断状态

private: typedefstruct node

{

int data;

struct node *next;}Node;Node *rear;};

int Queue::Init()//初始化 { rear=new Node;if(rear){

rear->data=-1;

rear->next=rear;

return 1;} return 0;}

int Queue::Insert(intelem)//入队 { Node * newd=new Node;

newd->data=elem;newd->next=rear->next;rear->next=newd;rear=newd;return 1;}

int Queue::Delete(int&elem)//出队 { if(rear==rear->next)

return 0;

Node *p=rear->next->next;elem=p->data;rear->next->next=p->next;if(p==rear)//删最后一个

rear=rear->next;free(p);return 1;

}

int Queue::QState()//判定状态 {

int i=0;Node *q=rear->next;

cout<<“队列状态:”<

cout<next->data<<“ ”;

q=q->next;

i++;} if(0==i)

cout<<“空”<

else

cout<

Queue::~Queue()//删除，如有未释放空间 { int i;if(rear)

} {

} if(rear->next==rear)free(rear);else { while(rear->next!=rear)

Delete(i);free(rear);} //主函数 int main(){ Queue DQ;intele;DQ.Init();DQ.QState();

cout<<“依次将5,7,3,8,55入队”<

5,7,3,8,55

cout<<“将5,7,3出队n”;system(“pause”);

if(DQ.Delete(ele))// 出队

cout<

if(DQ.Delete(ele))

cout<

if(DQ.Delete(ele))

cout<

DQ.QState();//当前状态 8,55 cout<<“再将8,55出队”<

system(“pause”);

if(DQ.Delete(ele))

cout<

cout<

cout<<“下一步将在空的队列里进行删除操作”<

if(DQ.Delete(ele))

cout<

} cout<<“队列已满，下溢”<

system(“pause”);

五、测试结果

六、心得体会

这个程序的实现关键在于类，类对于数据结构可以说是非常重要非常基础也是必不可少的一个杀手锏。在编这道题的过程中，最初的想法是设计一个程序可以实现入队、出队、上溢下溢提示，但考虑到这道题的具体要求，改为了程序自动将题目所要求出入队的元素进行操作，不过不影响核心算法核心思想的实现。

第二篇：斐波那契数列演讲稿

Speech 斐波那契数列在欧美可谓是尽人皆知，于是在电影这种通俗艺术中也时常出现，比如在风靡一时的《达芬奇密码》里它就作为一个重要的符号和情节线索出现，在《魔法玩具城》里又是在店主招聘会计时随口问的问题。可见此数列就像黄金分割一样流行。可是虽说叫得上名，多数人也就背过前几个数，并没有深入理解研究。

另外，观察延龄草、野玫瑰、南美血根草、大波斯菊、金凤花、耧斗菜、百合花、蝴蝶花的花瓣，可以发现它们花瓣数目具有斐波那契数：3、5、8、13、21、……

斐波那契数还可以在植物的叶、枝、茎等排列中发现。例如，在树木的枝干上选一片叶子，记其为数0，然后依序点数叶子（假定没有折损），直到到达与那息叶子正对的位置，则其间的叶子数多半是斐波那契数。叶子从一个位置到达下一个正对的位置称为一个循回。叶子在一个循回中旋转的圈数也是斐波那契数。在一个循回中叶子数与叶子旋转圈数的比称为叶序（源自希腊词，意即叶子的排列）比。多数的叶序比呈现为斐波那契数的比。对于许多植物来说，每片叶子从中轴附近生长出来，为了在生长的过程中一直都能最佳地利用空间（要考虑到叶子是一片一片逐渐地生长出来，而不是一下子同时出现的），每片叶子和前一片叶子之间的角度应该是222.5度，这个角度称为“黄金角度”，因为它和整个圆周360度之比是黄金分割数0.618033989……的倒数，而这种生长方式就决定了斐波那契螺旋的产生。

斐波那契螺旋：具有13条顺时针旋转和21条逆时针旋转的螺旋的蓟的头部

斐波那契数有时也称松果数，因为连续的斐波那契数会出现在松果的左和右的两种螺旋形走向的数目之中。这种情况在向日葵的种子盘中也会看到。向日葵的种子排列形成的斐波那契螺旋有时能达到89，甚至144条。

菠萝是又一种可以检验斐波那契数的植物。对于菠萝，我们可以去数一下它表面上六角形鳞片所形成的螺旋线数。

（斐波那契数列在自然界中的出现是如此地频繁，这些植物懂得斐波那契数列吗？）人们深信这不是偶然的。应该并非如此，它们只是按照自然的规律才进化成这样。这似乎是植物排列种子的“优化方式”，它能使所有种子具有差不多的大小却又疏密得当，不至于在圆心处挤了太多的种子而在圆周处却又稀稀拉拉。

其实生活中很多事情也就是这样的，一切都有其规律性，冥冥中一切自有安排！是啊！《触摸未来》中的很多情节似乎离我们现实生活很近很近，因为这就是真实，就是真理，这部美剧正在代表这个时代的人们去探索和更新我们的知识。世界有着无数的关联，自有它的定数，自有它的规律！只要我们尊重规律，我们就可以避免受伤！

2012年在古代玛雅历上是这个纪元的最后一年，世界上有1/7的人都认为是世界末日，其实我想，人类为了自己的目的一直在不断伤害着我们的地球母亲，着或许是古老文化对我们的一种警告如果我们现在学会懂得去尊重地球的规律，我们还可以继续看见未来升起的阳光！

第三篇：《斐波那契数列》教学反思

根据上午说课后其他老师的建议，我做了修改：

（一）引入部分简化，斐波那契数列的学习同样也运用了化难为易的思想，在刘**老师的授课《斐波那契数列》中多次提到难易的转化，我们的学生也认真地进行了这节《斐波那契数列》的学习，给我们的学生试课可以这样引入：

孩子们，我们在学习《斐波那契数列》时是怎么发现小兔子数量的规律呢？对，化难为易，我们可以用化难为易的方法解决很多问题，那老师请你们来试试连线游戏，在平面上有100个点，这些点能连成多少条线段？

学生回答不上来时，教师指导：100个点连线有点多有点难，老子说：“天下难事做于易。”我们就从最简单的两个点开始研究，用数学的思考方法解决点连线的问题。

这样的引入斐波那契数列就不只是欣赏，而是数学思考方法的延续。

可是，不知道其他学校的教师能否重视教材65页的阅读资料《斐波那契数列》，所以还是没底。

（二）探究过程的连线过程又做了一遍，原来用了四张幻灯片而且一直一闪而过，感觉有点杂有点多，我修改用一个表格一张幻灯片呈现，这样就不觉得繁杂。这点怪我有点懒了，用别人现成的，所以今天又用了半个下午修改了一遍。

第四篇：斐波那契数列通项公式的证明

斐波那契数列：1、1、2、3、5、8、13、21、34……它的通项公式为：an1[(15)n(1)n]

1解得证明：令anan1(an1an2)(n3)则有1





121

或





121

故有

(1)

an

1151111an1(an1an2)或(2)anan1(an1an2)222222

anan1

1an111515，因为n3故数列{an}是以aaa1为首项，n122221an

2(Ⅰ)由（1）得

以

1115n215

为公比的等比数列，所以，anan1(a2a1)()由a1a21得2222

1an12

an

11n1anan11 ()两边同除以(15)n得：221n115n115

()()2222

即

an(1n)2



1an1

11n1

()2



anan115移项得1515(n3)则由



221n11n1

()()22

1anan1155所以{an得，}是以2[]k

5151n15551n115n

()()()1

2221a2(152)2



1an

为首项为公比的等比数列。故511(2

)n

a21n2

[]()551521()2

a2515n2，由(1)2(2)2化简可得 得a(15)n{[]()}n

2152551215

()2

an

15n15n)()](n3)(*)验证可得，当n=

1、n=2时，a1a21故斐波那契数列中，225[（*

对于nN，(*)式都成立。

*

(Ⅱ)同理，由(2)an1an11(an11an2)也可得斐波那契数列中，（*)式对于nN都成立

222

所以，斐波那契数列的通项公式即为：an

15n15n)()] 225[（木鱼石整理

第五篇：基于信息技术的数学探究课题设计一例——“斐波那契数列”教学课例

桂林师范高等专科学校 蒋晓云 李政

【关键词】斐波那契数列 信息技术探究

【文献编码】doi:10.3969/j．issn.0450-9889(B)．2011.02.021 《普通高中数学课程标准》设置了数学建模和数学探究的学习活动。计算机技术和数学软件的飞速发展使人们对“数学课程与信息技术的整合”有了更深刻的理解，我们可以且应该用计算机“做数学”、“表现数学”，帮助学生学习数学、理解数学、欣赏数学，让学生在已有的认知结构基础上去发现和建构新知识。这样的数学实验提供了一种全新的数学教学手段和模式，受到了大中小学广泛的关注。

人民教育出版社和江苏教育出版社出版的课标教材都介绍了斐波那契数列；人民教育出版社教材中的研究性学习课题“上楼问题的数列模型”是一个与斐波那契数列密切相关的经典名题。我们选择斐波那契数列作为高中二年级数学探究性学习课题，设计了一节数学探究实验展示课。

一、教学目标

1．知识方面：使学生理解斐波那契数列，掌握斐波那契数列通项公式的求法，能应用斐波那契数列解决日常生活中的一些问题。

2．能力方面：培养学生的观察能力、发现能力、解决实际问题的能力和审美意识。3．品质素养方面：使学生体会数学来源于生活的大众数学思想，培养学生的实践能力和应用意识。

二、重点难点

重点：斐波那契数列、斐波那契数列的应用。

难点：斐波那契数列通项公式的求法，将实际问题转化为数学问题。

三、教学手段

多媒体辅助教学。

四、教学过程

（一）创设情境

今天这节课我们来看一个有趣的问题，它最初是由一名意大利数学家斐波那契在13世纪初提出的：兔子出生两个月后就能生小兔，若每次不多不少恰好生一对（一雌一雄），假如养了初生的小兔一对，试问第八个月共有多少对兔子（若生下的小兔都不死的话）? 先让学生自由讨论，教师再辅以课件分析。

我们用●表示一对大兔，用〇表示一对小兔，则可逐月统计得到每月的兔子对数：

如此推算下去，我们不难得出下面结果：

∴第八个月共有21对兔子。

如果我们用Un表示第n月后的兔子数，则有： {Un}:1,2,3,5,8,13,2l,„

这个数列被称为斐波那契数列，我们这节课就来研究这个有趣的数列问题。

（二）提出问题

问题1上述问题，两年后有多少对兔子？三年后、五年呢？

学生发现继续用上面这种方法来推算，似乎有些“笨”，而且越往后越复杂。学生自然会想有无简单的办法推算。

问题2请观察斐波那契数列，你发现了什么规律？

学生讨论后，不难得出该数列中各项有如下递推关系： 教师在鼓励学生的同时指出：在当时，这个简单的递推关系却是在斐氏死后近四百年才由一名叫奇拉特的数学家发现的。

由于这一发现，生小兔问题引起人们的极大兴趣。最重要的是，计算这列数给我们带来一定的方便。我们可以轻而易举地计算两年后、三年后、五年后„„的兔子对数。

问题3若要计算十年、二十年以后的兔子数，我们就不得不计算它前面所有项的兔子对数，用递推关系，是不是又出现了繁琐？这时我们迫切地想知道：若已知月份数，能够马上计算出兔子对数吗？

学生马上想到要推导斐波那契数列的通项公式。

（三）数学实验

【数学实验是指学生按照教师提出的要求，亲自用电脑完成相应的实验，努力去发现与所研究问题相关的一些数据中反映出的规律性，对实验结果做出清楚的描述，它是整个教学过程中的核心环节。作为中学数学实验工具的常用数学软件有几何画板、Mathematica、Math-CAD、EXCEL等。

请同学们用Mathematica数学软件，在电脑上完成相应的实验：

计算出斐波那契数列的前20项并作出其散点图，观察斐波那契数列的图像，连接相邻的点作折线图。

问题4仔细观察图像，它与哪一种已知函数图像很近似？

学生发现：fibonacci[i]随i增加的速度很快，猜想是按指数式增长。

也有学生进一步取对数后再观察，可以发现图像近似一条直线。

（四）归纳猜想

【学生在理解了学习课题后，通过直观观察、实验分析、数学灵感等各种途径和方式，根据已有的信息或新得到的信息，提出猜想。本环节是整个教学过程中的关键环节，是数学实验的高潮阶段，同时也是培养学生合情推理能力的过程。】

学生通过实验、观察可得出如下猜想：

猜想1：Un=an(2)并且由递推关系Un=Un-1+Un-2得出an=an-1+an-2,，即a2=a+l，解出两根a1=(1+√5)/2, a2=(1-√5)/2 无论Un=a1还是Un=a2n，数列Un都能满足递推关系Un=Un-1+Un-2。

但有学生马上指出，无论a=a1或a=a2，Un=an都不能满足u1=u2=1。

学生讨论后，有学生注意到了任意两个满足(1)式中的的数列的线性组合仍能满足(1)式中的递推关系，于是提出： 猜想2：Un=cla1n+c2a2n(3)并用用条件u1=u2=1来确定系数C1和C2，即解方程组同学们把这个任务交给Mathematica来完成，解出c1=l／√5，C2=-1／√5。由此得到斐波那契数列的通项公式：

这是一个耐人寻味的等式：等式左边是正整数，右边却是由无理数来表达的。

有学生用实验验证了这个斐波那契数列的通项公式。

（五）推理论证

【提出猜想之后，需要通过演绎推理的方法来证明猜想的正确性或通过举出反例的方法来否定猜想。验证猜想的过程实际上是培养学生求实的学习态度和严谨的逻辑推理能力的过程。这是数学实验不可缺少的环节，是获得正确结论的关键步骤。】

要求学生用数学归纳法证明通项公式。

（六）拓展应用

斐波那契数列是一个十分有趣的数列，在自然科学和数学领域中有着非常广泛的应用，如树枝生长问题、蜜蜂进蜂房问题、上楼方式问题„„许许多多的事物中都隐含着斐波那契数。启发学生善于将这些实际问题转化成数学问题。

应用1．树枝生长问题

波兰数学家史坦因豪斯的名著《数学万花筒》中有这样一个问题：一棵树一年后长出一条新枝，新枝隔一年后成为老枝，老枝便可每年长出一条新枝。如此下去，十年后树枝将有多少?（由学生回答，这个问题只是斐波那契数列问题的简单变化）

应用2．蜜蜂进蜂房问题

一次蜜蜂从蜂房A出发，想爬到n号蜂房，但只允许它自左向右（不许反方向倒走），则它爬到各号蜂房的路线数各是多少？

学生探讨，老师再进行分析、启发：

设蜜蜂从蜂房A出发，爬到i(i=1，2，„，n)号蜂房的路线数为ui，我们可将爬到n号蜂房的方式分为两类：一类是不经过n一l号蜂房而直接从n-2号蜂房进入第n号蜂房，路线数有un-2条；另一类是经过n-l号蜂房进入第n号蜂房，路线数有un-1条，所以un=un-1+un-2(ui=l，u2=2)。

应用3 反问兔子问题

兔子出生两个月后就能生小兔，若每次不多不少恰好生一对（一雌一雄），假如养了初生的小兔一对，试问第几个月可以得到360对兔子？(1)用递推公式

通过利用循环结构编写计算机程序，运行后即可得出结果为14。(2)作为斐波那契数列通项公式的应用。

拓展1．上楼方式问题

上楼梯时，若允许每次跨一级或两级，那么楼梯级数为12时上楼的方式数是多少？（数学竞赛题）一般地，楼梯级数为n时上楼的方式数是多少？（这个问题等价于斐波那契数列问题）

若允许每次跨一级或两级或三级，那么对于楼梯级数为n时的上楼方式数是多少？

（可建立上楼问题递推数列模型：fn+3=fn+2+fn+1+fn，以及f1=l ,f2=2,f3=4，利用循环结构编写一个计算机程序计算）。

拓展2．杨辉三角形与斐波那契数列

把杨辉三角形中的数据排列在表格中，自左下至右上斜线相加。直觉告诉我们，和数列可能是斐波那契数列。

学生通过观察和归纳得出了斐波那契数列通项的组合表达式的猜想：

（其中k=[n/2]是不超过n的最大整数）。这一猜想的发现使整个教学过程又达到了一个高潮，这说明学生已经有了一定的洞察力和数学灵感。

拓展3．黄金分割：(√5-1)/2=0.618 斐波那契数列和黄金分割数有很密切的联系，到底有哪些联系呢？

拓展4．斐波那契螺旋

由正方形可以构成一系列的长方形，其边长为斐波那契数列的连续项。在正方形内绘出一个圆的1/4，就可以得到一条螺线，这样的螺线被称为斐波那契螺旋。

展示从网上下载的丰富资源，同时指出：斐波那契螺旋在自然界中随处可见，如蜘蛛网、向日葵、水流的旋涡、蜗牛壳的螺纹以及星系内星球的分布等。【教学反思】

运用现代教育技术能向学生提供丰富多彩的教学内容，使教学内容形象化、生活化，创设良好的问题情境，拓宽学生的视野，激发学生的学习兴趣，增进学生对数学的理解，鼓励学生探究，最终提高数学教学的质量。

基于计算机信息技术的数学实验课的引入，给高中数学课注入了活力，更能给予学生一个“完整的数学”。教师使用计算机来辅助完成教学任务，通过数学实验来降低问题的难度，不用太多的语言，而是让学生自己动手实验、观察发现、猜想验证、合情推理、得出结论。

本节课教师从学生的生活经验和已有的知识背景出发，向他们提供了充分地从事数学活动和交流的机会，在分析和解决生兔子问题、树枝生长问题、上楼方式问题、蜜蜂进蜂房问题时，学生表现出了极大的热情和兴趣。

新教学模式呼唤高素质的教师，数学教师要能像使用粉笔、黑板、常规教具一样使用计算机来辅助完成教学任务，充分发挥计算机在数学实验教学中的优势。目前教师队伍可能难以适应发展的要求，要提高教师信息技术应用能力，才能更好地使数学实验课进人中学数学课堂。