算法設(shè)計與分析答案屈婉玲

1、算法設(shè)計與分析答案屈婉玲【篇一：分金塊問題的解決思想和算法設(shè)計】s=txt> 摘 要：在日常生活中，分金塊問題是一個常見的問題，人們總是會面臨怎樣比較大小。才能利用一種最高效的算法選出其中最大和最小的金塊。本文給出了較為常用的兩種算法 蠻力法和分治法。關(guān)鍵詞：分金塊問題；蠻力法(非遞歸)；分治法；points gold bullion problem solving thought and algorithmdesignabstract: in daily life, points gold bullion is a common problem, people will always

2、face how to compare size. can use one of the mostefficient algorithm choose the maximum and minimum of the gold. this paper gives a more commonly used two kinds of algorithm, brute force method and partition method.keywords: points gold bullion problem; brute force method(non recursive); partition m

3、ethod;1 引言遞歸調(diào)用是一種特殊的嵌套調(diào)用，是某個函數(shù)調(diào)用自己，而不是另外一個函數(shù)。遞歸調(diào)用一種解決方案，一種是邏輯思想，將一個大工作分為逐漸減小的小工作，比如說一個和尚要搬50 塊石頭，他想，只要先搬走49 塊，那剩下的一塊就能搬完了，然后考慮那49 塊，只要先搬走48塊，那剩下的一塊就能搬完了，遞歸是一種思想,只不過在程序中，就是依靠函數(shù)嵌套這個特性來實現(xiàn)了。由于回溯法是對解空間的深度優(yōu)先搜索，因此在一般情況下可用遞歸函數(shù)來實現(xiàn)回溯法2 問題概述老板有 n 個金塊，希望最優(yōu)秀的雇員得到其中最重要的一塊，最差的雇員得到其中最輕的一塊。假設(shè)有一臺比較重量的儀器，如何用最少的比較次數(shù)找出最

4、重和最輕的金塊？理解金塊問題：以9 以內(nèi)的實例理解問題。金塊示例問題： 1. 最重的是那塊？用max 標記。2 . 最輕的是那塊？用min 標記。3 求解分金塊問題的常用算法3.1 蠻力法蠻力法，也稱窮舉法，是一種簡單而直接地解決問題的方法，常常直接基于問題的描述，因此，也是最容易應(yīng)用的方法。但是，用蠻力法設(shè)計的算法其時間性能往往是最低的，典型的指數(shù)時間算法一般都是通過蠻力搜索而得到的。即從第一塊開始查找，查找哪塊最重，哪塊最輕。算法設(shè)計：maxmin(float a,int n)max=a1;min=a1;for(i=2;i=n;i=i+1)if(maxai)max=aielse if(mi

5、nai)min=aireturn(max, min)step1 將所有金塊重量存于數(shù)組step2 將第一個金塊同時標記為最重和最輕的金塊step3 將第一個與后一個進行重量的比較，將更重的標記為max ，同時如果現(xiàn)階段最輕的比后者輕，那么將后者標記為min 。step4 依次進行比較，最重得到最重的和最輕的max min.3.2 分治法1 典型二分法思想：一種簡單的分治法。即當每次將比較大的一個問題一分為二，形成兩個較小的問題，再把每個較小問題一分為二，變?yōu)楦〉膬蓚€問題，直到得到容易解決的小問題為止，再解決所有小問題，然后把小問題的解逐層合并，得到原來大問題的解。2 用二分法如何解決金塊問題

6、？從兩個簡單實例談起：(1) 假設(shè)只有一個金塊，重10 克，則不需要比較輕重,最重者和最輕者是同一個金塊。即比較0 次。(2) 假設(shè)有 2 個金塊，一個重10 克，另一個重16 克，則需要比較1 次，可以把最重者和最輕者確定下來。(3) 當有多個金塊時(假設(shè)6 塊)，則用二分法對其分解，直到分解為(1 )或(2)的情形時，問題很容易解決。假設(shè) 6 個金塊重量如下(以找最輕金塊為例)：2 6 4 3 8 1一分為二(兩組)：【 2 6 4】 【 3 8 1 】一分為二(四組)：【 2 6】【4】【 3 8】【1】解較小子問題：24 3 1合并子問題解：2 1最終的解：13 用二分法解決金塊問題算

