算法設(shè)計(jì)與分析蠻力法(已修改)
2025-01-20 15:47 本頁面
【正文】 算法分析與設(shè)計(jì) 1 蠻力法 算法分析與設(shè)計(jì) 2 蠻力法 Brute Force ? 蠻力法（枚舉法、窮舉法，暴力法）要求設(shè)計(jì)者找出所有可能的方法，然后選擇其中的一種方法，若該方法不可行則試探下一種可能的方法。 ? 蠻力法 是一種直接解決問題的方法，常常直接基于問題的描述和所設(shè)計(jì)的概念定義。 ? “ 力 ” －－指計(jì)算機(jī)的能力，而不是人的智力。 ? 蠻力法常常是最容易應(yīng)用的方法。 – 求 an（ n為非負(fù)整數(shù)） – 用連續(xù)整數(shù)檢測算法計(jì)算 GCD（ m,n） 算法分析與設(shè)計(jì) 3 蠻力法 Brute Force ? 蠻力法不是一個(gè)最好的算法（巧妙和高效的算法很少出自蠻力），但當(dāng)我們想不出更好的辦法時(shí)，它也是一種有效的解決問題的方法。 ? 它可能是惟一一種幾乎什么問題都能解決的一般性方法，常用于一些非?；尽⒌质种匾乃惴?，比如計(jì)算 n個(gè)數(shù)字的和，求一個(gè)列表的最大元素等等。 算法分析與設(shè)計(jì) 4 蠻力法的優(yōu)點(diǎn) ? 邏輯清晰，編寫程序簡潔 ? 對(duì)于一些重要的問題 （比如：排序、查找、矩陣乘法和字符串匹配） ，可以產(chǎn)生一些合理的算法 ? 解決問題的實(shí)例很少時(shí)，可以花費(fèi)較少的代價(jià) ? 可以解決一些小規(guī)模的問題（使用優(yōu)化的算法沒有必要，而且某些優(yōu)化算法本身較復(fù)雜） ? 可以作為其他高效算法的衡量標(biāo)準(zhǔn) 算法分析與設(shè)計(jì) 5 使用蠻力法的幾種情況 ? 搜索所有的解空間 ? 搜索所有的路徑 ? 直接計(jì)算 ? 模擬和仿真 算法分析與設(shè)計(jì) 6 比較熟悉的蠻力法應(yīng)用 ? 選擇排序和起泡排序 – 選擇排序： 每趟排序在當(dāng)前待排序序列中選出關(guān)鍵碼最小的記錄，添加到有序序列中。 – 起泡排序：兩兩比較相鄰記錄關(guān)鍵碼，如果反序則交換，直到?jīng)]有反序的記錄為止。 ? 順序查找和蠻力字符串匹配 – 順序查找：從線性表的一端向另一端逐個(gè)將關(guān)鍵碼與給定值進(jìn)行比較，若相等，則查找成功，給出該記錄在表中的位置；若整個(gè)表檢測完仍未找到與給定值相等的關(guān)鍵碼，則查找失敗，給出失敗信息。 – 蠻力字符串匹配：即樸素模式串匹配 算法分析與設(shè)計(jì) 7 根據(jù)問題中的條件將可能的情況一一列舉出來 ， 逐一嘗試從中找出滿足問題條件的解 。 但有時(shí)一一列舉出的情況數(shù)目很大 ， 如果超過了我們所能忍受的范圍 ， 則需要進(jìn)一步考慮 ， 排除一些明顯不合理的情況 ， 盡可能減少問題可能解的列舉數(shù)目 。 用蠻力法解決問題 ， 通?？梢詮膬蓚€(gè)方面進(jìn)行算法設(shè)計(jì)： 1） 找出枚舉范圍：分析問題所涉及的各種情況 。 2） 找出約束條件：分析問題的解需要滿足的條件 ， 并用邏輯表達(dá)式表示 。 蠻力法解題步驟 【 例 1】 百錢百雞問題。中國古代數(shù)學(xué)家張丘建在他的《 算經(jīng) 》 中提出了著名的 “ 百錢百雞問題 ” ：雞翁一，值錢五；雞母一，值錢三；雞雛三，值錢一；百錢買百雞，翁、母、雛各幾何 ? 算法設(shè)計(jì) 1： 通過對(duì)問題的理解，可能會(huì)想到列出兩個(gè)三元一次
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1