算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告(中南民族大學(xué))

.. .. ..院 系： 計(jì)算機(jī)科學(xué)學(xué)院專 業(yè)：專業(yè).專注 ... .. ..年 級(jí)：課程名稱：算法設(shè)計(jì)與分析基礎(chǔ)班 號(hào)：組 號(hào)：指導(dǎo)教師：年 月 日學(xué)號(hào) 姓名組員算法分析基礎(chǔ)實(shí)驗(yàn)名稱 ——給定一個(gè)非負(fù)整數(shù) n，計(jì)算第 n 實(shí)驗(yàn)室個(gè)Fibonacci 數(shù)專業(yè).專注 ... .. ..一．實(shí)驗(yàn)?zāi)康?）理解遞歸算法和迭代算法的設(shè)計(jì)思想以及遞歸程序的調(diào)式技術(shù)2)握并應(yīng)用遞歸算法和迭代算法效率的理論分析 (前驗(yàn)分析)和經(jīng)驗(yàn)分析(后驗(yàn)分析)方法；理解這樣一個(gè)觀點(diǎn)：不同的算法可以解決相同的問(wèn)題，這些算法的解題思路不同，復(fù)雜程度不同，效率也不同；二．實(shí)驗(yàn)要求1）使用教材2.5節(jié)中介紹的迭代算法 Fib(n),找出最大的 n,使得第n個(gè)Fibonacci 數(shù)不超過(guò)實(shí)計(jì)算機(jī)所能表示的最大整數(shù) ，并給出具體的執(zhí)行時(shí)間 ；驗(yàn)2）對(duì)于要求 1),使用教材 2.5節(jié)中介紹的遞歸算法 F(n)進(jìn)行計(jì)算,同樣給出具體的執(zhí)行時(shí)目間，并同1)的執(zhí)行時(shí)間進(jìn)行比較 ；的3）對(duì)于輸入同樣的非負(fù)整數(shù) n，比較上述兩種算法基本操作的執(zhí)行次數(shù) ；或4）對(duì)1)中的迭代算法進(jìn)行改進(jìn) ，使得改進(jìn)后的迭代算法其空間復(fù)雜度為 Θ(1)；要5）設(shè)計(jì)可供用戶選擇算法的交互式菜單 (放在相應(yīng)的主菜單下 )。求專業(yè).專注 ... .. ..一．迭代算法求最大 Fibonacci 在數(shù)列中位置1.先利用迭代求得計(jì)算機(jī)能表示的最大數(shù) MaxUnsignedInt.實(shí)unsignedlongintMaxUnsignedInt=1;驗(yàn)while(MaxUnsignedInt*2+1!=MaxUnsignedInt)原{理MaxUnsignedInt=MaxUnsignedInt*2+1;（}算2.從1起進(jìn)行(n-1) +(n-2) = n迭代，直到條件(temp3>temp) 時(shí)發(fā)生溢出(及超過(guò)最大法數(shù))，退出循環(huán)。求得此時(shí)的迭代次數(shù) -1即為最大 Fibonacci 的位置?；鵸nsignedlongintn=MaxUnsignedInt;本for(i=1;temp<=n;i++)//temp<=n思{想temp=temp1+temp2;）if(temp3>temp)// 當(dāng)temp3>temp 時(shí)，則發(fā)現(xiàn)temp發(fā)生溢出，結(jié)束計(jì)算break;專業(yè).專注 ... .. ..temp3=temp;temp2=temp1;temp1=temp;}二．遞歸算法1.根據(jù)/ 0 n=0f(n)= 1 n=1\ f(n-1)+f(n-2) n=2進(jìn)行遞歸調(diào)用求解 。longFF(unsignedinttt)//usedigui{if(tt<=1)returntt;elsereturnFF(tt-1)+FF(tt-2);}三．改進(jìn)空間復(fù)雜度為 Θ(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);專業(yè).專注 ... .. ..}voidfibo(){unsignedlongintMaxUnsignedInt,n,times,t=100;clock_tstart=clock();程序MaxUnsignedInt=1;代while(MaxUnsignedInt*2+1!=MaxUnsignedInt)碼{MaxUnsignedInt=MaxUnsignedInt*2+1;}cout<<" 時(shí)間消耗："<<clock()-start<<endl;專業(yè).專注 ... .. ..n=MaxUnsignedInt;intchoose;boolend_this=true;while(end_this){cout<<"************************************************************\n";cout<<"1. 輸 入 一 個(gè) 你 想 要 判 斷 的 數(shù)\n";cout<<"2. 判 斷 從 0 到 N 的 Fibonacci\n";cout<<"3. 計(jì) 算 機(jī) 能 判 斷 的 最 大 數(shù)\n";cout<<"4. 用 遞 歸 計(jì) 算 你 想 要 判 斷 的 數(shù)\n";cout<<"5. 結(jié) 束\n";again: cout<<"youwantdo:";cin>>choose;if(choose!=1&&choose!=2&&choose!=3&&choose!=4)// 輸入菜單檢查{cout<<" 輸入錯(cuò)誤\n";專業(yè).專注 ... .. ..gotoagain;}switch(choose){case1:{cout<<"inputyournumber:";cin>>t;start=clock();times=F(t);cout<<t<<" 是第"<<times<<" 個(gè)Fibonacci 數(shù)"<<endl;cout<<" 時(shí)間消耗："<<clock()-start<<endl;break;}case2:{start=clock();F(t);cout<<" 時(shí)間消耗："<<clock()-start<<endl;break;專業(yè).專注 ... .. ..}case3:{cout<<" 最大數(shù)是"<<n<<endl;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(temp3>temp)//當(dāng)temp3>temp時(shí)，則發(fā)現(xiàn)temp發(fā)生溢出，結(jié)束計(jì)算break;temp3=temp;temp2=temp1;temp1=temp;}cout<<n<<" 是第"<<i-1<<" 個(gè)Fibonacci 數(shù)"<<endl;cout<<" 時(shí)間消耗："<<clock()-start<<endl;break;專業(yè).專注 ... .. ..}case4:{start=clock();intx;cout<<"Youwantdo:";cin>>x;times=FF(x);cout<<" 第"<<x<<" 個(gè)Fibonacci數(shù)是"<<times<<endl;cout<<" 時(shí)間消耗："<<clock()-start<<endl;break;}case5:{end_this=false;break;}}}專業(yè).專注 ... .. ..}intF(unsignedintuu){unsignedlonginttemp=0,temp1=0,temp2=1;inti;//if(uu==0||uu==1)//returnuu;for(i=1;i<=uu;i++){temp =temp1+temp2;cout<<"number"<<i<<"is"<<temp<<endl;if(temp>=uu)returni;temp2=temp1;temp1=temp;}專業(yè).專注 ... .. ..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);}專業(yè).專注 .實(shí)驗(yàn)結(jié)果及分析

