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

下載本文檔

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

文檔簡介

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

2、/p><p>  專業(yè)班級 信息與計算科學(xué)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 時間復(fù)雜度分析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是相容的。也就是說,當(dāng)si>=fj或者sj>=fi時,活動i與活動j相容?;顒影才艈栴}就是要在所給的活動集合中選出最大的相容活動子集合。</p><p><b>  1.2 目的與任務(wù)</b></p><p>  利用貪心

9、算法的性質(zhì),通過選擇適當(dāng)?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è)計與分析(第二版) 王曉東 編著 清華大學(xué)出版社 2011</p><p>  [2] 標(biāo)準(zhǔn)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é)束時間遞增進(jìn)行排序,因為排序后,編寫貪心算法程序會變得十分簡潔。</p><p>  最后,在對所有活動進(jìn)行選擇完畢后,要程序中顯示選擇結(jié)果,以確實是否正確。</p><p><b>  2.2 特色</b></p><p>  本次編程,個人覺得最大的特色就是把貪心選擇算法程序和結(jié)果顯示程序分離開成單獨的模塊,這樣會使得貪心選擇

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

15、;p>  3 用貪心算法解決活動安排的問題的實驗及其結(jié)果分析</p><p>  3.1 貪心算法簡介</p><p>  貪心算法(又稱貪婪算法)是指,在對問題求解時,總是做出在當(dāng)前看來是最好的選擇。也就是說,不從整體最優(yōu)上加以考慮,他所做出的僅是在某種意義上的局部最優(yōu)解。貪心算法不是對所有問題都能得到整體最優(yōu)解,但對范圍相當(dāng)廣泛的許多問題他能產(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ù)學(xué)歸納法證明。事實上,設(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é)束時間長短進(jìn)行遞增排序。本貪心算法在處理非減序排列活動隊列時可以達(dá)到極高的效率。</p><p>  例:設(shè)待安排的11個活動的開始時間和結(jié)束時間按結(jié)束時間的非減序排列如下:</p><p>  表1 已排序活動安排</p><p>  貪心算法的計算過程如下圖所示。圖中每行相應(yīng)于算法的一次迭代。陰影長條表示的活動是已選入集合A的活動,而空白長條表示的活動是當(dāng)前

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é)束時間遞增順序進(jìn)行排序得到以下隊列:</p><p

22、>  表3 對數(shù)據(jù)以結(jié)束時間遞增順序進(jìn)行排序得到的隊列</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)選擇的貪心策略,對活動進(jìn)行選擇,其中布爾型數(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、的活動;所以為了讓核心算法更簡便更容易進(jìn)行,首先對活動按結(jié)束時間遞增排序。主要是通過冒泡排序。</p><p>  3.5.2 算法流程圖</p><p>  核心算法流程圖如圖4所示:</p><p><b>  圖4 算法流程圖</b></p><p>  3.5.3 時間復(fù)雜度分析</p><p

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

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

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

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

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

36、個課程設(shè)計最不好的地方就是缺少對照的貪心策略。本來是有想到要選擇其他貪心策略(比如以選擇最早開始的活動的策略、以選擇活動持續(xù)時間最短的策略等等)進(jìn)行比較實驗的,但是因為自己怕麻煩,所以沒有這樣做,這是非常不好的,這使得這個課程設(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)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論