《算法設(shè)計(jì)與分析》蠻力法.ppt
《《算法設(shè)計(jì)與分析》蠻力法.ppt》由會(huì)員分享,可在線閱讀,更多相關(guān)《《算法設(shè)計(jì)與分析》蠻力法.ppt(30頁(yè)珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
算法分析與設(shè)計(jì),1,蠻力法,算法分析與設(shè)計(jì),2,蠻力法BruteForce,蠻力法(枚舉法、窮舉法,暴力法)要求設(shè)計(jì)者找出所有可能的方法,然后選擇其中的一種方法,若該方法不可行則試探下一種可能的方法。蠻力法是一種直接解決問(wèn)題的方法,常常直接基于問(wèn)題的描述和所設(shè)計(jì)的概念定義。“力”指計(jì)算機(jī)的能力,而不是人的智力。蠻力法常常是最容易應(yīng)用的方法。求an(n為非負(fù)整數(shù))用連續(xù)整數(shù)檢測(cè)算法計(jì)算GCD(m,n),算法分析與設(shè)計(jì),3,蠻力法BruteForce,蠻力法不是一個(gè)最好的算法(巧妙和高效的算法很少出自蠻力),但當(dāng)我們想不出更好的辦法時(shí),它也是一種有效的解決問(wèn)題的方法。它可能是惟一一種幾乎什么問(wèn)題都能解決的一般性方法,常用于一些非?;尽⒌质种匾乃惴?,比如計(jì)算n個(gè)數(shù)字的和,求一個(gè)列表的最大元素等等。,算法分析與設(shè)計(jì),4,蠻力法的優(yōu)點(diǎn),邏輯清晰,編寫程序簡(jiǎn)潔對(duì)于一些重要的問(wèn)題(比如:排序、查找、矩陣乘法和字符串匹配),可以產(chǎn)生一些合理的算法解決問(wèn)題的實(shí)例很少時(shí),可以花費(fèi)較少的代價(jià)可以解決一些小規(guī)模的問(wèn)題(使用優(yōu)化的算法沒(méi)有必要,而且某些優(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è)表檢測(cè)完仍未找到與給定值相等的關(guān)鍵碼,則查找失敗,給出失敗信息。蠻力字符串匹配:即樸素模式串匹配,算法分析與設(shè)計(jì),7,根據(jù)問(wèn)題中的條件將可能的情況一一列舉出來(lái),逐一嘗試從中找出滿足問(wèn)題條件的解。但有時(shí)一一列舉出的情況數(shù)目很大,如果超過(guò)了我們所能忍受的范圍,則需要進(jìn)一步考慮,排除一些明顯不合理的情況,盡可能減少問(wèn)題可能解的列舉數(shù)目。用蠻力法解決問(wèn)題,通??梢詮膬蓚€(gè)方面進(jìn)行算法設(shè)計(jì):1)找出枚舉范圍:分析問(wèn)題所涉及的各種情況。2)找出約束條件:分析問(wèn)題的解需要滿足的條件,并用邏輯表達(dá)式表示。,蠻力法解題步驟,【例1】百錢百雞問(wèn)題。中國(guó)古代數(shù)學(xué)家張丘建在他的算經(jīng)中提出了著名的“百錢百雞問(wèn)題”:雞翁一,值錢五;雞母一,值錢三;雞雛三,值錢一;百錢買百雞,翁、母、雛各幾何?算法設(shè)計(jì)1:通過(guò)對(duì)問(wèn)題的理解,可能會(huì)想到列出兩個(gè)三元一次方程,去解這個(gè)不定解方程,就能找出問(wèn)題的解。這確實(shí)是一種辦法,但這里我們要用“懶惰”的枚舉策略進(jìn)行算法設(shè)計(jì):設(shè)x,y,z分別為公雞、母雞、小雞的數(shù)量。嘗試范圍:由題意給定共100錢要買百雞,若全買公雞最多買100/5=20只,顯然x的取值范圍120之間;同理,y的取值范圍在133之間,z的取值范圍在1100之間。約束條件:x+y+z=100且5*x+3*y+z/3=100,算法分析與設(shè)計(jì),9,算法1如下:main()intx,y,z;for(x=1;x=20;x=x+1)for(y=1;y=34;y=y+1)for(z=1;z=100;z=z+1)if(100=x+y+z,枚舉嘗試20*34*100=68000次,算法分析與設(shè)計(jì),10,算法設(shè)計(jì)2:在公雞(x)、母雞(y)的數(shù)量確定后,小雞的數(shù)量z就固定為100-x-y,無(wú)需再進(jìn)行枚舉了此時(shí)約束條件只有一個(gè):5*x+3*y+z/3=100算法2如下:,算法分析與設(shè)計(jì),11,main()intx,y,z;for(x=1;x=20;x=x+1)for(y=1;y=33;y=y+1)z=100-x-y;if(z%3=0,枚舉嘗試20*33=660次,Z能被3整除時(shí),才會(huì)判斷“5*x+3*y+z/3=100,算法分析與設(shè)計(jì),12,例2,求所有的三位數(shù),它除以11所得的余數(shù)等于它的三個(gè)數(shù)字的平方和。解題思路:三位數(shù)只有900個(gè),可用枚舉法解決,枚舉時(shí)可先估計(jì)有關(guān)量的范圍,以縮小討論范圍,減少計(jì)算量。,解:設(shè)這個(gè)三位數(shù)的百位、十位、個(gè)位的數(shù)字分別為x,y,z。由于任何數(shù)除以11所得余數(shù)都不大于10,所以x2+y2+z210,從而1x3,0y3,0z3。所求三位數(shù)必在以下數(shù)中:100,101,102,103,110,111,112,120,121,122,130,200,201,202,211,212,220,221,300,301,310。不難驗(yàn)證只有100,101兩個(gè)數(shù)符合要求。,例3獄吏問(wèn)題某國(guó)王對(duì)囚犯進(jìn)行大赦,讓一獄吏n次通過(guò)一排鎖著的n間牢房,每通過(guò)一次,按所定規(guī)則轉(zhuǎn)動(dòng)n間牢房中的某些門鎖,每轉(zhuǎn)動(dòng)一次,原來(lái)鎖著的被打開,原來(lái)打開的被鎖上;通過(guò)n次后,門鎖開著的,牢房中的犯人放出,否則犯人不得獲釋。轉(zhuǎn)動(dòng)門鎖的規(guī)則是這樣的,第一次通過(guò)牢房,要轉(zhuǎn)動(dòng)每一把門鎖,即把全部鎖打開;第二次通過(guò)牢房時(shí),從第二間開始轉(zhuǎn)動(dòng),每隔一間轉(zhuǎn)動(dòng)一次;第k次通過(guò)牢房,從第k間開始轉(zhuǎn)動(dòng),每隔k-1間轉(zhuǎn)動(dòng)一次;問(wèn)通過(guò)n次后,哪些牢房的鎖仍然是打開的?,算法分析與設(shè)計(jì),15,算法設(shè)計(jì)1:1)一維數(shù)組an記錄n個(gè)鎖的狀態(tài)1:被鎖上0:被打開2)對(duì)i號(hào)鎖的一次開關(guān)鎖可以轉(zhuǎn)化為算術(shù)運(yùn)算:ai=1-ai。3)第一次轉(zhuǎn)動(dòng)的是1,2,3,n號(hào)牢房;第二次轉(zhuǎn)動(dòng)的是2,4,6,號(hào)牢房;第i次轉(zhuǎn)動(dòng)的是i,2i,3i,4i,號(hào)牢房,是起點(diǎn)為i,公差為i的等差數(shù)列。4)不做其它的優(yōu)化,用蠻力法通過(guò)循環(huán)模擬獄吏的開關(guān)鎖過(guò)程,最后當(dāng)?shù)趇號(hào)牢房對(duì)應(yīng)的數(shù)組元素ai為0時(shí),該牢房的囚犯得到大赦。,算法分析與設(shè)計(jì),16,算法1如下:input(n);/輸入na=newint(n+1);for(i=1;i=n;i+)ai=1;for(i=1;i=n;i+)for(j=i;j=n;j=j+i)ai=1-ai;for(i=1;i=n;i+)if(ai=0)print(i,”isfree.”);算法分析:以一次開關(guān)鎖計(jì)算,算法的時(shí)間復(fù)雜度為n(1+1/2+1/3+1/n)=O(nlogn)。,問(wèn)題分析:轉(zhuǎn)動(dòng)門鎖的規(guī)則可以有另一種理解,第一次轉(zhuǎn)動(dòng)的是編號(hào)為1的倍數(shù)的牢房;第二次轉(zhuǎn)動(dòng)的是編號(hào)為2的倍數(shù)的牢房;第三次轉(zhuǎn)動(dòng)的是編號(hào)為3的倍數(shù)的牢房;則獄吏問(wèn)題是一個(gè)關(guān)于因子個(gè)數(shù)的問(wèn)題。令d(n)為自然數(shù)n的因子個(gè)數(shù),這里不計(jì)重復(fù)的因子,如4的因子為1,2,4共三個(gè)因子,而非1,2,2,4。則d(n)有的為奇數(shù),有的為偶數(shù),見下表:表1編號(hào)與因數(shù)個(gè)數(shù)的關(guān)系,算法分析與設(shè)計(jì),18,數(shù)學(xué)模型1:上表中的d(n)有的為奇數(shù),有的為偶數(shù),由于牢房的門開始是關(guān)著的,這樣編號(hào)為i的牢房,所含1i之間的不重復(fù)因子個(gè)數(shù)為奇數(shù)時(shí),牢房最后是打開的,反之,牢房最后是關(guān)閉的。,算法分析與設(shè)計(jì),19,算法設(shè)計(jì)2:1)算法應(yīng)該是求出每個(gè)牢房編號(hào)的不重復(fù)的因子個(gè)數(shù),當(dāng)它為奇數(shù)時(shí),這里邊的囚犯得到大赦。2)一個(gè)數(shù)的因子是沒(méi)有規(guī)律的,只能從1n枚舉嘗試。算法2如下:input(n);for(i=1;i=n;i+)s=1;for(j=2;j=i;j=j+)if(ij=0)s=s+1;if(s2=1)print(i,”isfree.”);,算法分析與設(shè)計(jì),20,算法分析:算法1中獄吏開關(guān)鎖的主要操作是ai=1-ai;共執(zhí)行了n*(1+1/2+1/3+1/n)次,時(shí)間近似為復(fù)雜度為O(nlogn)。使用了n個(gè)空間的一維數(shù)組。算法2沒(méi)有使用輔助空間,但由于求一個(gè)編號(hào)的因子個(gè)數(shù)也很復(fù)雜,其主要操作是判斷imodj是否為0,共執(zhí)行了n*(1+2+3+n)次,時(shí)間復(fù)雜度為O(n2)。仔細(xì)觀察表1,算法分析與設(shè)計(jì),21,數(shù)學(xué)模型2:觀察表1,發(fā)現(xiàn)當(dāng)且僅當(dāng)n為完全平方數(shù)時(shí),d(n)為奇數(shù);這是因?yàn)閚的因子是成對(duì)出現(xiàn)的,也即當(dāng)n=a*b且ab時(shí),必有兩個(gè)因子a,b;只有n為完全平方數(shù),也即當(dāng)n=a2時(shí),才會(huì)出現(xiàn)d(n)為奇數(shù)的情形。算法設(shè)計(jì)3:這時(shí)只需要找出小于n的平方數(shù)即可。,算法分析與設(shè)計(jì),22,算法3如下:input(n);for(i=1;i=n;i+)if(i*i=n)print(i,”isfree.”);elsebreak;注意:在對(duì)運(yùn)行效率要求較高的大規(guī)模的數(shù)據(jù)處理問(wèn)題時(shí),必須多動(dòng)腦筋找出效率較高的數(shù)學(xué)模型及其對(duì)應(yīng)的算法。,算法分析與設(shè)計(jì),23,例4假金幣,N個(gè)金幣(編號(hào)為1N)中有一枚重量不同的假金幣(真金幣重量相同),利用唯一的一臺(tái)天平將金幣分組稱量可以找出假金幣。輸入:第一行輸入2個(gè)空格隔開的整數(shù)N和K,N是金幣的總數(shù)(21000),K是稱重的次數(shù)(1100)。隨后2K行記錄稱量的情況和結(jié)果,連續(xù)2行記錄一次稱量:第1行首先是Pi(1N/2),表示兩邊托盤放置的金幣數(shù)目,隨后是左邊托盤中Pi個(gè)金幣編號(hào)和右邊托盤中Pi個(gè)金幣編號(hào),所有數(shù)之間都由空格隔開;第2行用和=記錄稱量結(jié)果。,算法分析與設(shè)計(jì),24,輸出輸出假金幣的編號(hào)。如果稱量記錄無(wú)法確定假金幣,輸出0輸入樣例:5321234114125,輸出樣例:3,算法分析與設(shè)計(jì),25,搜索過(guò)程,依次假設(shè)i號(hào)金幣是假的對(duì)稱量的記錄進(jìn)行比較,如果假設(shè)與所有的記錄都不矛盾,則有可能是假的如果可能的假金幣只有1個(gè),輸出他的編號(hào),否則,輸出0,算法分析與設(shè)計(jì),26,Intjd(intj,int*s,charc)/函數(shù)判斷假設(shè)j金幣是假的與稱量結(jié)果是否矛盾/s是稱量結(jié)果,其第一個(gè)元素是左托盤中金幣的個(gè)數(shù),c是稱量結(jié)果m=2*s0;for(i=f=1;i=m,算法分析與設(shè)計(jì),27,intmain()intnum1001000;chars1000;/輸入內(nèi)容for(i=1,count=0;i1)break;/不止一枚假金幣no=i;if(count!=1)printf(“0”);elseprintf(“%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,1、某地刑偵大隊(duì)對(duì)涉及六個(gè)嫌疑人的一樁疑案進(jìn)行分析:A、B至少有一人作案;A、E、F三人中至少有兩人參與作案;A、D不可能是同案犯;B、C或同時(shí)作案,或與本案無(wú)關(guān);C、D中有且僅有一人作案;如果D沒(méi)有參與作案,則E也不可能參與作案。試設(shè)計(jì)算法將作案人找出來(lái)。,練習(xí),算法分析與設(shè)計(jì),30,2、將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)化,枚舉范圍就更少了。,- 1.請(qǐng)仔細(xì)閱讀文檔,確保文檔完整性,對(duì)于不預(yù)覽、不比對(duì)內(nèi)容而直接下載帶來(lái)的問(wèn)題本站不予受理。
- 2.下載的文檔,不會(huì)出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請(qǐng)點(diǎn)此認(rèn)領(lǐng)!既往收益都?xì)w您。
下載文檔到電腦,查找使用更方便
9.9 積分
下載 |
- 配套講稿:
如PPT文件的首頁(yè)顯示word圖標(biāo),表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開word文檔。
- 特殊限制:
部分文檔作品中含有的國(guó)旗、國(guó)徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計(jì)者僅對(duì)作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- 算法設(shè)計(jì)與分析 算法 設(shè)計(jì) 分析 蠻力法
鏈接地址:http://appdesigncorp.com/p-13158188.html