2023年全國碩士研究生考試考研英語一試題真題(含答案詳解+作文范文)_第1頁
已閱讀1頁,還剩11頁未讀 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

1、<p><b>  算法分析與設(shè)計</b></p><p>  課 程 設(shè) 計 報 告 </p><p>  課程名稱 算 法 分 析 與 設(shè) 計</p><p>  實驗學期 2013 年至 2014 年 第 1 學期</p><p>  所在學院 理學院 年級 <

2、/p><p>  專業(yè)班級 信息與計算科學3班 </p><p>  《算法分析與設(shè)計》課程設(shè)計報告</p><p><b>  目 錄</b></p><p><b>  1課程實驗概述4</b></p><p>  1.1 問題概述4</p>

3、<p>  1.2 目的與任務(wù)4</p><p>  1.3 開發(fā)環(huán)境4</p><p>  1.4 參考資料4</p><p>  1.5 任務(wù)完成的一般過程4</p><p>  1.6 軟件配置5</p><p>  2 個人的構(gòu)思與創(chuàng)意5</p><p><b

4、>  2.1 構(gòu)思5</b></p><p><b>  2.2 特色5</b></p><p>  3 用貪心算法解決活動安排的問題的實驗及其結(jié)果分析5</p><p>  3.1 貪心算法簡介5</p><p>  3.2 貪心算法思路6</p><p>  3.3

5、 貪心算法實現(xiàn)6</p><p>  3.4 算法結(jié)果7</p><p>  3.4.1 實驗結(jié)果8</p><p>  3.4.2 結(jié)果分析8</p><p>  3.5 算法分析9</p><p>  3.5.1 關(guān)鍵代碼及解釋9</p><p>  3.5.2 算法流程圖10

6、</p><p>  3.5.3 時間復雜度分析11</p><p>  4 實驗個人小結(jié)11</p><p>  4.1總體實驗分析總結(jié)11</p><p>  4.2 個人經(jīng)驗總結(jié)11</p><p>  4.2.1 收獲11</p><p>  4.2.2 不足12</p

7、><p><b>  1課程實驗概述 </b></p><p><b>  1.1 問題概述</b></p><p>  設(shè)有n個活動的集合E={1,2,……,n},其中每個活動都要求使用同一資源,如演講會場等,而在同一時間內(nèi)只有一個活動能使用這一資源。每個活動i都有一個要求使用該資源的起始時間si和一個結(jié)束時間fi,且si&

8、lt;fi。如果選擇了活動i,則它在時間區(qū)間[si,fi]內(nèi)占用資源。若區(qū)間[si,fi]與區(qū)間[sj,fj]不相交,則稱活動i與活動j是相容的。也就是說,當si>=fj或者sj>=fi時,活動i與活動j相容?;顒影才艈栴}就是要在所給的活動集合中選出最大的相容活動子集合。</p><p><b>  1.2 目的與任務(wù)</b></p><p>  利用貪心

9、算法的性質(zhì),通過選擇適當?shù)呢澬牟呗缘呢澬乃惴ń鉀Q活動安排問題,且能求得活動安排的最優(yōu)解。</p><p><b>  1.3 開發(fā)環(huán)境</b></p><p>  平臺:Windows 7; 編程語言:C語言;</p><p><b>  1.4 參考資料</b></p><p>  [1]

10、算法設(shè)計與分析(第二版) 王曉東 編著 清華大學出版社 2011</p><p>  [2] 標準C語言基礎(chǔ)教程(第四版) [美]Gary J.Bronson 電子工業(yè)出版社 2011</p><p>  1.5 任務(wù)完成的一般過程</p><p>  完成過程如下圖1所示:</p><p>  圖1 任務(wù)完成的一般過程</p>

11、<p><b>  1.6 軟件配置</b></p><p>  編程工具:C-Free5.0</p><p>  2 個人的構(gòu)思與創(chuàng)意</p><p><b>  2.1 構(gòu)思</b></p><p>  此次課程設(shè)計的構(gòu)思過程的核心是:貪心算法并不總能求得問題的整體最優(yōu)解。但對于活

12、動安排問題,貪心算法卻總能求得的整體最優(yōu)解,即它最終所確定的相容活動集合A的規(guī)模最大。因此,這個方向非常明確,就是用貪心算法解決活動安排問題。</p><p>  首先,貪心算法最大的難度在于選擇貪心策略,只要選擇正確的貪心策略就能通過貪心算法求得最優(yōu)解,對于活動安排,以選擇結(jié)束時間最早的活動為貪心策略是可以得到最優(yōu)解的。</p><p>  其次,既然是按照一定的順序來選擇活動,那么必將

13、先要對活動按結(jié)束時間遞增進行排序,因為排序后,編寫貪心算法程序會變得十分簡潔。</p><p>  最后,在對所有活動進行選擇完畢后,要程序中顯示選擇結(jié)果,以確實是否正確。</p><p><b>  2.2 特色</b></p><p>  本次編程,個人覺得最大的特色就是把貪心選擇算法程序和結(jié)果顯示程序分離開成單獨的模塊,這樣會使得貪心選擇

