1、精選優質文檔-傾情為你奉上考試批次算法與數據分析結課作業學生姓名 學習中心 學號 考 號 專 業 年級層次北京語言大學網絡教育學院算法與數據分析結課作業注意：本學期所布置的結課作業，請同學一律按照以下要求執行：一、學生必須預約才能在學生平臺看見相關課程的“結課作業”按鈕；二、提交路徑：個人平臺首頁-學習中的課程，點擊該課程名稱-點擊“結課作業”-點擊“瀏覽”按鈕，選擇要上傳的文檔后點擊“提交作業”即可。三、結課作業提交起止時間：2018年2月1日-3月12日。（屆時平臺自動關閉，逾期不予接收。）四、提交的文檔格式必須為word文檔，截止日期前可多次提交，平臺只保留最后一次提交的文檔；五、嚴格按

2、照課程名稱提交相應課程結課作業，提交錯誤的結課作業，按0分處理。一. 論述題(本大題共5小題,請任選其中兩道題作答,每小題25分，總分50分)1、 試述分治法的基本思想。答：分治法的基本思想是將一個規模為n的問題分解為k個規模較小的子問題，這些子問題互相獨立且與原問題相同。遞歸地解這些子問題，然后將各個子問題的解合并得到原問題的解2、 設計動態規劃算法有哪些主要步驟。答：設計動態規劃算法的主要步驟為：（1）找出最優解的性質，并刻劃其結構特征。（2）遞歸地定義最優值。（3）以自底向上的方式計算出最優值。（4）根據計算最優值時得到的信息，構造最優解3、分治法與動態規劃法的異同？答：分治法與動態規劃

3、法的相同點是：將待求解的問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。兩者的不同點是：適合于用動態規劃法求解的問題，經分解得到的子問題往往不是互相獨立的。而用分治法求解的問題，經分解得到的子問題往往是互相獨立的。4、比較分支限界法與回溯法的異同？答：相同點：二者都是一種在問題的解空間樹T上搜索問題解的算法。不同點：1.在一般情況下，分支限界法與回溯法的求解目標不同。回溯法的求解目標是找出T中滿足約束條件的所有解，而分支限界法的求解目標則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出使某一值達到極大或極小的解，即在某種意義下的最優解。2.回溯法與分支-限界法

4、對解空間的搜索方式不同，回溯法通常采用嘗試優先搜索，而分支限界法則通常采用廣度優先搜索。3.對節點存儲的常用數據結構以及節點存儲特性也各不相同，除由搜索方式決定的不同的外，分支限界法通常需要存儲一些額外的信息以利于進一步地展開搜索5、寫出回溯法搜索子集樹的算法。二. 算法設計題(本大題5小題,請任選其中兩道題作答,每小題25分，總分50分)1、背包問題的貪心算法。答：void Knapsack(int n,float M,float v,float w,float x) /重量為w1.n,價值為v1.n的 n個物品，裝入容量為M的背包 /用貪心算法求最優解向量x1.n int i; Sort(

5、n,v,w); for (i=1;i=n;i+) xi=0; float c=M; for (i=1;ic) break; xi=1; c-=wi; if (i=n) xi=c/wi; 2、最大子段和: 動態規劃算法。答：int MaxSum(int n, int a) int sum=0, b=0； /sum存儲當前最大的bj, b存儲bj for (int j=1; j0) b+= aj; else b=ai; /一旦某個區段和為負，則從下一個位置累和 if(bsum) sum=b; return sum;3、貪心算法求活動安排問題。答：template void GreedySelect

6、or(int n, Type s, Type f, bool A) A1=true; int j=1; for (int i=2;i=fj) Ai=true; j=i; else Ai=false; 4、排列問題。答：template void QuickSort (Type a, int p, int r) if (pr) int q=Partition(a,p,r); QuickSort (a,p,q-1); /對左半段排序 QuickSort (a,q+1,r); /對右半段排序 5、回溯法解迷宮問題：迷宮用二維數組存儲，用H表示墻,O表示通道。答：int x1,y1,success=0; /出口點 void MazePath(int x,int y) /遞歸求解:求迷宮maze從入口(x,y)到出口(x1,y1)的一條路徑 mazexy=*; /路徑置為* if (x=x1)&(y=y1) success=1; /到出口則成功 else if (mazexy+1=O) MazePath(x,+y); /東鄰方格是通路,向東嘗試if (!success)&(mazex+1y=O) MazePath(+x,y); /不成功且南鄰方格是通路,向南嘗試 if (!success)&(mazexy-1=O) MazePath(x,-y); /不成功且西鄰