算法設計與分析實驗指導書(編輯修改稿)
2025-08-31 18:22 本頁面
【文章內容簡介】 分三種情況：k=k=n和k=中位數。實驗四 貪心算法（2學時）基本題一：多機調度問題一、實驗目的與要求熟悉多機調度問題的算法；初步掌握貪心算法；二、實驗題 要求給出一種作業(yè)調度方案，使所給的n個作業(yè)在盡可能短的時間內由m臺機器加工處理完成。約定，每個作業(yè)均可在任何一臺機器上加工處理，但未完工前不允許中斷處理。作業(yè)不能拆分成更小的子作業(yè)。三、實驗提示把作業(yè)按加工所用的時間從大到小排序如果作業(yè)數目比機器的數目少或相等，則直接把作業(yè)分配下去如果作業(yè)數目比機器的數目多，則每臺機器上先分配一個作業(yè)，如下的作業(yè)分配時，是選那個表頭上s最小的鏈表加入新作業(yè)。typedef struct Job{ int ID。//作業(yè)號 int time。//作業(yè)所花費的時間}Job。typedef struct JobNode //作業(yè)鏈表的節(jié)點{ int ID。 int time。 JobNode *next。}JobNode,*pJobNode。typedef struct Header //鏈表的表頭{ int s。 pJobNode next。}Header,pHeader。int SelectMin(Header* M,int m){ int k=0。 for(int i=1。im。i++) { if(M[i].sm[k].s)k=i。 } return k。提高題一：用貪心算法求解最小生成樹一、實驗要求與目的 熟悉貪心算法的基本原理與適用范圍。 使用貪心算法編程，求解最小生成樹問題。二、實驗內容 任選一種貪心算法（Prim或Kruskal），求解最小生成樹。對算法進行描述和復雜性分析。編程實現，并給出測試實例提高題二： 汽車加油問題一、實驗目的與要求掌握汽車加油問題的算法；進一步掌握貪心算法；二、實驗題 一輛汽車加滿油后可以行駛N千米。旅途中有若干個加油站。若要使沿途的加油次數最少，設計一個有效的算法，指出應在那些加油站停靠加油。并證明你的算法能產生一個最優(yōu)解。三、實驗提示把兩加油站的距離放在數組中，a[1..n]表示從起始位置開始跑，經過n個加油站，a[k]表示第k－1個加油站到第k個加油站的距離。汽車在運行的過程中如果能跑到下一個站則不加油，否則要加油。（算法略） 實驗五 回溯算法（2學時）基本題一：符號三角形問題一、實驗目的與要求掌握符號三角形問題的算法；初步掌握回溯算法；二、實驗題圖下面都是“”。 下圖是由14個“+”和14個“”組成的符號三角形。2個同號下面都是“+”，2個異號下面都是“”。 + + + + ++ + + + + + + + +在一般情況下，符號三角形的第一行有n個符號。符號三角形問題要求對于給定的n，計算有多少個不同的符號三角形，使其所含的“+”和“”的個數相同。三、實驗提示void Triangle::Backtrack(int t){ if ((counthalf)||(t*(t1)/2counthalf)) return。 if (tn) sum++。 else for (int i=0。i2。i++) { p[1][t]=i。 count+=i。 for (int j=2。j=t。j++) { p[j][tj+1]=p[j1][tj+1]^p[j1][tj+2]。 count+=p[j][tj+1]。 } Backtrack(t+1)。 for (int j=2。j=t。j++) count=p[j][tj+1]。 count=i。 } }基本題二：0—1背包問題一、實驗目的與要求掌握0—1背包問題的回溯算法；進一步掌握回溯算法；二、實驗題：給定n種物品和一背包。物品i的重量是wi，其價值為vi，背包的容量為C。問應如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?三、實驗提示templateclass Typew, class TypepTypep KnapTypew, Typep::Bound(int i){// 計算上界 Typew cleft = c cw。 // 剩余容量 Typep b = cp。 // 以物品單位重量價值遞減序裝入物品 while (i = n amp。amp。 w[i] = cleft) { cleft = w[i]。 b += p[i]。 i++。 } // 裝滿背包 if (i = n) b += p[i]/w[i] * cleft。 return b。}提高題一：用回溯法求解跳馬問題一、實驗要求與目的 掌握回溯法的基本原理。 使用回溯法編程，求解跳馬問題二、實驗內容 問題描述：在N*N棋盤上有N2個格子，馬在初始位置（X0，Y0），按照象棋中馬走“日”的規(guī)則，使馬走遍全部格子且每個格子僅經過一次。編
環(huán)評公示相關推薦
鄂ICP備17016276號-1