算法设计与分析实验报告(中南民族大学)

院系：计算机科学学院专业：年级：课程名称：算法设计与分析基础班号：组号：指导教师：年月日组员学号姓名实验名称算法分析基础——给定一个非负整数n，计算第n个Fibonacci数实验室实验目的或要求一．实验目的1）理解递归算法和迭代算法的设计思想以及递归程序的调式技术2)握并应用递归算法和迭代算法效率的理论分析(前验分析)和经验分析(后验分析)方法；3)理解这样一个观点：不同的算法可以解决相同的问题，这些算法的解题思路不同，复杂程度不同，效率也不同；二．实验要求1）使用教材2.5节中介绍的迭代算法Fib(n),找出最大的n,使得第n个Fibonacci数不超过计算机所能表示的最大整数，并给出具体的执行时间；2）对于要求1),使用教材2.5节中介绍的递归算法F(n)进行计算,同样给出具体的执行时间，并同1)的执行时间进行比较；3）对于输入同样的非负整数n，比较上述两种算法基本操作的执行次数；4）对1)中的迭代算法进行改进，使得改进后的迭代算法其空间复杂度为Θ(1)；5）设计可供用户选择算法的交互式菜单(放在相应的主菜单下)。实验原理（算法基本思想）一．迭代算法求最大Fibonacci在数列中位置1.先利用迭代求得计算机能表示的最大数MaxUnsignedInt.unsignedlongintMaxUnsignedInt=1;while(MaxUnsignedInt*2+1!=MaxUnsignedInt){MaxUnsignedInt=MaxUnsignedInt*2+1;}2.从1起进行(n-1)+(n-2)=n迭代，直到条件(temp3temp)时发生溢出(及超过最大数)，退出循环。求得此时的迭代次数-1即为最大Fibonacci的位置。unsignedlongintn=MaxUnsignedInt;for(i=1;temp=n;i++)//temp=n{temp=temp1+temp2;if(temp3temp)//当temp3temp时，则发现temp发生溢出，结束计算break;temp3=temp;temp2=temp1;temp1=temp;}二．递归算法1.根据/0n=0f(n)=1n=1\f(n-1)+f(n-2)n=2进行递归调用求解。longFF(unsignedinttt)//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(){unsignedlongintMaxUnsignedInt,n,times,t=100;clock_tstart=clock();MaxUnsignedInt=1;while(MaxUnsignedInt*2+1!=MaxUnsignedInt){MaxUnsignedInt=MaxUnsignedInt*2+1;}cout时间消耗：clock()-startendl;n=MaxUnsignedInt;intchoose;boolend_this=true;while(end_this){cout************************************************************\n;cout1.输入一个你想要判断的数\n;cout2.判断从0到N的Fibonacci\n;cout3.计算机能判断的最大数\n;cout4.用递归计算你想要判断的数\n;cout5.结束\n;again:coutyouwantdo:;cinchoose;if(choose!=1&&choose!=2&&choose!=3&&choose!=4)//输入菜单检查{cout输入错误\n;gotoagain;}switch(choose){case1:{coutinputyournumber:;cint;start=clock();times=F(t);coutt是第times个Fibonacci数endl;cout时间消耗：clock()-startendl;break;}case2:{start=clock();F(t);cout时间消耗：clock()-startendl;break;}case3:{cout最大数是nendl;//times=F(n);start=clock();unsignedlonginttemp=1,temp1=0,temp2=1,temp3=temp;inti;for(i=1;temp=n;i++)//temp=n{temp=temp1+temp2;if(temp3temp)//当temp3temp时，则发现temp发生溢出，结束计算break;temp3=temp;temp2=temp1;temp1=temp;}coutn是第i-1个Fibonacci数endl;cout时间消耗：clock()-startendl;break;}case4:{start=clock();intx;coutYouwantdo:;cinx;times=FF(x);cout第x个Fibonacci数是timesendl;cout时间消耗：clock()-startendl;break;}case5:{end_this=false;break;}}}}intF(unsignedintuu){unsignedlonginttemp=0,temp1=0,temp2=1;inti;//if(uu==0||uu==1)//returnuu;for(i=1;i=uu;i++){temp=temp1+temp2;coutnumberiistempendl;if(temp=uu)returni;temp2=temp1;temp1=temp;}return0;}longFF(unsignedinttt)//usedigui{if(tt=1)returntt;elsereturnFF(tt-1)+FF(tt-2);}intfib(intn){doublegh5=sqrt((double)5);return(pow((1+gh5),n)-pow((1-gh5),n))/(pow((double)2,n)*gh5);}实验结果及分析1.求最大数2.递归法与迭代法性能比较递归迭代3.改进算法1.利用公式法对第n项Fibonacci数求解时可能会得出错误结果。主要原因是由于double类型的精度还不够，所以程序算出来的结果会有误差，要把公式展开计算。2.由于递归调用栈是一个费时的过程，通过递归法和迭代法的比较表明，虽然递归算法的代码更精简更有可读性，但是执行速度无法满足大数问题的求解。3.在当前计算机的空间较大的情况下，在一些速度较慢的问题中，空间换时间是一个比较周全的策略。实验名称分治法在数值问题中的应用——矩阵相乘问题实验室实验目的或要求一．实验题目设M1和M2是两个n×n的矩阵，设计算法计算M1×M2的乘积。二．实验目的1）提高应用蛮力法设计算法的技能；2）深刻理解并掌握分治法的设计思想；3）理解这样一个观点：用蛮力法设计的算法，一般来说，经过适度的努力后，都可以对其进行改进，以提高算法的效率。三．实验要求1）设计并实现用BF方法求解矩阵相乘问题的算法；2）设计并实现用DAC方法求解矩阵相乘问题的算法；3）以上两种算法的输入既可以手动输入，也可以自动生成；4）对上述两个算法进行时间复杂性分析，并设计实验程序验证分析结果；5）设计可供用户选择算法的交互式菜单(放在相应的主菜单下)。实验原理（算法基本思想）定义：若A=(aij),B=(bij)是n×n的方阵，则对i,j=1,2,…n，定义乘积C=A⋅B中的元素cij为：1.分块解法通常的做法是将矩阵进行分块相乘，如下图所示：二．Strassen解法分治法思想将问题实例划分为同一问题的几个较小的实例。对这些较小实例求解，通常使用递归方法，但在问题规模足够小时，也会使用另一种算法。如果有必要，合并这些问题的解，以得到原始问题的解。求解矩阵相乘的DAC算法，使用了strassen算法。DAC（A[]，B[]，n）{Ifn=2使用7次乘法的方法求得解ElseDivide（A）//把A分成4块Divide（B）//把B分成4块调用7次strassen算法求得解的4块合并这4块得到解并返回}伪代码Serial_StrassenMultiply(A,B,C){T1=A0+A3;T2=B0+B3;StrassenMultiply(T1,T2,M1);T1=A2+A3;StrassenMultiply(T1,B0,M2);T1=(B1-B3);StrassenMultiply(A0,T1,M3);T1=B2-B0;StrassenMultiply(A3,T1,M4);T1=A0+A1;StrassenMultiply(T1,B3,M5);T1=A2–A0;T2=B0+B1;StrassenMultiply(T1,T2,M6);T1=A1–A3;T2=B2+B3;StrassenMultiply(T1,T2,M7);C0=M1+M4-M5+M7C1=M3+M5C2=M2+M4C3=M1-M2+M3+M6}程序代码//矩阵相乘问题voidPrintIn(ArrayA,ArrayB){intn=A.n;inti,j;printf(请输入A数据：\n);for(i=0;in;i++)for(j=0;jn;j++)cinA.a[i*n+j];printf(请输入B数据：\n);for(i=0;in;i++)for(j=0;jn;j++)cinB.a[i*n+j];}voidRandomIn(ArrayA,ArrayB){intn=A.n;srand((unsigned)time(NULL));inti,j;for(i=0;in;i++)for(j=0;jn;j++)A.a[i*n+j]=rand()%10;for(i=0;in;i++)for(j=0;jn;j++)B.a[i*n+j]=rand()%10;}voidPrintOut(ArrayA){intn=A.n;inti,j;for(i=0;in;i++){for(j=0;jn;j++)coutA.a[i*n+j]'';printf(\n);}}voiddivide(Arrayd,Arrayd00,Arrayd01,Arrayd10,Arrayd11)/*分割矩阵*/{intn=d00.n;inti,j;for(i=0;in;i++){for(j=0;jn;j++){d00.a[n*i+j]=d.a[2*n*i+j];d01.a[n*i+j]=d.a[2*n*i+n+j];d10.a[n*i+j]=d.a[2*n*n+2*n*i+j];d11.a[n*i+j]=d.a[2*n*n+2*n*i+n+j];}}}Arraymerge(Arrayd00,Arrayd01,Arrayd10,Arrayd11){intn=d00.n;inti,j;Arrayd;d.a=(int*)malloc(sizeof(int)*(4*n*n));for(i=0;in;i++){for(j=0;jn;j++){d.a[2*n*i+j]=d00.a[n*i+j];d.a[2*n*i+n+j]=d01.a[n*i+j];d.a[2*n*n+2*n*i