《算法設(shè)計(jì)與分析》蠻力法.ppt

算法分析與設(shè)計(jì),1,蠻力法,算法分析與設(shè)計(jì),2,蠻力法BruteForce,蠻力法（枚舉法、窮舉法，暴力法）要求設(shè)計(jì)者找出所有可能的方法，然后選擇其中的一種方法，若該方法不可行則試探下一種可能的方法。蠻力法是一種直接解決問題的方法，常常直接基于問題的描述和所設(shè)計(jì)的概念定義。“力”指計(jì)算機(jī)的能力，而不是人的智力。蠻力法常常是最容易應(yīng)用的方法。求an（n為非負(fù)整數(shù)）用連續(xù)整數(shù)檢測算法計(jì)算GCD（m,n）,算法分析與設(shè)計(jì),3,蠻力法BruteForce,蠻力法不是一個最好的算法（巧妙和高效的算法很少出自蠻力），但當(dāng)我們想不出更好的辦法時，它也是一種有效的解決問題的方法。它可能是惟一一種幾乎什么問題都能解決的一般性方法，常用于一些非?；?、但又十分重要的算法，比如計(jì)算n個數(shù)字的和，求一個列表的最大元素等等。,算法分析與設(shè)計(jì),4,蠻力法的優(yōu)點(diǎn),邏輯清晰，編寫程序簡潔對于一些重要的問題（比如：排序、查找、矩陣乘法和字符串匹配），可以產(chǎn)生一些合理的算法解決問題的實(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)]有反序的記錄為止。順序查找和蠻力字符串匹配順序查找：從線性表的一端向另一端逐個將關(guān)鍵碼與給定值進(jìn)行比較，若相等，則查找成功，給出該記錄在表中的位置；若整個表檢測完仍未找到與給定值相等的關(guān)鍵碼，則查找失敗，給出失敗信息。蠻力字符串匹配：即樸素模式串匹配,算法分析與設(shè)計(jì),7,根據(jù)問題中的條件將可能的情況一一列舉出來，逐一嘗試從中找出滿足問題條件的解。但有時一一列舉出的情況數(shù)目很大，如果超過了我們所能忍受的范圍，則需要進(jìn)一步考慮，排除一些明顯不合理的情況，盡可能減少問題可能解的列舉數(shù)目。用蠻力法解決問題，通?？梢詮膬蓚€方面進(jìn)行算法設(shè)計(jì)：1）找出枚舉范圍：分析問題所涉及的各種情況。2）找出約束條件：分析問題的解需要滿足的條件，并用邏輯表達(dá)式表示。,蠻力法解題步驟,【例1】百錢百雞問題。中國古代數(shù)學(xué)家張丘建在他的算經(jīng)中提出了著名的“百錢百雞問題”：雞翁一，值錢五；雞母一，值錢三；雞雛三，值錢一；百錢買百雞，翁、母、雛各幾何?算法設(shè)計(jì)1：通過對問題的理解，可能會想到列出兩個三元一次方程，去解這個不定解方程，就能找出問題的解。這確實(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，無需再進(jìn)行枚舉了此時約束條件只有一個：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整除時，才會判斷“5*x+3*y+z/3=100,算法分析與設(shè)計(jì),12,例2,求所有的三位數(shù)，它除以11所得的余數(shù)等于它的三個數(shù)字的平方和。解題思路：三位數(shù)只有900個，可用枚舉法解決，枚舉時可先估計(jì)有關(guān)量的范圍，以縮小討論范圍，減少計(jì)算量。,解：設(shè)這個三位數(shù)的百位、十位、個位的數(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兩個數(shù)符合要求。,例3獄吏問題某國王對囚犯進(jìn)行大赦，讓一獄吏n次通過一排鎖著的n間牢房，每通過一次，按所定規(guī)則轉(zhuǎn)動n間牢房中的某些門鎖,每轉(zhuǎn)動一次,原來鎖著的被打開,原來打開的被鎖上；通過n次后，門鎖開著的，牢房中的犯人放出，否則犯人不得獲釋。轉(zhuǎn)動門鎖的規(guī)則是這樣的，第一次通過牢房，要轉(zhuǎn)動每一把門鎖，即把全部鎖打開；第二次通過牢房時，從第二間開始轉(zhuǎn)動，每隔一間轉(zhuǎn)動一次；第k次通過牢房，從第k間開始轉(zhuǎn)動，每隔k-1間轉(zhuǎn)動一次；問通過n次后，哪些牢房的鎖仍然是打開的？,算法分析與設(shè)計(jì),15,算法設(shè)計(jì)1：1）一維數(shù)組an記錄n個鎖的狀態(tài)1:被鎖上0:被打開2）對i號鎖的一次開關(guān)鎖可以轉(zhuǎn)化為算術(shù)運(yùn)算：ai=1-ai。3）第一次轉(zhuǎn)動的是1，2，3，n號牢房；第二次轉(zhuǎn)動的是2，4，6，號牢房；第i次轉(zhuǎn)動的是i，2i，3i，4i，號牢房，是起點(diǎn)為i，公差為i的等差數(shù)列。4）不做其它的優(yōu)化，用蠻力法通過循環(huán)模擬獄吏的開關(guān)鎖過程，最后當(dāng)?shù)趇號牢房對應(yīng)的數(shù)組元素ai為0時，該牢房的囚犯得到大赦。,算法分析與設(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ì)算，算法的時間復(fù)雜度為n(1+1/2+1/3+1/n)=O(nlogn)。,問題分析：轉(zhuǎn)動門鎖的規(guī)則可以有另一種理解，第一次轉(zhuǎn)動的是編號為1的倍數(shù)的牢房；第二次轉(zhuǎn)動的是編號為2的倍數(shù)的牢房；第三次轉(zhuǎn)動的是編號為3的倍數(shù)的牢房；則獄吏問題是一個關(guān)于因子個數(shù)的問題。令d(n)為自然數(shù)n的因子個數(shù)，這里不計(jì)重復(fù)的因子，如4的因子為1，2，4共三個因子，而非1，2，2，4。則d(n)有的為奇數(shù)，有的為偶數(shù)，見下表:表1編號與因數(shù)個數(shù)的關(guān)系,算法分析與設(shè)計(jì),18,數(shù)學(xué)模型1：上表中的d(n)有的為奇數(shù)，有的為偶數(shù)，由于牢房的門開始是關(guān)著的，這樣編號為i的牢房，所含1i之間的不重復(fù)因子個數(shù)為奇數(shù)時，牢房最后是打開的，反之，牢房最后是關(guān)閉的。,算法分析與設(shè)計(jì),19,算法設(shè)計(jì)2:1）算法應(yīng)該是求出每個牢房編號的不重復(fù)的因子個數(shù)，當(dāng)它為奇數(shù)時，這里邊的囚犯得到大赦。2）一個數(shù)的因子是沒有規(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)次，時間近似為復(fù)雜度為O（nlogn）。使用了n個空間的一維數(shù)組。算法2沒有使用輔助空間，但由于求一個編號的因子個數(shù)也很復(fù)雜，其主要操作是判斷imodj是否為0，共執(zhí)行了n*(1+2+3+n)次，時間復(fù)雜度為O（n2）。仔細(xì)觀察表1,算法分析與設(shè)計(jì),21,數(shù)學(xué)模型2：觀察表1，發(fā)現(xiàn)當(dāng)且僅當(dāng)n為完全平方數(shù)時,d(n)為奇數(shù)；這是因?yàn)閚的因子是成對出現(xiàn)的,也即當(dāng)n=a*b且ab時，必有兩個因子a，b;只有n為完全平方數(shù)，也即當(dāng)n=a2時,才會出現(xiàn)d(n)為奇數(shù)的情形。算法設(shè)計(jì)3：這時只需要找出小于n的平方數(shù)即可。,算法分析與設(shè)計(jì),22,算法3如下：input(n);for(i=1;i<=n;i+)if（i*i<=n）print(i,”isfree.”);elsebreak;注意：在對運(yùn)行效率要求較高的大規(guī)模的數(shù)據(jù)處理問題時，必須多動腦筋找出效率較高的數(shù)學(xué)模型及其對應(yīng)的算法。,算法分析與設(shè)計(jì),23,例4假金幣,N個金幣（編號為1N）中有一枚重量不同的假金幣（真金幣重量相同），利用唯一的一臺天平將金幣分組稱量可以找出假金幣。輸入：第一行輸入2個空格隔開的整數(shù)N和K，N是金幣的總數(shù)（21000），K是稱重的次數(shù)（1100）。隨后2K行記錄稱量的情況和結(jié)果，連續(xù)2行記錄一次稱量：第1行首先是Pi(1N/2)，表示兩邊托盤放置的金幣數(shù)目，隨后是左邊托盤中Pi個金幣編號和右邊托盤中Pi個金幣編號，所有數(shù)之間都由空格隔開；第2行用和=記錄稱量結(jié)果。,算法分析與設(shè)計(jì),24,輸出輸出假金幣的編號。如果稱量記錄無法確定假金幣，輸出0輸入樣例：5321234<114125,輸出樣例：3,算法分析與設(shè)計(jì),25,搜索過程,依次假設(shè)i號金幣是假的對稱量的記錄進(jìn)行比較，如果假設(shè)與所有的記錄都不矛盾，則有可能是假的如果可能的假金幣只有1個，輸出他的編號，否則，輸出0,算法分析與設(shè)計(jì),26,Intjd(intj,int*s,charc)/函數(shù)判斷假設(shè)j金幣是假的與稱量結(jié)果是否矛盾/s是稱量結(jié)果，其第一個元素是左托盤中金幣的個數(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：用蠻力法解決凸包問題,凸包問題：S是平面上的一個點(diǎn)集，封閉S中所有頂點(diǎn)的最小凸多邊形，稱為S的凸包。凸包問題就是為一個n個點(diǎn)的集合構(gòu)造凸包的問題。對于一個n個點(diǎn)集合中的兩個點(diǎn)pi和pj，當(dāng)且僅當(dāng)該集合中的其他點(diǎn)都位于穿過這兩點(diǎn)的直線的同一邊時，它們的連線是該集合凸包邊界的一部分。例6最近對問題找出一個包含n個點(diǎn)的集合中距離最近的兩個點(diǎn)。,算法分析與設(shè)計(jì),29,1、某地刑偵大隊(duì)對涉及六個嫌疑人的一樁疑案進(jìn)行分析：A、B至少有一人作案；A、E、F三人中至少有兩人參與作案；A、D不可能是同案犯；B、C或同時作案，或與本案無關(guān)；C、D中有且僅有一人作案；如果D沒有參與作案，則E也不可能參與作案。試設(shè)計(jì)算法將作案人找出來。,練習(xí),算法分析與設(shè)計(jì),30,2、將1,2.9共9個數(shù)分成三組,分別組成三個三位數(shù),且使這三個三位數(shù)構(gòu)成1:2:3的比例,試求出所有滿足條件的三個三位數(shù)Tip：如果我們不假思索地以每一個數(shù)位為枚舉對象，一位一位地去枚舉，枚舉次數(shù)就有9次，如果我們分別設(shè)三個數(shù)為x,2x,3x，以x為枚舉對象，窮舉的范圍就減少為9，在細(xì)節(jié)上再進(jìn)一步優(yōu)化，枚舉范圍就更少了。,