算法設(shè)計與分析蠻力法-wenkub
2023-01-23 15:47:06 本頁面
【正文】 、小雞的數(shù)量。 用蠻力法解決問題 ， 通常可以從兩個方面進(jìn)行算法設(shè)計： 1） 找出枚舉范圍：分析問題所涉及的各種情況 。 – 起泡排序：兩兩比較相鄰記錄關(guān)鍵碼，如果反序則交換，直到?jīng)]有反序的記錄為止。 ? 蠻力法常常是最容易應(yīng)用的方法。算法分析與設(shè)計 1 蠻力法 算法分析與設(shè)計 2 蠻力法 Brute Force ? 蠻力法（枚舉法、窮舉法，暴力法）要求設(shè)計者找出所有可能的方法，然后選擇其中的一種方法，若該方法不可行則試探下一種可能的方法。 – 求 an（ n為非負(fù)整數(shù)） – 用連續(xù)整數(shù)檢測算法計算 GCD（ m,n） 算法分析與設(shè)計 3 蠻力法 Brute Force ? 蠻力法不是一個最好的算法（巧妙和高效的算法很少出自蠻力），但當(dāng)我們想不出更好的辦法時，它也是一種有效的解決問題的方法。 ? 順序查找和蠻力字符串匹配 – 順序查找：從線性表的一端向另一端逐個將關(guān)鍵碼與給定值進(jìn)行比較，若相等，則查找成功，給出該記錄在表中的位置；若整個表檢測完仍未找到與給定值相等的關(guān)鍵碼，則查找失敗，給出失敗信息。 2） 找出約束條件：分析問題的解需要滿足的條件 ， 并用邏輯表達(dá)式表示 。 嘗試范圍： 由 題意給定共 100錢要買百雞 ， 若全買公雞最多買 100/5=20只 ， 顯然 x的取值范圍 1~20之間；同理 ， y的取值范圍在 1~33之間 ， z的取值范圍 在 1~100之間 。x=x+1) for(y=1。z=z+1) if(100==x+y+zamp。 for(x=1。y=y+1) { z=100xy。} } } 枚舉嘗試 20*33=660次 Z能被 3整除時，才會判斷“ 5*x+3*y+z/3=100 算法分析與設(shè)計 12 例 2 ? 求所有的三位數(shù)，它除以 11所得的余數(shù)等于它的三個數(shù)字的平方和。所求三位數(shù)必在以下數(shù)中： 100， 101， 102， 103， 110， 111， 112， 120， 121， 122， 130， 200， 201， 202， 211， 212， 220， 221， 300， 301， 310。 3） 第一次轉(zhuǎn)動的是 1， 2， 3， …… ， n號牢房； 第二次轉(zhuǎn)動的是 2， 4， 6， …… 號牢房； 第 i次轉(zhuǎn)動的是 i， 2i， 3i， 4i， …… 號牢 房 ， 是起點(diǎn)為 i， 公差為 i的等差數(shù)列 。 for (i=1。 i=n。 for (i=1。 問題分析： 轉(zhuǎn)動門鎖的規(guī)則可以有另一種理解，第一次轉(zhuǎn)動的 是編號為 1的倍數(shù)的牢房；第二次轉(zhuǎn)動的是編號為 2的倍數(shù)的牢 房；第三次轉(zhuǎn)動的是編號為 3的倍數(shù)的牢房； …… 則 獄吏問題是 一個關(guān)于因子個數(shù)的 問題。 2） 一個數(shù)的因子是沒有規(guī)律的 ， 只能從 1——n枚舉嘗試 。i++) { s=1。
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1