算法設(shè)計(jì)與分析蠻力法-資料下載頁(yè)
2025-01-08 15:47本頁(yè)面
【正文】 ＝ ?輸出樣例： 3 算法分析與設(shè)計(jì) 25 搜索過(guò)程 ? 依次假設(shè) i號(hào)金幣是假的 ? 對(duì)稱量的記錄進(jìn)行比較，如果假設(shè)與所有的記錄都不矛盾，則有可能是假的 ? 如果可能的假金幣只有 1個(gè)，輸出他的編號(hào)，否則，輸出 0 算法分析與設(shè)計(jì) 26 Int jd( int j, int *s, char c) {//函數(shù)判斷假設(shè) j金幣是假的與稱量結(jié)果是否矛盾 //s是稱量結(jié)果，其第一個(gè)元素是左托盤中金幣的個(gè)數(shù)， c是稱量結(jié)果 m=2*s[0]。 for(i=f=1。i=mamp。amp。f。) if(s[i]==j) f=0。 else ++i。 if(!famp。amp。c==?=?||famp。amp。c!=?=?) return 0。 return 1。 } 算法分析與設(shè)計(jì) 27 int main() { int num[100][1000]。 char s[1000]。//輸入內(nèi)容 for(i=1,count=0。i=n。++i)//蠻力搜索所有可能 { for(j=0 。 jkamp。amp。 jd( i, num[j] , s[j]) 。 j++)。 if(jk) continue。 count++。 //count保存現(xiàn)已發(fā)現(xiàn)的個(gè)數(shù) if(count1) break。 //不止一枚假金幣 no=i。 } if(count!=1) printf(“0”)。 else printf(“%d”,no)。 } 算法分析與設(shè)計(jì) 28 例 5：用蠻力法解決凸包問(wèn)題 ? 凸包問(wèn)題： S是平面上的一個(gè)點(diǎn)集，封閉 S中所有頂點(diǎn)的最小凸多邊形，稱為 S的凸包。凸包問(wèn)題就是為一個(gè) n個(gè)點(diǎn)的集合構(gòu)造凸包的問(wèn)題。 ? 對(duì)于一個(gè) n個(gè)點(diǎn)集合中的兩個(gè)點(diǎn) pi和 pj，當(dāng)且僅當(dāng)該集合中的其他點(diǎn)都位于穿過(guò)這兩點(diǎn)的直線的同一邊時(shí)，它們的連線是該集合凸包邊界的一部分。 例 6 最近對(duì)問(wèn)題 找出一個(gè)包含 n個(gè)點(diǎn)的集合中距離最近的兩個(gè)點(diǎn)。 算法分析與設(shè)計(jì) 29 某地刑偵大隊(duì)對(duì)涉及六個(gè)嫌疑人的一樁疑案進(jìn)行分析： ?A、 B至少有一人作案； ?A、 E、 F三人中至少有兩人參與作案； ?A、 D不可能是同案犯； ?B、 C或同時(shí)作案，或與本案無(wú)關(guān)； ?C、 D中有且僅有一人作案； ?如果 D沒有參與作案，則 E也不可能參與作案。 試設(shè)計(jì)算法將作案人找出來(lái)。 練習(xí) 算法分析與設(shè)計(jì) 30 將 1,2...9共 9個(gè)數(shù)分成三組 ,分別組成三個(gè)三位數(shù) ,且使這三個(gè)三位數(shù)構(gòu)成 1:2:3的比例 ,試求出所有滿足條件的三個(gè)三位數(shù) Tip：如果我們不假思索地以每一個(gè)數(shù)位為枚舉對(duì)象，一位一位地去枚舉，枚舉次數(shù)就有 9９ 次，如果我們分別設(shè)三個(gè)數(shù)為 x,2x,3x，以 x為枚舉對(duì)象，窮舉的范圍就減少為 9３ ，在細(xì)節(jié)上再進(jìn)一步優(yōu)化，枚舉范圍就更少了。
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1