7、法設(shè)計：問題抽象、簡化為：在n 個元素的集合中尋找最大和最小值元素。(1)將集合一分為二，變?yōu)閮蓚€集合，目的是在較小的兩個集合中分別找最大、最小元素。(2)遞歸分解較小集合，直到每個集合中的元素個數(shù) < 2,然后找出小 集合的最大、最小元素。3 3) 合并(回溯)：自低向上把子問題的解合并，大元素中取最大者，小元素中取最小者，最后得到元問題的解。4 用二分法解決金塊問題算法描述：void maxmin(int i,int j,float fmax,float fmin)int mid;float lmax,lmin,rmax,rmin;if(i=j)fmax=ai;fmin=ai;els

8、e if(i=j-1)if(aiaj)fmax=aj;fmin=ai;elsefmax=ai;fmin=aj;elsemid=(i+j)/2;maxmin(i,mid,lmax,lmin);maxmin(mid+1,j,rmax,rmin);if(lmaxrmax)fmax=lmax;elsefmax=rmax;if(lminrmin)fmin=rmin;elsefmin=lmin;5 仿真實驗及其結(jié)果：在 eclipse3.5 環(huán)境下測試brute force method ，隨機輸入n=8 ;num=23,43,3,5,6,23,9,6 驗證 ,驗證結(jié)果max=43; min=3結(jié)果正確。

9、輸入 n=6; num=3,7,8,9,0,15 驗證 ;驗證結(jié)果max=15;min=0結(jié)果正確。表-1brute force method實驗輸入輸出參數(shù)設(shè)置由于蠻力算法是從第一個金塊開始逐一尋找，直到和第n 個金塊比較之后才結(jié)束，所以最后得到的必然是最重(max) 、最輕 (min) 的金塊.表 -2 partition method 實驗輸入輸出參數(shù)設(shè)置表 -2 貪心算法的時間復雜度分析分析蠻力法可以看出，比較操作maxai 和 mixai 是執(zhí)行頻次最高的關(guān)鍵語句。因此以這兩個語句執(zhí)行的總次數(shù)作為該算法執(zhí)行所需要的時間。最好情況下，金塊由輕到重排列，不需要進行minai 比較，而 m

10、axai 比較共需進行n-1 次 ,即可得到max 和 min; 最壞情況下，金塊由重到輕排列，還需要進行n-1 次 minai 比較，才能得到最終的min ，因此共進行2(n-1) 次比較。在平均情況下(概率平均)，ai 將有一半的時間比max 大，因此平均比較次數(shù)是3(n-1)/2 。所以算法時間復雜度為o(n).分析分治法可以看出，元素比較總次數(shù)作為maxmin 算法的時間復雜度度量指標，用t(n) 表示比較總次數(shù)，則可以推導出遞歸關(guān)系：t(n) 下界為 (3n/2)-25 結(jié)束語本文給出了兩種關(guān)于金塊問題的算法，分別是蠻力法和二分法。分析了其時間復雜度和占用空間等。總結(jié)了兩種算法的特點

11、及適用性。一般情況下，選擇二分法較為快速，但內(nèi)存消耗較大。參考文獻1 算法設(shè)計與分析王紅梅 清華大學出版社（2006-07 出版 ）2 算法設(shè)計與分析屈婉玲、劉田、張立昂清華大學出版社（2011-05 出版 ）3 java 核心技術(shù)（卷 1）: 基礎(chǔ)知識（原書第8 版 ） 昊斯特曼（horstmann gay s.）、 gary cornell 、葉乃文、 鄺勁筠 機械工業(yè)出版社（2008-06 出版 ）【篇二：b0301340s- 算法分析與設(shè)計-課程實驗教學大綱】s=txt> 課程編號：課內(nèi)總學時：b0301340s 48課程名稱：實驗學時：算法分析與設(shè)計8實驗類別： 通識基礎(chǔ) 學科

