20xx計(jì)算機(jī)算法設(shè)計(jì)與分析習(xí)題及答案(編輯修改稿)
2025-07-21 04:01 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 貪心選擇性質(zhì) 是貪心算法可行的第一個(gè)基本要素，也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。1矩陣連乘問(wèn)題的算法可由 動(dòng)態(tài)規(guī)劃 設(shè)計(jì)實(shí)現(xiàn)。1拉斯維加斯算法找到的解一定是 正確解。 貪心選擇 性質(zhì)和 最優(yōu)子結(jié)構(gòu) 性質(zhì) 。21. 動(dòng)態(tài)規(guī)劃算法的基本思想是將待求解問(wèn)題分解成若干 子問(wèn)題 ，先求解 子問(wèn)題 ，然后從這些 子問(wèn)題 的解得到原問(wèn)題的解。，且要滿足輸入、 輸出 、確定性和 有限性 四條性質(zhì)。2大整數(shù)乘積算法是用 分治法 來(lái)設(shè)計(jì)的。2以廣度優(yōu)先或以最小耗費(fèi)方式搜索問(wèn)題解的算法稱為 分支限界法 。2舍伍德算法總能求得問(wèn)題的 一個(gè)解 。2 貪心選擇性質(zhì) 是貪心算法可行的第一個(gè)基本要素，也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。 分治策略 的一種排序算法。. 最優(yōu)子結(jié)構(gòu) 性質(zhì)和 重疊子問(wèn)題 性質(zhì) 。 系統(tǒng)性 又帶有 跳躍性 的搜索算法。 隊(duì)列式（FIFO） 分支限界法和 優(yōu)先隊(duì)列式 分支限界法。 系統(tǒng)性 又帶有 跳躍性 的搜索算法。，常用的兩種剪枝函數(shù)為 約束函數(shù) 和 限界函數(shù) 。 規(guī)模 有關(guān)。 劃分的對(duì)稱性 。 所求問(wèn)題的整體最優(yōu)解可以通過(guò)一系列局部最優(yōu)的選擇，即貪心選擇來(lái)達(dá)到 。 問(wèn)題的最優(yōu)解包含了其子問(wèn)題的最優(yōu)解 。 具有限界函數(shù)的深度優(yōu)先生成法 。在任何時(shí)刻，算法只保存從根結(jié)點(diǎn)到當(dāng)前擴(kuò)展結(jié)點(diǎn)的路徑。如果解空間樹(shù)中從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的最長(zhǎng)路徑的長(zhǎng)度為h(n)，則回溯法所需的計(jì)算空間通常為 O(h(n)) ）。 子集樹(shù) 算法框架與 排列樹(shù) 算法框架。，該問(wèn)題的解空間結(jié)構(gòu)為 子集樹(shù) 結(jié)構(gòu)。，該問(wèn)題的解空間結(jié)構(gòu)為 排列樹(shù) 結(jié)構(gòu)。 排列樹(shù) 。三、算法填空void Knapsack(int n,float M,float v[],float w[],float x[]){//重量為w[1..n]],價(jià)值為v[1..n]的 n個(gè)物品，裝入容量為M的背包//用貪心算法求最優(yōu)解向量x[1..n]int i。 Sort(n,v,w)。 for (i=1。i=n。i++) x[i]=0。 float c=M。 for (i=1。i=n。i++) {if (w[i]c) break。 x[i]=1。 c=w[i]。 } if (i=n) x[i]=c/w[i]。}: 動(dòng)態(tài)規(guī)劃算法int MaxSum(int n, int a[]){ int sum=0, b=0； //sum存儲(chǔ)當(dāng)前最大的b[j], b存儲(chǔ)b[j] for (int j=1； j=n； j++) { if (b0) b+= a[j] ； else b=a[i]。 ； //一旦某個(gè)區(qū)段和為負(fù)，則從下一個(gè)位置累和 if(bsum) sum=b。 } return sum；} templateclass Typevoid GreedySelector(int n, Type s[], Type f[], bool A[]){ A[1]=true。 int j=1。 for (int i=2。i=n。i++) if (s[i]=f[j]) { A[i]=true。 j=i。 } else A[i]=false。}templateclass Typevoid QuickSort (Type a[], int p, int r){ if (pr) {int q=Partition(a,p,r)。 QuickSort (a,p,q1)。 //對(duì)左半段排序 QuickSort (a,q+1,r)。 //對(duì)右半段排序 }}Template class Typevoid perm(Type list[], int k, int m ){//產(chǎn)生[list[k:m]的所有排列 if (k==m) //只剩下一個(gè)元素 { for (int i=0。i=m。i++) coutlist[i]。 coutendl。 } else //還有多個(gè)元素待排列，遞歸產(chǎn)生排列 for (int i=k。 i=m。 i++) { swap(list[k]，list[i])。 perm(list,k+1。m)。 swap(list[k],list[i])。 }} 6. 回溯法解迷宮問(wèn)題 迷宮用二維數(shù)組存儲(chǔ)，用39。H39。表示墻,39。O39。表示通道int x1,y1,success=0。 //出口點(diǎn)void MazePath(int x,int y){//遞歸求解:求迷宮maze從入口(x,y)到出口(x1,y1)的一條路徑 maze[x][y]=39。*39。 //路徑置為* if ((x==x1)amp。amp。(y==y1)) success=1。 //到出口則成功 else {if (maze[x][y+1]==39。O39。) MazePath(x,++y)。 //東鄰方格是通路,向東嘗試 if ((!success)amp。amp。(maze[x+1][y]==39。O39。)) MazePath(++x,y)。 //不成功且南鄰方格是通路,向南嘗試 if ((!success)amp。amp。(maze[x][y1]==39。O39。)) MazePath(x,y)。 //不成功且西鄰方格是通路,向西嘗試 if ((!success)amp。amp。(maze[x1][y]==39。O39。)) MazePath(x,y)。 //不成功且北鄰方格是通路,向北嘗試 } if (!success) maze[x][y]=39。@39。 //死胡同置為@}四、證明題，即只要正在被考慮的物品裝得進(jìn)就裝入背包，則此方法不一定能得到最優(yōu)解（此題說(shuō)明0/1背包問(wèn)題與背包問(wèn)題的不同）。證明：舉例如：p={7,4,4},w={3,2,2},c=8時(shí)，由于7/3最大，若按題目要求的方法，只能取第一個(gè)，解為{1,0,0}，入包重量是7，價(jià)值為3。而此實(shí)例的最大價(jià)值應(yīng)該是4，取第2，3 個(gè)，最優(yōu)解為{0,1,1}。，要求各個(gè)城市經(jīng)歷且僅經(jīng)歷一次然后回到出發(fā)城市，并要求所走的路程最短。證明TSP問(wèn)題滿足最優(yōu)性原理證明：設(shè)s, s1, s2, …, sp, s是從s出發(fā)的一條路徑長(zhǎng)度最短的簡(jiǎn)單回路，假設(shè)從s到下一個(gè)城市s1已經(jīng)求出，則問(wèn)題轉(zhuǎn)化為求從s1到s的最短路徑，顯然s1, s2, …, sp, s一定構(gòu)成一條從s1到s的最短路徑。 如若不然，設(shè)s1, r1, r2, …, rq, s是
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號(hào)-1