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