.. .. ..1.求最大數(shù)2.遞歸法與迭代法性能比較遞歸 迭代3.改進(jìn)算法1.利用公式法對(duì)第 n項(xiàng)Fibonacci數(shù)求解時(shí)可能會(huì)得出錯(cuò)誤結(jié)果 。主要原因是由于double 類型的精度還不夠 ，所以程序算出來(lái)的結(jié)果會(huì)有誤差 ，要把公式展開計(jì)算 。2.由于遞歸調(diào)用棧是一個(gè)費(fèi)時(shí)的過(guò)程 ，通過(guò)遞歸法和迭代法的比較表明 ，雖然遞歸算法的代碼更精簡(jiǎn)更有可讀性 ，但是執(zhí)行速度無(wú)法滿足大數(shù)問(wèn)題的求解 。3.在當(dāng)前計(jì)算機(jī)的空間較大的情況下 ，在一些速度較慢的問(wèn)題中 ，空間換時(shí)間是一個(gè)比較周全的策略。專業(yè).專注 ... .. ..分治法在數(shù)值問(wèn)題中的應(yīng)用實(shí)驗(yàn)名稱 實(shí)驗(yàn)室——矩陣相乘問(wèn)題專業(yè).專注 .實(shí)驗(yàn)

.. .. ..一．實(shí)驗(yàn)題目設(shè)M1和M2是兩個(gè)n×n的矩陣，設(shè)計(jì)算法計(jì)算 M1×M2 的乘積。二．實(shí)驗(yàn)?zāi)康?）提高應(yīng)用蠻力法設(shè)計(jì)算法的技能 ；2）深刻理解并掌握分治法的設(shè)計(jì)思想 ；3）理解這樣一個(gè)觀點(diǎn) ：用蠻力法設(shè)計(jì)的算法 ，一般來(lái)說(shuō)，經(jīng)過(guò)適度的努力后 ，都可以對(duì)其進(jìn)行改進(jìn)，以提高算法的效率 。三．實(shí)驗(yàn)要求目1）設(shè)計(jì)并實(shí)現(xiàn)用BF方法求解矩陣相乘問(wèn)題的算法；的2）設(shè)計(jì)并實(shí)現(xiàn)用DAC方法求解矩陣相乘問(wèn)題的算法；或3）以上兩種算法的輸入既可以手動(dòng)輸入，也可以自動(dòng)生成；要4）對(duì)上述兩個(gè)算法進(jìn)行時(shí)間復(fù)雜性分析，并設(shè)計(jì)實(shí)驗(yàn)程序驗(yàn)證求 分析結(jié)果；5）設(shè)計(jì)可供用戶選擇算法的交互式菜單 (放在相應(yīng)的主菜單下 )。專業(yè).專注 ... .. ..定義：若A=(a)B=(b)是n×n的方陣，則對(duì)i,j=1,2,?n，定義乘積C=A?B中ij,ij的元素cij為：實(shí)驗(yàn)1.分塊解法原 通常的做法是將矩陣進(jìn)行分塊相乘 ，如下圖所示：理（算法基專業(yè).專注 ... .. ..本 二．Strassen 解法思 分治法思想想 將問(wèn)題實(shí)例劃分為同一問(wèn)題的幾個(gè)較小的實(shí)例 。對(duì)這些較小實(shí)例求解 ，通常使） 用遞歸方法 ，但在問(wèn)題規(guī)模足夠小時(shí) ，也會(huì)使用另一種算法 。如果有必要，合并這些問(wèn)題的解，以得到原始問(wèn)題的解 。求解矩陣相乘的 DAC算法，使用了strassen算法。DAC（A[]，B[]，n）{Ifn=2 使用7次乘法的方法求得解ElseDivide（A）//把A分成4塊Divide（B）//把B分成4塊調(diào)用7次strassen算法求得解的 4塊合并這4塊得到解并返回}偽代碼Serial_StrassenMultiply(A,B,C){專業(yè).專注 ... .. ..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+M5專業(yè).專注 ... .. ..C2=M2+M4C3=M1-M2+M3+M6}程序代

矩陣相乘問(wèn)題voidPrintIn(ArrayA,ArrayB){intn=A.n;inti,j;printf("請(qǐng)輸入A數(shù)據(jù)：\n");for(i=0;i<n;i++)for(j=0;j<n;j++)cin>>A.a[i*n+j];printf("請(qǐng)輸入B數(shù)據(jù)：\n");for(i=0;i<n;i++)for(j=0;j<n;j++)cin>>B.a[i*n+j];}碼voidRandomIn(ArrayA,ArrayB){intn=A.n;srand((unsigned)time(NULL));inti,j;for(i=0;i<n;i++)for(j=0;j<n;j++)A.a[i*n+j]=rand()%10;專業(yè).專注 ... .. ..for(i=0;i<n;i++)for(j=0;j<n;j++)B.a[i*n+j]=rand()%10;}voidPrintOut(ArrayA){intn=A.n;inti,j;for(i=0;i<n;i++){for(j=0;j<n;j++)cout<<A.a[i*n+j]<< '';printf("\n" );}}voiddivide(Arrayd,Arrayd00,Arrayd01,Arrayd10,Arrayd11) /*分割矩陣*/{intn=d00.n;inti,j;for(i=0;i<n;i++){for(j=0;j<n;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;i<n;i++){for(j=0;j<n;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+j]=d10.a[n*i+j];d.a[2*n*n+2*n*i+n+j]=d11.a[n*i+j];}專業(yè).專注 ... .. ..}d.n=2*n;returnd;}Arrayoperator +(ArrayA,ArrayB){intn=A.n;ArrayC;C.a=(int*)malloc(sizeof(int)*(n*n));for(inti=0;i<n*n;i++)C.a[i]=A.a[i]+B.a[i];C.n=A.n;returnC;}Arrayoperator -(ArrayA,ArrayB){intn=A.n;ArrayC;C.a=(int*)malloc(sizeof(int)*(n*n));for(inti=0;i<n*n;i++)C.a[i]=A.a[i]-B.a[i];C.n=A.n;returnC;}Arraystrassen(ArrayA,ArrayB){intn=A.n;ArrayC;C.a=(int*)malloc(sizeof(int)*(n*n));C.n=n;if(n==2){intm1,m2,m3,m4,m5,m6,m7;m1=(A.a[0]+A.a[3])*(B.a[0]+B.a[3]);m2=(A.a[2]+A.a[3])*B.a[0];m3=A.a[0]*(B.a[1]-B.a[3]);m4=A.a[3]*(B.a[2]-B.a[0]);m5=(A.a[0]+A.a[1])*B.a[3];m6=(A.a[2]-A.a[0])*(B.a[0]+B.a[1]);m7=(A.a[1]-A.a[3])*(B.a[2]+B.a[3]);C.a[0]=m1+m4-m5+m7;C.a[1]=m3+m5;C.a[2]=m2+m4;C.a[3]=m1+m3-m2+m6;專業(yè).專注 ... .. ..returnC;}else{n=n/2;Arraya00,a01,a10,a11;Arrayb00,b01,b10,b11;Arrayc00,c01,c10,c11;Arrays1,s2,s3,s4,s5,s6,s7;a00.a=(int*)malloc(sizeof(int)*(n*n));a00.n=n;a01.a=(int*)malloc(sizeof(int)*(n*n));a01.n=n;a10.a=(int*)malloc(sizeof(int)*(n*n));a10.n=n;a11.a=(int*)malloc(sizeof(int)*(n*n));a11.n=n;b00.a=(int*)malloc(sizeof(int)*(n*n));b00.n=n;b01.a=(int*)malloc(sizeof(int)*(n*n));b01.n=n;b10.a=(int*)malloc(sizeof(int)*(n*n));b10.n=n;b11.a=(int*)malloc(sizeof(int)*(n*n));b11.n=n;divide(A,a00,a01,a10,a11);divide(B,b00,b01,b10,b11);s1=strassen(a00+a11,b00+b11);s2=strassen(a10+a11,b00);s3=strassen(a00,b01-b11);s5=strassen(a00+a01,b11);s4=strassen(a11,b10-b00);s6=strassen(a10-a00,b00+b01);s7=strassen(a01-a11,b10+b11);c00=s1+s4-s5+s7;c01=s3+s5;c10=s2+s4;c11=s1+s3-s2+s6;C=merge(c00,c01,c10,c11);returnC;}}Arraymul(ArrayA,ArrayB) //普通的矩陣乘法計(jì)算{專業(yè).專注 ... .. ..intn=A.n;ArrayC;C.a=(int*)malloc(sizeof(int)*(n*n));C.n=n;inti,j,k;for(i=0;i<n;i++)for(j=0;j<n;j++){C.a[i*n+j]=0;for(k=0;k<n;k++)C.a[i*n+j]=C.a[i*n+j]+A.a[i*n+k]*B.a[k*n+j];}returnC;}voidmatrix(){intn;charch;ArrayA,B,C;printf("\t\t計(jì)算M1×M2的乘積\n");printf("\t\t 輸入矩陣階數(shù)n:");cin>>n;A.a=(int*)malloc(sizeof(int)*(n*n));A.n=n;B.a=(int*)malloc(sizeof(int)*(n*n));B.n=n;C.a=(int*)malloc(sizeof(int)*(n*n));C.n=n;printf("\t\t---1 手動(dòng)輸入---\n" );printf("\t\t---2 隨機(jī)生成---\n" );printf("\t\t 請(qǐng)選擇\n\n" );ch=getch();switch(ch){case'1':printf("手動(dòng)輸入\n");PrintIn(A,B);printf("\n" );break;case'2':printf("自動(dòng)生成\n" );RandomIn(A,B);專業(yè).專注 ... .. ..break;default:printf("按鍵錯(cuò)誤\n");break;}printf("結(jié)果數(shù)組A中數(shù)據(jù)為：\n");PrintOut(A);printf("結(jié)果數(shù)組B中數(shù)據(jù)為：\n");PrintOut(B);cout<<endl;do{doublestart,finish,duration;printf("\n---1 用BF方法---\n" );printf("---2 用DAC方法---\n" );printf("---3 退出 ---\n" );printf("\n請(qǐng)選擇:");ch=getch();switch(ch){case'1':start=clock();C=mul(A,B);finish=clock();duration=( double)(finish-start);printf("\n 用BF方法得出的結(jié)果\n" );PrintOut(C);printf( "用BF方法計(jì)算矩陣所花費(fèi)的時(shí)間是 ：%fms\n" ,duration);printf("\n" );break;case'2':start=clock();C=strassen(A,B);finish=clock();duration=( double)(finish-start);printf("用DAC方法得出的結(jié)果 \n");PrintOut(C);printf( "DAC方法計(jì)算矩陣所花費(fèi)的時(shí)間是 ：%fms\n" ,duration);printf("\n" );break;case'3':exit(0);default:printf("按鍵錯(cuò)誤\n");}printf("\n 你想用另外一種方法嗎 ？請(qǐng)輸入(Y/N)?：");do專業(yè).專注 ... .. ..{ch=getch();}while(ch!='Y'&&ch!= 'y'&&ch!= 'N'&&ch!= 'n');}while(ch=='Y'||ch=='y');}專業(yè).專注 ... .. ..實(shí)驗(yàn)結(jié)果及分析時(shí)間復(fù)雜度1.分塊相乘總共用了 8次乘法，因而需要 Θ(nlog28)即Θ(n3)的時(shí)間復(fù)雜度。2.在求解M1，M2，M3，M4，M5，M6，M7時(shí)需要使用 7次矩陣乘法，其他都是矩陣加法和減法。因此時(shí)間復(fù)雜度下降為 O(nlog27)=O(n2.807)。有得必有失，Strassen演算法的數(shù)值穩(wěn)定性較差 。專業(yè).專注 ... .. ..減治法在組合問(wèn)題中的應(yīng)用實(shí)驗(yàn)名稱 實(shí)驗(yàn)室實(shí)驗(yàn)?zāi)?/p>

——8枚硬幣問(wèn)題二．實(shí)驗(yàn)?zāi)康?）深刻理解并掌握減治法的設(shè)計(jì)思想并理解它與分治法的區(qū)別 ；2）提高應(yīng)用減治法設(shè)計(jì)算法的技能 。3）理解這樣一個(gè)觀點(diǎn) ：建立正角的模型對(duì)于問(wèn)題的求解是非常重要的 。二．實(shí)驗(yàn)要求的1）設(shè)計(jì)減治算法實(shí)現(xiàn)8枚硬幣問(wèn)題；或2）設(shè)計(jì)實(shí)驗(yàn)程序，考察用減治技術(shù)設(shè)計(jì)的算法是否高效；要 3）擴(kuò)展算法，使之能處理 n枚硬幣中有一枚假幣的問(wèn)題 。求專業(yè).專注 ... .. ..實(shí)驗(yàn)原理（算法基減治法原理本思想）專業(yè).專注 ... .. ..假幣問(wèn)題voidfake_coin(){int a[100];int i,n,p;程printf("please input n:");序scanf("%d",&n);代for(i=0;i<n;i++)碼{cout<<"a["<<i<<"]=";cin>>a[i];}專業(yè).專注 ... .. ..p=check_coin_2(a,0,n-1);//printf("the false coin is %d\n",p);cout<<"the false coin is"<<p<<endl;}int sum_coin(int a[],int from,int to){int i,sum=0;for(i=from;i<=to;i++)sum+=a[i];return sum;}int check_coin_2(int a[],int from,int to){int i,n=to-from+1;if(n==1)return from;else{if(n%2==0){專業(yè).專注 ... .. ..if(sum_coin(a,from,from+n/2-1)==sum_coin(a,to-n/2+1,to))return from-1;else{if(sum_coin(a,from,from+n/2-1)<sum_coin(a,to-n/2+1,to))check_coin_2(a,from,from+n/2-1);elsecheck_coin_2(a,to-n/2+1,to);}}elsecheck_coin_2(a,from+1,to); } }專業(yè).專注 ... .. ..實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)結(jié)果正確，能夠在N枚硬幣問(wèn)題條件下準(zhǔn)確查找假幣在什么位置 。通過(guò)硬幣問(wèn)題，讓我更加理解了減治法的使用 ，讓我對(duì)減治法有了更深的理解，對(duì)于以后的編程思想有了更深的研究專業(yè).專注 ... .. ..變治法在排序問(wèn)題中的應(yīng)用實(shí)驗(yàn)名稱 實(shí)驗(yàn)室 9#204——堆排序?qū)I(yè).專注 ... .. ..三．實(shí)驗(yàn)?zāi)康?）深刻理解并掌握變治法的設(shè)計(jì)思想 ；2）掌握堆的概念以及如何用變治法把任意給定的一組數(shù)據(jù)改變成堆 ；3）提高應(yīng)用變治法設(shè)計(jì)算法的技能 。二．實(shí)驗(yàn)要求1）設(shè)計(jì)與實(shí)現(xiàn)堆排序算法 ；2）待排序的數(shù)據(jù)可以手工輸入 (通常規(guī)模比較小 ，10個(gè)數(shù)據(jù)左右），用以檢測(cè)程序的正實(shí)確性；也可以計(jì)算機(jī)隨機(jī)生成 （通常規(guī)模比較大 ，1500－3000 個(gè)數(shù)據(jù)左右），用以檢驗(yàn)驗(yàn)(用計(jì)數(shù)法)堆排序算法的時(shí)間效率 。目的或要求專業(yè).專注 ... .. ..專業(yè).專注 .實(shí)驗(yàn)原理（算法基本思想）

.. .. ..1)將初始待排序關(guān)鍵字序列 (R1,R2....Rn)構(gòu)建成大頂堆，此堆為初始的無(wú)須區(qū) ；2)將堆頂元素 R[1]與最后一個(gè)元素 R[n]交換，此時(shí)得到新的無(wú)序區(qū) (R1,R2,......Rn-1)和新的有序區(qū) (Rn),且滿足R[1,2...n-1]<=R[n];