12、基礎(chǔ) 專業(yè)基礎(chǔ)專業(yè)一、實驗課程的性質(zhì)、目的和任務(wù)性質(zhì)：本實驗課程是軟件工程專業(yè)的專業(yè)基礎(chǔ)課，該實驗是理論課程的課內(nèi)上機實驗環(huán)節(jié)。目的：加深學生對算法設(shè)計的基本策略和主要方法的理解，培養(yǎng)學生針對具體的問題，選擇合適的數(shù)據(jù)結(jié)構(gòu)和設(shè)計結(jié)構(gòu)清晰、正確有效的算法的能力。任務(wù)：通過8 個課時的實驗，學生需要完成分治策略、動態(tài)規(guī)劃法、回溯法和密碼算法四個實驗內(nèi)容，掌握為實際問題設(shè)計合適的算法、以及結(jié)合程序設(shè)計語言加以具體實現(xiàn)的技能，鍛煉學生運用書本知識實際解決問題的能力，達到對所學算法思想理解深刻、舉一反三的目的。每位同學應(yīng)在實驗課前充分復習和理解課堂教學內(nèi)容，明確實驗目的和任務(wù)，對實驗題目進行分析，掌握實

13、驗原理及過程，選擇有效的算法編程實現(xiàn)，并進行充分測試。在實驗中通過獨立思考、與同學討論、老師輔導答疑相結(jié)合的方法完成相應(yīng)的實驗內(nèi)容。二、實驗內(nèi)容、學時分配及基本要求三、考核及實驗報告（一）考核本課程實驗的考核包括：有無缺勤、有無事先準備程序代碼、實驗課上是否認真做實驗、程序代碼和實驗結(jié)果是否正確、實驗報告的撰寫情況等幾個方面。實驗課成績由平時實驗課的課堂表現(xiàn)、源代碼及實驗報告內(nèi)容綜合評定。實驗課成績記入該課程的平時成績，約占課程總成績的15% 。（二）實驗報告實驗報告的內(nèi)容：實驗名稱、實驗目的、實驗任務(wù)、實驗內(nèi)容（包括系統(tǒng)分析、概要設(shè)計和詳細設(shè)計）、實驗過程描述（包括核心算法和算法分析、程序代

14、碼、測試用例、實驗結(jié)果分析）、實驗小結(jié)（包括實驗過程中遇到的問題及體會）。實驗報告的要求：實驗報告以文本形式遞交。實驗報告要求書寫規(guī)范、內(nèi)容完整、文字通順、圖表清晰。四、主要儀器設(shè)備硬件：微型計算機。軟件： windows 操作系統(tǒng)，visual c+ 6.0 。五、教材及參考書教材1 陳慧南算法設(shè)計與分析 c+ 語言描述（第二版）北京：電子工業(yè)出版社，2012 參考書2 王曉東 . 計算機算法分析與設(shè)計. 北京：電子工業(yè)出版社，2001年.3 thomas h.cormen, charles e.leiserson, ronald l.rivest, clifford stein 著 . 算

15、法導論. 潘金貴，顧鐵成，李成法，葉懋譯 . 北京：機械工業(yè)出版社，2007 年 .4 robert sedgewick, kevin wayne 著 .算法（第4 版） . 謝路云 譯 .北京：人民郵電出版社，2013 年 .5 jon kleinberg, eva tardos 著 . 算法設(shè)計. 張立昂，屈婉玲譯 . 北京：清華大學出版社，2007 年 .6 sara baase ， allen van gelder 著 . computer algorithms ， introduction to design and analysis. 北京： higher education pr

16、ess ， 2001 年 .執(zhí)筆人：張怡婷審核人：陳志實驗院長：陳丹偉編寫完成時間：2014.1.6附件： 設(shè)計性實驗教學大綱一、實驗目的通過構(gòu)造一個簡單的rsa 公開密鑰系統(tǒng)，使學生熟悉非對稱密鑰系統(tǒng)的工作流程，理解加、解密算法的基本原理，能夠編程實現(xiàn)生成正確的公有/私有密鑰對、用公有密鑰對明文進行加密并用私有密鑰對密文進行解密的功能，并了解該rsa 算法在實際系統(tǒng)中的應(yīng)用。在該配套實驗環(huán)節(jié)中，達到進一步鞏固和加強學生對算法分析與設(shè)計課程相關(guān)知識點的掌握和理解的目的。二、設(shè)計內(nèi)容1. 根據(jù)題意和加、解密基本原理，設(shè)計具體的算法流程。2. 完成 rsa 密鑰系統(tǒng)的具體實現(xiàn)，使之能夠生成正確的公

