算法分析與設(shè)計(jì)實(shí)驗(yàn)報(bào)告

組員學(xué)號(hào)姓名實(shí)驗(yàn)名稱算法實(shí)驗(yàn)整體框架的構(gòu)建實(shí)驗(yàn)室實(shí)驗(yàn)?zāi)康幕蛞?.實(shí)驗(yàn)題目算法實(shí)驗(yàn)主菜單的設(shè)計(jì)。2．實(shí)驗(yàn)?zāi)康蘑攀煜?shí)驗(yàn)環(huán)境VC＋＋6.0；⑵復(fù)習(xí)C、C++語言以及數(shù)據(jù)結(jié)構(gòu)課程的相關(guān)知識(shí)，實(shí)現(xiàn)課程間的平滑過度；3.實(shí)驗(yàn)要求1）設(shè)計(jì)的主菜單可以是圖形模式的，也可以是控制臺(tái)模式的。以控制臺(tái)為例，主菜單大致如下： －－－－－－－－－－－－－－－－－－－－－－－－－ 《算法設(shè)計(jì)與分析》實(shí)驗(yàn) －－－－－－－－－－－－－－－－－－－－－－－－－算法分析基礎(chǔ)——Fibonacci序列問題分治法在數(shù)值問題中的應(yīng)用——最近點(diǎn)對(duì)問題減治法在組合問題中的應(yīng)用——8枚硬幣問題變治法在排序問題中的應(yīng)用——堆排序問題動(dòng)態(tài)規(guī)劃法在圖問題中的應(yīng)用——全源最短路徑問題 99. 退出本實(shí)驗(yàn) －－－－－－－－－－－－－－－－－－－－－－－－－請(qǐng)輸入您所要執(zhí)行的操作（1，2，3，4，5，99）：2）點(diǎn)擊操作后進(jìn)入相應(yīng)的實(shí)驗(yàn)項(xiàng)目或是相應(yīng)項(xiàng)目的下一級(jí)菜單；3）可以反復(fù)執(zhí)行，直到退出實(shí)驗(yàn)。程序代碼voidshow(){printf("\n");printf("|－－－－－－－－－－－－－－－－－－－－－－－－－－|\n");printf("||\n");printf("|《算法設(shè)計(jì)與分析》實(shí)驗(yàn)|\n");printf("||\n");printf("|－－－－－－－－－－－－－－－－－－－－－－－－－－|\n");printf("|1.算法分析基礎(chǔ)——Fibonacci序列問題|\n");printf("||\n");printf("|2.分治法在數(shù)值問題中的應(yīng)用——最近點(diǎn)對(duì)問題|\n");printf("||\n");printf("|3.減治法在組合問題中的應(yīng)用——8枚硬幣問題|\n");printf("||\n");printf("|4.變治法在排序問題中的應(yīng)用——堆排序問題|\n");printf("||\n");printf("||\n");printf("|99.退出本實(shí)驗(yàn)|\n");printf("|－－－－－－－－－－－－－－－－－－－－－－－－－－|\n");printf("\n");printf("*請(qǐng)輸入您所要執(zhí)行的操作（1，2，3，4，5，99）：\n");printf("\n");}實(shí)驗(yàn)結(jié)果及分析實(shí)驗(yàn)名稱算法分析基礎(chǔ)——Fibonacci序列問題實(shí)驗(yàn)室實(shí)驗(yàn)?zāi)康幕蛞髮?shí)驗(yàn)題目給定一個(gè)非負(fù)整數(shù)n，計(jì)算第n個(gè)Fibonacci數(shù)實(shí)驗(yàn)?zāi)康?）理解遞歸算法和迭代算法的設(shè)計(jì)思想以及遞歸程序的調(diào)式技術(shù)2）掌握并應(yīng)用遞歸算法和迭代算法效率的理論分析(前驗(yàn)分析)和實(shí)際分析(后驗(yàn)分析)方法；3）理解這樣一個(gè)觀點(diǎn)：不同的算法可以解決相同的問題，這些算法的解題思路不同，復(fù)雜程度不同，效率也不同；實(shí)驗(yàn)要求1）使用教材2.5節(jié)中介紹的迭代算法Fib(n),找出最大的n,使得第n個(gè)Fibonacci數(shù)不超過計(jì)算機(jī)所能表示的最大整數(shù)，并給出具體的執(zhí)行時(shí)間；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)的主菜單下)。實(shí)驗(yàn)原理（算法基本思想）F(n)//根據(jù)定義，遞歸計(jì)算第n個(gè)斐波那契數(shù)//輸入：一個(gè)非負(fù)數(shù)n//輸出：第幾個(gè)斐波那契數(shù)ifn≤1returnnelsereturnF(n-1)+F(n-2)程序代碼intFib1(intn){ints[48],i;s[0]=0;s[1]=1;for(i=2;i<=n;i++)s[i]=s[i-1]+s[i-2],time1++;returns[n];}intFib2(intn){longintf;if(n>1){f=Fib2(n-1)+Fib2(n-2),time2++;returnf;}if(n<2){time3++; returnn;}time3=time3+time2;}實(shí)驗(yàn)結(jié)果及分析實(shí)驗(yàn)名稱分治法在數(shù)值問題中的應(yīng)用——最近點(diǎn)對(duì)問題實(shí)驗(yàn)室實(shí)驗(yàn)?zāi)康幕蛞髮?shí)驗(yàn)題目設(shè)p1=(x1,y1),p2=(x1,y2),……,pn=(xn,yn)是平面上n個(gè)點(diǎn)構(gòu)成的集合S，設(shè)計(jì)算法找出集合S中距離最近的點(diǎn)對(duì)。實(shí)驗(yàn)?zāi)康?）提高應(yīng)用蠻力法設(shè)計(jì)算法的技能；2）深刻理解并掌握分治法的設(shè)計(jì)思想；3）理解這樣一個(gè)觀點(diǎn)：用蠻力法設(shè)計(jì)的算法，一般來說，經(jīng)過適度的努力后，都可以對(duì)其進(jìn)行改進(jìn)，以提高算法的效率。實(shí)驗(yàn)要求1）設(shè)計(jì)并實(shí)現(xiàn)用BF方法求解最近點(diǎn)對(duì)問題的算法；2）設(shè)計(jì)并實(shí)現(xiàn)用DAC方法求解最近點(diǎn)對(duì)問題的算法；3）以上兩種算法的輸入既可以手動(dòng)輸入，也可以自動(dòng)生成；4）算法不僅要輸出最近點(diǎn)對(duì)的距離，還要輸出最近點(diǎn)對(duì)的兩個(gè)點(diǎn)；5）對(duì)上述兩個(gè)算法進(jìn)行時(shí)間復(fù)雜性分析，并設(shè)計(jì)實(shí)驗(yàn)程序驗(yàn)證分析結(jié)果；6）設(shè)計(jì)可供用戶選擇算法的交互式菜單(放在相應(yīng)的主菜單下)。實(shí)驗(yàn)原理（算法基本思想）程序代碼voiddian(){time_tc_start1,c_end1;c_start1=clock();ints[100],f[100],i,j,t,a,b,c,d,n;printf("蠻力法求最近點(diǎn)問題");printf("\n請(qǐng)輸入坐標(biāo)數(shù):");scanf("%d",&n);for(t=0;t<n;t++){ scanf("%d",&s[t]); scanf("%d",&f[t]);}doublel,k;k=sqrt((s[1]-s[0])*(s[1]-s[0])+(f[1]-f[0])*(f[1]-f[0]));a=s[1];b=f[1];c=s[0];d=f[0];for(i=0;i<n;i++){ for(j=i+1;j<=n;j++){l=sqrt((s[j]-s[i])*(s[j]-s[i])+(f[j]-f[i])*(f[j]-f[i]));if(k>l) {k=l;a=s[j];b=f[j];c=s[i];d=f[i]; } }} c_end1=clock(); printf("\n最近的距離為：%f\n",k);printf("\n他們的坐標(biāo)分別為：(%d,%d),(%d,%d)\n",a,b,c,d);printf("\n此方法所花時(shí)間為:%f",difftime(c_end1,c_start1)/18.2);}typedefstruct{doublex;doubley;}pttype;longarr[maxsize];longarr1;pttypept[maxsize];intsortcmp(constvoid*a,constvoid*b){if(((pttype*)a)->x<((pttype*)b)->x)return-1;elsereturn1;}intarrcmp(constvoid*a,constvoid*b){if(((pttype*)a)->y<((pttype*)b)->y)return-1;elsereturn1;}doubledis(pttypea,pttypeb){returnsqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}doublegetMin(doublea,doubleb){if(a<b)returna;elsereturnb;}doubleshortest(longleft,longright){if(right-left==1)//兩個(gè)點(diǎn)returndis(pt[left],pt[right]);if(right-left==2)//三個(gè)點(diǎn)returngetMin(getMin(dis(pt[left],pt[left+1]),dis(pt[left],pt[right])),dis(pt[left+1],pt[right]));/*枚舉個(gè)點(diǎn)和個(gè)點(diǎn)的情況，當(dāng)邊界使用*///大于用分治法longi,j,mid=(left+right)/2;doublecurmin=getMin(shortest(left,mid),shortest(mid+1,right));arr1=0;for(i=mid;i>=left&&pt[mid+1].x-pt[i].x<=curmin;i--)arr[arr1++]=i;//確定左邊-d內(nèi)的點(diǎn)for(i=mid+1;i<=right&&pt[i].x-pt[mid].x<=curmin;i++)arr[arr1++]=i;//確定右邊+d內(nèi)的點(diǎn)qsort(arr,arr1,sizeof(arr[0]),arrcmp);//按y排序for(i=0;i<arr1;i++)for(j=i+1;j<arr1&&pt[arr[j]].y-pt[arr[i]].y<=curmin;j++)curmin=getMin(curmin,dis(pt[arr[i]],pt[arr[j]]));returncurmin;}實(shí)驗(yàn)結(jié)果及分析實(shí)驗(yàn)名稱減治法在組合問題中的應(yīng)用——8枚硬幣問題實(shí)驗(yàn)室實(shí)驗(yàn)?zāi)康幕蛞髮?shí)驗(yàn)題目在8枚外觀相同的硬幣中，有一枚是假幣，并且已知假幣與真幣的重量不同，但不知道假幣與真幣相比較輕還是較重?？梢酝ㄟ^一架天平來任意比較兩組硬幣，設(shè)計(jì)一個(gè)高效的算法來檢測這枚假幣。實(shí)驗(yàn)?zāi)康?）深刻理解并掌握減治法的設(shè)計(jì)思想并理解它與分治法的區(qū)別；2）提高應(yīng)用減治法設(shè)計(jì)算法的技能。3）理解這樣一個(gè)觀點(diǎn)：建立正角的模型對(duì)于問題的求解是非常重要的。實(shí)驗(yàn)要求1）設(shè)計(jì)減治算法實(shí)現(xiàn)8枚硬幣問題；2）設(shè)計(jì)實(shí)驗(yàn)程序，考察用減治技術(shù)設(shè)計(jì)的算法是否高效；3）擴(kuò)展算法，使之能處理n枚硬幣中有一枚假幣的問題。實(shí)驗(yàn)原理（算法基本思想）程序代碼intjiabi(ints[],intn,inti){intl[1000];intr=0,t,k,y,x,a,b,c=0,f,e;k=n+i;f=i;if(n>=3){if(n%2==0){ t=n/2;for(e=i;e<i+t;e++)y+=s[e];for(e=i+t;e<n+i;e++)x+=s[e];if(y>x){for(e=i;e<i+t;e++)l[e]=s[e];returnjiabi(l,t,f);}c=0;if(x>y){for(e=i+t;e<n+i;e++)l[e]=s[e];returnjiabi(l,t,f+t);} if(y==x) printf("沒有假幣?。?！");}if(n%2==1){a=(n-1)/2;for(e=i;e<i+a;e++)y+=s[e];for(e=a+i;e<i+n-1;e++) x+=s[e];b=s[k-1];if(y>x){for(e=i;e<i+a;e++)l[e]=s[e];returnjiabi(l,a,f);}if(x>y){for(e=a+i;e<i+n-1;e++)l[e]=s[e];returnjiabi(l,a,f+a);}if(x==y)printf("第%d個(gè)是假幣",k);}}if(n==2){if(s[i]>s[i+n-1]) printf("第%d個(gè)是假幣",i+1); if(s[i]<s[i+n-1]) printf("第%d個(gè)是假幣",n+i);}if(n==1)printf("第%d個(gè)是假幣",i+1);}實(shí)驗(yàn)結(jié)果及分析實(shí)驗(yàn)名稱變治法在排序問題中的應(yīng)用——堆排序問題實(shí)驗(yàn)室實(shí)驗(yàn)?zāi)康幕蛞髮?shí)驗(yàn)題目用基于變治法