算法設計基本方法ppt課件-展示頁
2025-05-21 12:54本頁面
【正文】 36 7 87 94 40111415*13*14*12*13*11*12*10*11*9*10*0*1.II.II.II.II.II.II.II????????????????????????????????? ?? ? ! ! ! What happened?! 注意此公式 精確 成立 考察第 n步的誤差 nE|)1()1(||||| * 11* ?? ?????? nnnnn nInIIIE ||!. . . 01 En||En n ??? ?我們有責任改變。如果下雨的話，營長將命令彗星穿上野戰(zhàn)服到操場上去。如果操場上下雨，營長將下達另一個命令，這種命令每隔 76年才會出現(xiàn)一次。如果下雨的話，就讓士兵穿著野戰(zhàn)服列隊前往禮堂，這一罕見的現(xiàn)象將在那里出現(xiàn)。如果下雨的話，就在禮堂集合，我為他們放一部有關彗星的影片。 例：百雞問題（教材 p6） 特點：算法簡單，可讀性強，直觀易于理解和設計 適用范圍：解決“是否存在”或者“有多少種可能”問題 缺點：運算工作量巨大 改進方法：分析實際問題，縮小列舉范圍以減少運算量 軟肋：不能用以解決列舉量無限的問題 ,或列舉量非常大的問題 算法設計基本方法（ 2） ? 歸納法： ? 通過分析少量特殊情況，找出關系，得到結論 例：搏彩問題 這期彩票該買幾呢？ 第一期 3 十一 2 二 5 十二 1 三 6 十三 1 四 8 十四 0 五 9 十五 2 六 8 十六 2 七 7 十七 3 八 5 十八 4 九 5 十九 4 十 3 二十 4 根據(jù)曲線，買 5比較好 歸納法 特點：適用面廣，高效使用，常能解決許多實際問題 適用范圍：樣本空間有一定規(guī)律，多用于預測領域，數(shù)據(jù)難以獲得的工程計算科學計算等領域 缺點：歸納出的數(shù)學模型需要證明，且代碼實現(xiàn)不規(guī)范 改進方法：常采用不同歸納方法共同求解一個問題 軟肋：不能求解樣本空間過于零散的問題 算法設計基本方法（ 3） ? 遞推 ? 從已知的初始條件出發(fā)，逐次推出所要求的各中間結果和最后結果 特點：采用遞推關系式數(shù)學模型，理論正確性得到保證，由于遞推關系式來源于歸納，所以本質上屬于歸納法 適用范圍：數(shù)值計算等工程應用 缺點：需考慮數(shù)值計算中穩(wěn)定性問題，易產(chǎn)生蝴蝶效應 軟肋：無遞推關系式的問題不可解 NY BJ 遞推 據(jù)說，美軍 1910 年的一次部隊的命令傳遞是這樣的 : 營長對值班軍官 : 明晚大約 8點鐘左右，哈雷彗星將可能在這個地區(qū)看到，這種彗星每隔 76年才能看見一次。算法設計基本方法（ 1） ? 列舉法 (窮舉法 ): ? 指的是從可能的解的集合中一一枚舉各元素， 用題目給定的檢驗條件判定哪些是無用的，哪些是有用的。能使命題成立，即為其解。命令所有士兵著野戰(zhàn)服在操場上集合，我將向他們解釋這一罕見的現(xiàn)象。 值班軍官對連長 : 根據(jù)營長的命令，明晚 8點哈雷彗星將在操場上空出現(xiàn)。 連長對排長 : 根據(jù)營長的命令，明晚 8點，非凡的哈雷彗星將身穿野戰(zhàn)服在禮堂中出現(xiàn)。 排長對班長 : 明晚 8點，營長將帶著哈雷彗星在禮堂中出現(xiàn)，這是每隔 76年才有的事。 班長對士兵 : 在明晚 8點下雨的時候，著名的 76歲哈雷將軍將在營長的陪同下身著野戰(zhàn)服，開著他那“彗星”牌汽車，經(jīng)過操場前往禮堂。 造成這種情況的是 不穩(wěn)定的算法 /* unstable algorithm */ 迅速積累，誤差呈遞增走勢 可見初始的小擾動 80 1050|| ??? .E)1(11 11 nnnn InIInI ????? ??? 公式二： 注意此公式與公式一 在理論上 等價 。 11)1(1???? NINe N?NN INNeI ??????????? 11)1(121*可取 0* ?????? NNN IIEN ,時當6 3 2 1 2 0 5 60)1(113 6 7 8 7 9 4 40)1(21. . .. . .. . .. . .0 8 3 8 7 7 1 1 50)1(1110 7 7 3 5 1 7 3 20)1(1210 7 1 7 7 9 2 1 40)1(1310 6 6 8 7 0 2 2 00)1(1410 6 3 8 1 6 9 1 80)1(1510 4 2 7 4 6 2 3 3016116121*1*0*2*1*11*10*12*11*13*12*14*13*15*14*15.II.II.II.II.II.II.II.eI?????????????????????????????
教學課件相關推薦
鄂ICP備17016276號-1