17、有密鑰和私有密鑰，并能用公有密鑰對明文進行加密、用私有密鑰對密文進行解密。3. 在生成公開/私有密鑰對的過程中，培養(yǎng)學生借助已有的成熟算法并加以變換來解決實際應(yīng)用中新問題的能力。4. 進一步鍛煉學生編程的方法和技巧，提高學生編制清晰、合理、可讀性好的應(yīng)用程序來實現(xiàn)算法的能力。三、實驗要求要求了解密碼學中加/解密的基本原理，掌握數(shù)論的基本知識，理解非對稱密碼體制的著名代表rsa 加密算法的工作原理和流程，能夠設(shè)計并實現(xiàn)一個簡單的rsa 公開密鑰加解密系統(tǒng)。四、實驗報告該課程的實驗是理論課程學習的重要實踐環(huán)節(jié)，實驗報告應(yīng)包括以下幾個部分的主要內(nèi)容：一、實驗目的和要求二、實驗環(huán)境硬件：微型計算機和打

18、印機。軟件： windows 2000 以上操作系統(tǒng)；visual c+ 6.0 編程環(huán)境。三、實驗原理及內(nèi)容主要包括：1 、對本次實驗的題目更為深入的理解、對實驗原理和步驟的清晰闡述等。2 、對實驗內(nèi)容、實驗過程以及源程序代碼的詳細記錄。（應(yīng)包括全部實驗內(nèi)容的源代碼、測試數(shù)據(jù)及運行結(jié)果、實驗相關(guān)結(jié)論。對代碼中關(guān)鍵行要注釋。）四、實驗小結(jié)主要包括：在編程、調(diào)試、測試過程中遇到的問題及解決方法、本次實驗的心得體會、進一步改進的設(shè)想等。五、思考題1. 由于實際應(yīng)用中rsa 算法通常需要選擇大質(zhì)數(shù)進行運算，因此實際系統(tǒng)中如何實現(xiàn)大數(shù)運算的功能，對超出整型變量表示范圍的數(shù)進行運算？2. 如何自行實現(xiàn)隨

19、機生成質(zhì)數(shù)的功能？如何快速判斷一個數(shù)是否質(zhì)數(shù)？ 3. rsa 加密的安全性是如何保證的？4. rsa 加密算法的優(yōu)缺點都有哪些？5. 針對 rsa 算法可能有哪些攻擊方法？6. 如何將 rsa 算法用于數(shù)字簽名？執(zhí)筆人：張怡婷審核人：陳志編寫完成時間：2014 年 2 月 2 日實驗院長：章韻【篇三：浙教版高一算法與程序設(shè)計】/p> 課時）一、設(shè)計思想本課以浙江省普通高中新課程實驗信息技術(shù)學科教學指導意見為指導，在高中一年級下學期算法與程序設(shè)計選修課階段開展教學。本課以培養(yǎng)學生能力為目標，突出學生觀察、實踐、應(yīng)用能力，領(lǐng)悟生活中的相關(guān)應(yīng)用。二、教材分析1 高中信息技術(shù)課程標準提出信息技術(shù)

20、課的基本理念之一是強調(diào)問題的解決，倡導運用信息技術(shù)進行創(chuàng)新實踐。在課程設(shè)置上，算法與程序設(shè)計可在高一下學期選修，其中“對分查找 ”算法是學生技能提升的重要一課；在信息技術(shù)學科教學指導意見中“對分查找”算法要求學生了解對分查找的概念、初步掌握該算法，重點是對算法分析，以講授法為主，適當讓學生討論與體驗。2 對分查找算法由理解該算法概念、流程圖分析、算法描述、程序?qū)崿F(xiàn)組成，在“查找 ”模塊中是重點要求部分；3 初中階段未學習過相關(guān)知識，故這部分作為全新內(nèi)容學習。三、學情分析1 通過信息技術(shù)基礎(chǔ)必修課信息的加工 算法與編程、算法與程序設(shè)計選修課的初步學習，學生已經(jīng)對算法有一定了解，能夠應(yīng)用流程圖和偽

21、碼對一些簡單算法進行分析，能夠初步應(yīng)用vb 編寫簡單應(yīng)用程序、實現(xiàn)算法。2 根據(jù)信息技術(shù)學科教學指導意見，算法與程序設(shè)計可按以下順序教學：先上“算法和算法表示”，再上 “面向?qū)ο蟪绦蛟O(shè)計的基本知識”，接下來進行“算法實例的程序?qū)崿F(xiàn)”、 “算法實例”、 “ vb程序設(shè)計初步”穿插學習。學生在此可能會遇到來自于對分查找法的分析、查找效率以及程序?qū)崿F(xiàn)的困難；3 學生學習此部分，會自然而然地把“對分查找”和 “順序查找”聯(lián)系起來，因為順序查找易于實現(xiàn)，相比之下，對分法稍稍有些困難；也有學生可能會采取先掌握流程再用自然語言實現(xiàn)、進而用程序?qū)崿F(xiàn)的方法。對此，在教學上可通過流程圖的演示幫助學生理解對分查找比

