算法设计实验报告

院系：计算机科学学院专业：计算机科学与技术年级：级课程名称：算法设计与分析基础班号：组号：3指导教师：邢光林12月30日组员学号姓名试验名称算法试验整体框架构建试验室9#205实验目或要求1.试验题目算法试验主菜单设计。2．试验目标⑴熟悉试验环境VC＋＋6.0；⑵复习C、C++语言以及数据结构课程相关知识，实现课程间平滑过分；3.试验要求1）设计主菜单能够是图形模式，也能够是控制台模式。以控制台为例，主菜单大致以下： －－－－－－－－－－－－－－－－－－－－－－－－－ 《算法设计与分析》试验 －－－－－－－－－－－－－－－－－－－－－－－－－算法分析基础——Fibonacci序列问题分治法在数值问题中应用——最近点对问题减治法在组合问题中应用——8枚硬币问题变治法在排序问题中应用——堆排序问题动态规划法在图问题中应用——全源最短路径问题 99. 退出本试验 －－－－－－－－－－－－－－－－－－－－－－－－－请输入您所要执行操作（1，2，3，4，5，99）：2）点击操作后进入对应试验项目或是对应项目标下一级菜单；3）能够重复执行，直到退出试验。程序代码voidmenu();intmain(){FibonaccifibonacciImpl;HeapsortheapsortImpl;MartrixmartrixImpl;ThecointhecoinImpl; intchose; menu(); cin>>chose; while(chose!=99) { switch(chose) { case1:{fibonacciImpl.fib1();cout<<endl;fibonacciImpl.fib2();break;} case2:{martrixImpl.martrix();break;} case3:{thecoinImpl.Fake_coin();break;} case4:{heapsortImpl.heapsort();break;} case5:{break;} default:cout<<"请按序号输入操作"<<endl; } menu(); cin>>chose; } return0;}voidmenu(){ cout<<"---------------------------------------"<<endl; cout<<"《《算法设计与分析》》试验"<<endl; cout<<"---------------------------------------"<<endl; cout<<"1.算法分析基础——Fibonacci序列问题"<<endl; cout<<"2.分治法在数值问题中应用——矩阵相乘问题"<<endl; cout<<"3.减治法在组合问题中应用——8枚硬币问题"<<endl; cout<<"4.变治法在排序问题中应用——堆排序问题"<<endl; cout<<"5.动态规划法在图问题中应用——全源最短路径问题"<<endl; cout<<"99.退出本试验"<<endl;}实验结果及分析试验名称算法分析基础——Fibonacci序列问题试验室9#205实验目或要求试验题目给定一个非负整数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）设计可供用户选择算法交互式菜单(放在对应主菜单下)。实验原理（算法基本思想）1、递归法基本思想递归就是定义一个函数，让它自己调用自己。Fib（intn）//输入整数n，输出第n个斐波那契数{if(n=0)return0;Elseif(n=1)return1;ElsereturnFib(n-1)+Fib(n-2)}2、迭代法这种方法相对于递归法来说在时间复杂度上减小了不少，但代码相对就要复杂些了。Fib（intn）//输入整数n，输出第n个斐波那契数{if(n=0)return0;Elseif(n=1)return1;ElseF0←0;F1←1;for(i=2;i<n-2;i++){F2=f1+f0;//f1表示当前值F0←F1F1←F2;}ReturnF2;}程序代码//Fibonacci数列#ifndefFINBONACCI_H//头文件#defineFINBONACCI_HclassFibonacci{public: doublefibonacci(inti,int&count); //计算fibonacci intfib2(); intfib1();};#endifintFibonacci::fib2(){ inti=1; doublefib=0; intcount; doublex=INT_MAX; while(fib<x) { i++; count=1; fib=fibonacci(i,count); cout<<i<<""<<fib<<endl; } cout<<"使用迭代算法时"<<endl; cout<<"第"<<i<<"会超出INT所能表示最大值"<<endl; cout<<"总共进行了"<<count<<"次操作"<<endl; return0;}intFibonacci::fib1(){ doublefib=0; doublea=0; doubleb=1; intcount=0; doublex=INT_MAX; inti; for(i=1;fib<x;i++) { fib=a+b; a=b; b=fib; count++; } i--; cout<<"使用迭代算法时"<<endl; cout<<"第"<<i<<"会超出INT表示值"<<endl; cout<<"共做"<<count<<"次操作"<<endl; return0;}doubleFibonacci::fibonacci(inti,int&count){ count++; if(i<=1)return1; return(fibonacci(i-1,count)+fibonacci(i-2,count));}实验结果及分析经过比较两种方法求Fibonacci数列所用时间，能够发觉迭代法效率显著高于递归法。同时也明白了不一样算法能够处理相同问题，这些算法解题思绪不一样，复杂程度不一样，效率也不一样。试验名称分治法在数值问题中应用——矩阵相乘问题试验室9#205实验目或要求试验题目设M1和M2是两个n×n矩阵，设计算法计算M1×M2乘积。试验目标1）提升应用蛮力法设计算法技能；2）深刻了解并掌握分治法设计思想；3）了解这么一个观点：用蛮力法设计算法，通常来说，经过适度努力后，都能够对其进行改进，以提升算法效率。试验要求1）设计并实现用BF方法求解矩阵相乘问题算法；2）设计并实现用DAC方法求解矩阵相乘问题算法；3）以上两种算法输入既能够手动输入，也能够自动生成；4）对上述两个算法进行时间复杂性分析，并设计试验程序验证分析结果；5）设计可供用户选择算法交互式菜单(放在对应主菜单下)。实验原理（算法基本思想）1）蛮力法求解蛮力法比较简单，直接使用矩阵相乘公式计算矩阵每行每列值，很轻易就能得出答案2）分治法求解分治法思想将问题实例划分为同一问题几个较小实例。对这些较小实例求解，通常使用递归方法，但在问题规模足够小时，也会使用另一个算法。假如有必要，合并这些问题解，以得到原始问题解。求解矩阵相乘DAC算法，使用了strassen算法。DAC（A[]，B[]，n）{Ifn=2使用7次乘法方法求得解ElseDivide（A）//把A分成4块Divide（B）//把B分成4块调用7次strassen算法求得解4块合并这4块得到解并返回}程序代码//矩阵相乘问题#ifndefMARTRIX_H#defineMARTRIX_HstructTSMartrix{ intdata[100][100]; intmu;//矩阵行数 intnu;//矩阵列数};classMartrix{ public: voidmartrix(); //随机生成一个矩阵 voidRand_CreateSMartrix(structTSMartrix&M); //输出矩阵到控制台 voidOutputSMartrix(structTSMartrixM); //分治法--两个矩阵相乘 voidDAC_MultSMatrix(structTSMartrixM,structTSMartrixN,structTSMartrix&Q); //分割矩阵 voiddivide(structTSMartrixM,structTSMartrix&M00,structTSMartrix&M01,structTSMartrix&M10,structTSMartrix&M11); //合并矩阵 voidmerge(structTSMartrix&Q,structTSMartrixM00,structTSMartrixM01,structTSMartrixM10,structTSMartrixM11); //矩阵相加 structTSMartrixAddSMatrix(structTSMartrixM,structTSMartrixN); //矩阵相减 structTSMartrixSubSMatrix(structTSMartrixM,structTSMartrixN); private: structTSMartrixM00,M01,M10,M11; structTSMartrixN00,N01,N10,N11; structTSMartrixQ00,Q01,Q10,Q11; structTSMartrixs1,s2,s3,s4,s5,s6,s7;};#endif voidMartrix::martrix(){longstart,end; structTSMartrixM,N,Q; do { Rand_CreateSMartrix(M); Rand_CreateSMartrix(N); if(M.mu!=N.mu||M.mu!=M.nu||N.mu!=N.nu) printf("两个矩阵不一样维，无法用分治法!!!\n"); }while(M.nu!=N.mu||M.mu!=M.nu||N.mu!=N.nu); Q.mu=M.mu;Q.nu=M.mu;start=clock(); DAC_MultSMatrix(M,N,Q); end=clock(); printf("矩阵M：\n"); OutputSMartrix(M); printf("矩阵N：\n"); OutputSMartrix(N); printf("矩阵M*N：\n"); OutputSMartrix(Q); printf("历时%ld毫秒\n",end-start);}//随机生成一个矩阵voidMartrix::Rand_CreateSMartrix(structTSMartrix&M){ inti,j; printf("请输入矩阵行数，列数："); scanf("%d%d",&M.mu,&M.nu); srand((unsigned)time(NULL)); for(i=0;i<M.mu;i++) for(j=0;j<M.nu;j++) M.data[i][j]=rand()%10; printf("生成成功!\n");}//输出矩阵voidMartrix::OutputSMartrix(structTSMartrixM){ inti,j;for(i=0;i<M.mu;i++) { for(j=0;j<M.nu;j++) printf("%-5d",M.data[i][j]); puts("\n"); }}//分治法--两个矩阵相乘voidMartrix::DAC_MultSMatrix(structTSMartrixM,structTSMartrixN,structTSMartrix&Q){intn=M.mu; if(n==2) { intm1,m2,m3,m4,m5,m6,m7; m1=(M.data[0][0]+M.data[1][1])*(N.data[0][0]+N.data[1][1]); m2=(M.data[1][0]+M.data[1][1])*N.data[0][0]; m3=M.data[0][0]*(N.data[0][1]-N.data[1][1]); m4=M.data[1][1]*(N.data[1][0]-N.data[0][0]); m5=(M.data[0][0]+M.data[0][1])*N.data[1][1]; m6=(M.data[1][0]-M.data[0][0])*(N.data[0][0]+N.data[0][1]); m7=(M.data[0][1]-M.data[1][1])*(N.data[1][0]+N.data[1][1]);Q.data[0][0]=m1+m4-m5+m7; Q.data[0][1]=m3+m5; Q.data[1][0]=m2+m4; Q.data[1][1]=m1+m3-m2+m6; } else { n=n/2; M00.mu=M01.mu=M10.mu=M11.mu=M00.nu=M01.nu=M10.nu=M11.nu=N00.mu=N01.mu=N10.mu=N11.mu=N00.nu=N01.nu=N10.nu=N11.nu=n; s1.mu=s1.nu=s2.mu=s2.nu=s3.mu=s3.nu=s4.mu=s4.nu=s5.mu=s5.nu=s6.mu=s6.nu=s7.mu=s7.nu=n; divide(M,M00,M01,M10,M11); divide(N,N00,N01,N10,N11); DAC_MultSMatrix(AddSMatrix(M00,M11),AddSMatrix(N00,N11),s1); DAC_MultSMatrix(AddSMatrix(M10,M11),N00,s2); DAC_MultSMatrix(M00,SubSMatrix(N01,N11),s3); DAC_MultSMatrix(M11,SubSMatrix(N10,N00),s4); DAC_MultSMatrix(AddSMatrix(M00,M01),N11,s5); DAC_MultSMatrix(SubSMatrix(M10,M00),AddSMatrix(N00,N01),s6); DAC_MultSMatrix(SubSMatrix(M01,M11),AddSMatrix(N10,N11),s7); Q00=AddSMatrix(s1,AddSMatrix(s4,SubSMatrix(s7,s5))); Q01=AddSMatrix(s3,s5); Q10=AddSMatrix(s2,s4); Q11=AddSMatrix(s1,AddSMatrix(s3,SubSMatrix(s6,s2))); merge(Q,Q00,Q01,Q10,Q11); }}//分割矩阵voidMartrix::divide(structTSMartrixM,structTSMartrix&M00,structTSMartrix&M01,structTSMartrix&M10,structTSMartrix&M11){ intn=M00.mu; inti,j; for(i=0;i<n;i++) for(j=0;j<n;j++) { M00.data[i][j]=M.data[i][j]; M01.data[i][j]=M.data[i][n+j]; M10.data[i][j]=M.data[n+i][j]; M11.data[i][j]=M.data[n+i][j+n]; }}//合并矩阵voidMartrix::merge(structTSMartrix&Q,structTSMartrixM00,structTSMartrixM01,structTSMartrixM10,structTSMartrixM11){ intn=M00.mu; inti,j; for(i=0;i<n;i++) for(j=0;j<n;j++) { Q.data[i][j]=M00.data[i][j]; Q.data[i][j+n]=M01.data[i][j]; Q.data[i+n][j]=M10.data[i][j]; Q.data[i+n][j+n]=M11.data[i][j]; }}//矩阵相加structMartrix::TSMartrixAddSMatrix(structTSMartrixM,structTSMartrixN){ structTSMartrixQ; intn=M.mu; inti,j; Q.mu=Q.nu=n; for(i=0;i<n;i++) for(j=0;j<n;j++) Q.data[i][j]=M.data[i][j]+N.data[i][j];returnQ;}//矩阵相减structMartrix::TSMartrixSubSMatrix(structTSMartrixM,structTSMartrixN){ structTSMartrixQ; intn=M.mu; inti,j; Q.mu=Q.nu=n; for(i=0;i<n;i++) for(j=0;j<n;j++) Q.data[i][j]=M.data[i][j]-N.data[i][j];returnQ;}实验结果及分析经过这个试验，我明白了蛮力法几乎能够处理全部问题，不过算法效率不高。对蛮力法进行改进，经过适当努力后，算法效率能够得到提升试验名称减治法在组合问题中应用——8枚硬币问题试验室9#205实验目或要求试验题目在8枚外观相同硬币中，有一枚是假币，而且已知假币与真币重量不一样，但不知道假币与真币相比较轻还是较重。能够经过一架天平来任意比较两组硬币，设计一个高效算法来检测这枚假币。试验目标1）深刻了解并掌握减治法设计思想并了解它与分治法区分；2）提升应用减治法设计算法技能。3）了解这么一个观点：建立正角模型对于问题求解是非常主要。试验要求1）设计减治算法实现8枚硬币问题；2）设计试验程序，考查用减治技术设计算法是否高效；3）扩展算法，使之能处理n枚硬币中有一枚假币问题。实验原理（算法基本思想）减治法主要有三种变种减去一个常量减去一个常量因子减可变规模与分治法区分：分治法把实例分为几部分分别求解减治法把实例规模减为一个更小实例求解A（n）//输入硬币个数n，要求必须有假币且已知假币只有1个（假设更重）{ifn=1,这枚就是假币Elseifn=2，较重那枚是假币Else把n个硬币分为3份，2份相等，另一份与这2份相差个数尽可能小称2份个数相等If这2份重量相等，假币在第3堆中，对第3堆使用该算法Else在较重那堆中，对该堆硬币使用该算法}程序代码//假币问题#ifndefTHECOIN_H#defineTHECOIN_H //用减治法处理假币问题classThecoin{public: voidFake_coin(); intFake_coin_DC(intarray[],doublen,intnum);private: intflag;};#endifvoidThecoin::Fake_coin(){ intn,array[100]; printf("输入硬币个数:"); scanf("%d",&n); flag=n; for(inti=0;i<n;i++) {printf("输入第%d硬币重量:",i+1); scanf("%d",&array[i]); }Fake_coin_DC(array,n,0);}intThecoin::Fake_coin_DC(intarray[],doublen,intnum){if(n>=4){ doublekey;inti=0,k=0,m=0,u=0;key=ceil(n/3);for(i=num;i<=num+key-1;i++)//3分k=k+array[i];for(i;i<=num+2*key-1;i++)m=m+array[i];for(i;i<=num+n-1;i++)u=+array[i];if(abs(k-m)>0) { Fake_coin_DC(array,key,num); Fake_coin_DC(array,key,num+key); }else Fake_coin_DC(array,n-num-2*key,num+2*key); }else{if(n==3){ if(array[num]!=array[num+1]) { if(abs(array[num]-array[num+2]>0)) {printf("第%d枚是假币",num+1);d(num+1,array);} else{printf("第%d枚是假币",num+2);d(num+2,array);} } else if(array[num]!=array[num+2]) {printf("第%d枚是假币",num+3);d(num+3,array);}}if(n==2) { if(abs(array[num]-array[num+1])>0) { if(num==0) {if(abs(array[0]-array[2])>0) {printf("第%d枚是假币",num+1);d(num+1,array);} else {printf("第%d枚是假币",num+2);d(num+2,array);} } if(num+1==flag-1) { if(abs(array[num-1]-array[num+1])>0) {printf("第%d枚是假币",num+2);d(num+2,array);} if(abs(array[num-1]-array[num])>0) {printf("第%d枚是假币",num+1);d(num+1,array);} } if(num+1!=flag-1&&num!=0) { if(abs(array[num]-array[num+2])>0) {printf("第%d枚是假币",num+1);d(num+1,array);} if(abs(array[num+1]-array[num+2])>0) {printf("第%d枚是假币",num+2);d(num+2,array);} } } }if(n==1&&(abs(array[num]-array[num-1])>0)){printf("第%d枚是假币",num+1);d(num+1,array);}}return0;} voidd(intm,intarray[]){ if(m==1&&array[0]<array[1])printf("且假币重量小于真币.\n"); elseif(m==1) printf("且假币重量大于真币.\n"); if(m!=1&&array[m-1]<array[m-2])printf("且假币重量小于真币.\n"); elseif(m!=1) printf("且假币重量大于真币.\n");}实验结果及分析经过这个试验，了解并掌握了减治法设计思想并了解了它与分治法区分。在写这个算法前，一定要建立正确求解模型。试验名称变治法在排序问题中应用——堆排序问题试验室9#205实验目或要求试验题目用基于变治法堆排序算法对任意一组给定数据进行排序试验目标1）深刻了解并掌握变治法设计思想；2）掌握堆概念以及怎样用变治法把任意给定一组数据改变成堆；3）提升应用变治法设计算法技能。试验要求1）设计与实现堆排序算法；2）待排序数据能够手工输入(通常规模比较小，10个数据左右），用以检测程序正确性；也能够计算机随机生成（通常规模比较大，1500－3000个数据左右），用以检验(用计数法)堆排序算法时间效率。实验原理（算法基本思想）堆排序利用了大根堆(或小根堆)堆顶统计关键字最大(或最小)这一特征，使得在当前无序区中选取最大(或最小)关键字统计变得简单。(1)用大根堆排序基本思想（2）大根堆排序算法基本操作特点:堆排序(HeapSort)是一树形选择排序。堆排序特点是：在排序过程中，将R[l..n]看成是一棵完全二叉树次序存放结构，利用完全二叉树中双亲结点和孩子结点之间内在关系(参见二叉树次序存放结构)，在当前无序区中选择关键字最大(或最小)统计堆排序最坏时间复杂度为O(nlogn)。堆序平均性能较靠近于最坏性能。它是不稳定排序方法。程序代码//堆排序#ifndefHEAPSORT_H#defineHEAPSORT_HclassHeapsort{public: voidheapsort(); voidHeapBottomUp(intarry[],intn); voidFixHeap(intarry[],inti,intv,intn);};#endif voidHeapsort::HeapBottomUp(intarry[],intn){ inti; for(i=n/2;i>=1;i--)FixHeap(arry,i,arry[i],n);}voidFixHeap(intarry[],inti,intv,intn){ intj,k; k=i; v=arry[k]; while(2*k<=n) {j=2*k; if(j<n) if(arry[j]<arry[j+1])j=j+1; if(v>=arry[j])break; elsearry[k]=arry[j];k=j; } arry[k]=v;}voidHeapsort::heapsort(){intchoice; inti,n,max,arry[3000]={0},p=-1000,q=1000;doublettime; clock_tstar,finish; printf("请输入共有几个点："); scanf("%d",&n); printf("请输入你选择(1、手动输入各点信息，2、自动产生各点信息):"); scanf("%d",&choice); srand(time(NULL));switch(choic