14、算法變得更加簡潔易懂,便于瀏覽閱讀。</p><p>  其次,在界面設(shè)計上,為了讓前后銜接的更加美觀,也設(shè)置的兩個表格,以便顯示輸入是的活動表和排序后的活動表,這樣可以很直觀的看出此次設(shè)計的運行過程。</p><p>  再者,我是通過設(shè)置全局變量,一次賦值或者排序后都可以在所有函數(shù)中調(diào)用,這也使得個模塊的連接更加簡單,沒有復雜的地址調(diào)用,是代碼更具易讀性。</p><

15、;p>  3 用貪心算法解決活動安排的問題的實驗及其結(jié)果分析</p><p>  3.1 貪心算法簡介</p><p>  貪心算法(又稱貪婪算法)是指,在對問題求解時,總是做出在當前看來是最好的選擇。也就是說,不從整體最優(yōu)上加以考慮,他所做出的僅是在某種意義上的局部最優(yōu)解。貪心算法不是對所有問題都能得到整體最優(yōu)解,但對范圍相當廣泛的許多問題他能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解

16、。</p><p>  3.2 貪心算法思路</p><p>  活動安排運用貪心算法的思路為,盡可能多的使更多的事件得到資源的安排。按這種方法選擇相容活動為未安排活動留下盡可能多的時間。也就是說,該算法的貪心選擇的意義是使剩余的可安排時間段極大化,以便安排盡可能多的相容活動。實現(xiàn)方法是在滿足相容的條件下,使結(jié)束時間靠前的活動得到資源,這樣就為后續(xù)時間留下更多的安排時間,以使更多的活動得到

17、安排。</p><p>  3.3 貪心算法實現(xiàn)</p><p>  貪心算法并不總能求得問題的整體最優(yōu)解。但對于活動安排問題,貪心算法卻總能求得的整體最優(yōu)解,即它最終所確定的相容活動集合A的規(guī)模最大。這個結(jié)論可以用數(shù)學歸納法證明。事實上,設(shè)E={1,2,...,n}為所給的活動集合。由于E中活動按結(jié)束時間的非減序列排列,故活動1具有最早的完成時間。首先證明活動安排問題有一個最優(yōu)解以貪心選

18、擇開始,即該最優(yōu)解中包含活動1。設(shè)是所給的活動安排問題的一個最優(yōu)解,且A中活動也按結(jié)束時間非減序排序,A中的第一個活動是活動k。若k=1,則A就是以貪心選擇開始的最優(yōu)解;若k>1,則設(shè)。由于f1fk,且A中活動是相容的。又由于B中活動個數(shù)與A中活動個數(shù)相同,且A是最優(yōu)的,故B也是最優(yōu)的。由此可見,此貪心策略能得到最優(yōu)解。</p><p>  由于貪心算法解決安排問題要考慮么個活動的結(jié)束時間,所以先將活動按照

19、結(jié)束時間長短進行遞增排序。本貪心算法在處理非減序排列活動隊列時可以達到極高的效率。</p><p>  例:設(shè)待安排的11個活動的開始時間和結(jié)束時間按結(jié)束時間的非減序排列如下:</p><p>  表1 已排序活動安排</p><p>  貪心算法的計算過程如下圖所示。圖中每行相應(yīng)于算法的一次迭代。陰影長條表示的活動是已選入集合A的活動,而空白長條表示的活動是當前

20、正在檢查相容性的活動。</p><p>  圖2貪心算法的計算過程圖</p><p>  若被檢查的活動i的開始時間Si小于最近選擇的活動j的結(jié)束時間fi,則不選擇活動i,否則選擇活動i加入集合A中。</p><p><b>  3.4 算法結(jié)果</b></p><p>  若所需安排的活動為:</p>&

21、lt;p><b>  表2 活動安排</b></p><p>  3.4.1 實驗結(jié)果</p><p><b>  圖3 運行結(jié)果</b></p><p>  3.4.2 結(jié)果分析</p><p>  首先對以上數(shù)據(jù)以結(jié)束時間遞增順序進行排序得到以下隊列:</p><p

22、>  表3 對數(shù)據(jù)以結(jié)束時間遞增順序進行排序得到的隊列</p><p>  然后按照貪心算法取結(jié)束時間提前的活動以為后續(xù)活動提供更多時間,同時在保證選擇的活動的結(jié)束時間提前還要保證該活動與前一個活動相容。依次選擇的活動為2、4、8、10。</p><p><b>  3.5 算法分析</b></p><p>  3.5.1 關(guān)鍵代碼及解釋

23、</p><p>  void greedySelect(int n)//活動的貪心選擇 </p><p><b>  {</b></p><p>  a[num[1]]=true;</p><p><b>  int j=1;</b></p><p>  for(int i

24、=2;i<=n;i++)</p><p>  if(s[i]>=f[j])</p><p><b>  {</b></p><p>  a[num[i]]=true;</p><p><b>  j=i;</b></p><p><b>  }</