22、順序查找高效。四、教學目標知識性目標：1. 了解并熟悉對分查找算法的概念、能列舉現(xiàn)實生活中的應(yīng)用實例；2. 能解釋對分查找中數(shù)字之間的邏輯聯(lián)系，明確對分查找算法相對于順序查找法的優(yōu)勢；3. 具備知識遷移能力，發(fā)現(xiàn)對分查找算法的現(xiàn)實應(yīng)用，總結(jié)對分查找的規(guī)律，能把學習所得應(yīng)用于現(xiàn)實生活中。技能性目標：1. 能通過流程圖，剖析對分查找算法的原理；2. 能使用自然語言表達對分查找算法，并能應(yīng)用信息技術(shù)與他人交流自己對此部分知識的理解；3. 能熟練 “對分查找算法”的程序?qū)崿F(xiàn)，有效利用此算法解決實際問題。 情感、態(tài)度、價值觀目標：要求學生從“了解理解實現(xiàn)應(yīng)用”對分查找算法的過程，獲得對該算法的感性認識，

23、表達對分查找算法的學習體驗，養(yǎng)成追求算法高效率、增加程序效率意識、并領(lǐng)悟?qū)Ψ植檎宜惴▽τ诂F(xiàn)實應(yīng)用的價值。五、重點難點重點：分析對分查找算法難點：程序?qū)崿F(xiàn)、知識遷移六、教學策略與手段以流程圖的完善為線索，以生動的、較有價值的實例穿插在各個教學環(huán)節(jié)，輔助學生理解以提高效率為目標，讓學生在應(yīng)用中體會順序查找與對分查找的效率采用比較、分組討論、探究教學法綜合運用的教學手段七、課前準備1 學生的學習準備：掌握查找的概念，預習對分查找法。2 教師的教學準備：cctv “幸運52” 中猜價格游戲的片段；對分查找算法的演示材料和數(shù)據(jù)。3教學環(huán)境的設(shè)計與布置：給學生分組( 4-6 人一組)；八、教學過程播放 c

24、ctv “幸運 52”中猜價格游戲的片段。 猜一件物品的價格。競猜者說一個價格，再根據(jù)主持人提示價格的高低修改下次猜測的范圍 小組合作模仿視頻片斷，親身體驗猜價格技巧。由同學研究并指出如何根據(jù)高低的提示做出相應(yīng)策略？分組討論如果按照“順序查找”策略來猜價格，情況會怎么樣？ 切入正題今天我們要學習的就是類似于視頻中猜價格策略的一種查找算法 對分查找算法，它還有兩種叫法：折半查找法、二分查找法。它是在有序的數(shù)字系列中查找一個數(shù)字，可以先確定待查數(shù)字所在的范圍，然后逐步縮小范圍直到找到或找不到記錄。 學生根據(jù)已學知識完成聲明數(shù)組和賦值，因為此數(shù)組不僅在一個過程中有效，故要以通用里聲明dim d(1

25、to 10) as integer private sub form_load()dim i as integer i=1do while i=10d(i) = val(inputbox( 請按順序輸入數(shù)組中各元素的值，第i 個： )list1.additem (str(d(i)i=i+1 loop end sub我們需要用到的變量：被查找的數(shù)key (由用戶輸入)、最大數(shù)的下標 high 、最小數(shù)的下標low 、位于數(shù)字系列中央的數(shù)字為第mid ，其中 mid=fix (low+high ) /2 ,應(yīng)滿足 low w high。 學生完成對變量的聲明和賦值 dim key as integer dim high asinteger dim low as integer dim mid as integerhigh=10:low=1mid=fix(high+low)/2 回顧 fix() 函數(shù)用法 key=val(text1.text) 回顧 val() 函數(shù)用法 結(jié)合猜價格策略 先把 key 與第 mid 元素進行比較，最好的情況：key=d(mid) ，這樣可以直接