欢迎来到天天文库
浏览记录
ID:15328420
大小:511.00 KB
页数:28页
时间:2018-08-02
《算法设计与分析实验报告_肖志强》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、院系:计算机科学学院专业:计算机科学与技术年级:2012课程名称:算法设计与分析基础班号:1201组号:1指导教师:邢光林2015年5月25日组员学号姓名2012213508蒲灿2012213510肖志强2012213514邹治东实验名称算法分析基础——给定一个非负整数n,计算第n个Fibonacci数实验室9#206实验目的或要求一.实验目的1)理解递归算法和迭代算法的设计思想以及递归程序的调式技术2)握并应用递归算法和迭代算法效率的理论分析(前验分析)和经验分析(后验分析)方法;3)理解这样一个观点:不同的算
2、法可以解决相同的问题,这些算法的解题思路不同,复杂程度不同,效率也不同;二.实验要求1)使用教材2.5节中介绍的迭代算法Fib(n),找出最大的n,使得第n个Fibonacci数不超过计算机所能表示的最大整数,并给出具体的执行时间;2)对于要求1),使用教材2.5节中介绍的递归算法F(n)进行计算,同样给出具体的执行时间,并同1)的执行时间进行比较;3)对于输入同样的非负整数n,比较上述两种算法基本操作的执行次数;4)对1)中的迭代算法进行改进,使得改进后的迭代算法其空间复杂度为Θ(1);5)设计可供用户选择算法
3、的交互式菜单(放在相应的主菜单下)。实验原理(算法基本思想)一.迭代算法求最大Fibonacci在数列中位置1.先利用迭代求得计算机能表示的最大数MaxUnsignedInt.unsignedlongintMaxUnsignedInt=1;while(MaxUnsignedInt*2+1!=MaxUnsignedInt){MaxUnsignedInt=MaxUnsignedInt*2+1;}2.从1起进行(n-1)+(n-2)=n迭代,直到条件(temp3>temp)时发生溢出(及超过最大数),退出循环。求得此时
4、的迭代次数-1即为最大Fibonacci的位置。unsignedlongintn=MaxUnsignedInt;for(i=1;temp<=n;i++)//temp<=n{temp=temp1+temp2;if(temp3>temp)//当temp3>temp时,则发现temp发生溢出,结束计算break;temp3=temp;temp2=temp1;temp1=temp;}二.递归算法1.根据/0n=0f(n)=1n=1f(n-1)+f(n-2)n=2进行递归调用求解。longFF(unsignedinttt
5、)//usedigui{if(tt<=1)returntt;elsereturnFF(tt-1)+FF(tt-2);}三.改进空间复杂度为Θ(1)。利用公式:F(n)=(1/√5)*{[(1+√5)/2]^n-[(1-√5)/2]^n}intfib(intn){doublegh5=sqrt((double)5);return(pow((1+gh5),n)-pow((1-gh5),n))/(pow((double)2,n)*gh5);}程序代码voidfibo(){unsignedlongintMaxUnsigne
6、dInt,n,times,t=100;clock_tstart=clock();MaxUnsignedInt=1;while(MaxUnsignedInt*2+1!=MaxUnsignedInt){MaxUnsignedInt=MaxUnsignedInt*2+1;}cout<<"时间消耗:"<7、**************************************";cout<<"a.迭代算法";cout<<"b递归算法";cout<<"c.退出";again:cout<<"请选择输入:";cin>>choose;if(choose!=‘a’&&choose!=’b’&&choose!=’c’)//输入菜单检查{cout<<"输入错误";gotoagain;}switch(choose){casea:{cout<<"inputyournumber:";cin>>t;start=8、clock();times=F(t);cout<
7、**************************************";cout<<"a.迭代算法";cout<<"b递归算法";cout<<"c.退出";again:cout<<"请选择输入:";cin>>choose;if(choose!=‘a’&&choose!=’b’&&choose!=’c’)//输入菜单检查{cout<<"输入错误";gotoagain;}switch(choose){casea:{cout<<"inputyournumber:";cin>>t;start=
8、clock();times=F(t);cout<
此文档下载收益归作者所有