25、b></p><p><b>  else</b></p><p>  a[num[i]]=false; </p><p><b>  }</b></p><p>  這是整個貪心算法的核心,一個for循環(huán),根據(jù)已經(jīng)選擇的貪心策略,對活動進行選擇,其中布爾型數(shù)組a[]用與保存活動是否被選

26、擇,若被選擇則保存為true,否則保存為false。</p><p>  void greedySort(int n)//將活動按結(jié)束時間遞增排序 </p><p><b>  {</b></p><p>  int i,j,m;</p><p>  for(i=1;i<=n;i++)</p><

27、;p>  for(j=i;j<=n-1;j++)</p><p>  if(f[j]>f[j+1])</p><p><b>  {</b></p><p><b>  m=f[j];</b></p><p>  f[j]=f[j+1];</p><p>&

28、lt;b>  f[j+1]=m;</b></p><p><b>  m=s[j];</b></p><p>  s[j]=s[j+1];</p><p><b>  s[j+1]=m;</b></p><p><b>  m=num[j];</b></

29、p><p>  num[j]=num[j+1];</p><p>  num[j+1]=m;</p><p><b>  }</b></p><p><b>  }</b></p><p>  這是一個排序函數(shù),這是也算法的主要部分,因為此貪心算法的貪心策略為:選擇結(jié)束時間最早

30、的活動;所以為了讓核心算法更簡便更容易進行,首先對活動按結(jié)束時間遞增排序。主要是通過冒泡排序。</p><p>  3.5.2 算法流程圖</p><p>  核心算法流程圖如圖4所示:</p><p><b>  圖4 算法流程圖</b></p><p>  3.5.3 時間復雜度分析</p><p

31、>  貪心算法的效率極高,當輸入的活動已按結(jié)束時間的非減序排列,算法只需O(n)的時間安排n個活動,使最多的活動能相容地使用公共資源。如果所給出的活動未按非減序排列,只需要對隊列進行遞增排序,最簡只要用O(nlogn)的時間。</p><p><b>  4 實驗個人小結(jié)</b></p><p>  4.1總體實驗分析總結(jié)</p><p>

32、;  可以看出,在解決一個活動安排的問題是,只需要兩個步驟。一、對活動隊列進行排序,二、用貪心算法對隊列進行安排。運用貪心算法只要很少的時間便能實現(xiàn)地問題的解決。貪心算法貪心算法并不總能求得問題的整體最優(yōu)解。但對于活動安排問題,貪心算法r卻總能求得的整體最優(yōu)解。所以對于某些問題貪心算法可以給出極漂亮的解決。</p><p>  4.2 個人經(jīng)驗總結(jié)</p><p><b>  4

33、.2.1 收獲</b></p><p>  通過對活動安排問題的分析和最終解決這個問題,我確實學到了不少東西。在這個過程中,我了解到貪心算法貪心算法并不總能求得問題的整體最優(yōu)解。但對于活動安排問題,貪心算法r卻總能求得的整體最優(yōu)解。所以對于某些問題貪心算法可以給出極漂亮的解決。不僅如此,我還知道,不同的貪心選擇策略會導致不同的結(jié)果,而結(jié)果可能是最優(yōu)也可能不是最優(yōu)的,使我進一步了解了貪心算法;</

34、p><p>  這次課程設(shè)計更多的收獲是:C語言是計算機程序語言的基礎(chǔ)語言,內(nèi)容是比較簡單,但它的實踐操作還是比較強的,平時上機課較少,空閑時間又沒想過去編程,通過這次課程設(shè)計,每一步的實踐操作,提高了自我動手編程的能力,將在課本中許多學到的知識和很多想法都在編程過程中一一實踐。</p><p><b>  4.2.2 不足</b></p><p>

35、;  因為這次是一個人做一個題目,所以在選題方面也會偏向簡單一點的,這對于課程設(shè)計鍛煉個人編程能力的效果大打折扣。其次,因為是單人編程,雖然不用和別人討論,有想法就寫上去,但是少了討論,就很難找到會比自己想法更好更簡單的方法,也不能鍛煉到自己的團隊合作能力,這對于以后參加較大型項目開發(fā)所需的團隊合作能力鍛煉有一定的不好,所以,個人覺得,不管簡單還是難,如果可以,團隊運行是最好的。</p><p>  個人覺得,這

36、個課程設(shè)計最不好的地方就是缺少對照的貪心策略。本來是有想到要選擇其他貪心策略(比如以選擇最早開始的活動的策略、以選擇活動持續(xù)時間最短的策略等等)進行比較實驗的,但是因為自己怕麻煩,所以沒有這樣做,這是非常不好的,這使得這個課程設(shè)計顯得比較平凡,特色不大。</p><p>  我覺得我對C語言的掌握還是不夠熟悉的,因為在這次編程中沒能用到比較高級的數(shù)據(jù)結(jié)構(gòu)(比如棧,隊列等等),只是用C語言的一些較為簡單的基礎(chǔ)語法等

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論