實(shí)驗(yàn)二--蠻力法.doc

南華大學(xué)實(shí)驗(yàn)名稱：算法的時(shí)間復(fù)雜度學(xué) 院：計(jì) 算 機(jī) 學(xué) 院專業(yè)班級(jí)：本2010電氣信息類03班 學(xué) 號(hào)：20104030342 姓 名： 謝志興指導(dǎo)教師： 余穎日期： 2012 年 3 月 27 日實(shí)驗(yàn)二 蠻力法一、 實(shí)驗(yàn)?zāi)康呐c要求熟悉C/C+語(yǔ)言的集成開(kāi)發(fā)環(huán)境；通過(guò)本實(shí)驗(yàn)加深對(duì)蠻力法的理解。二、 實(shí)驗(yàn)內(nèi)容:掌握蠻力法的概念和基本思想，并結(jié)合具體的問(wèn)題學(xué)習(xí)如何用相應(yīng)策略進(jìn)行求解的方法。三、 實(shí)驗(yàn)題1. 某地刑偵大隊(duì)對(duì)涉及六個(gè)嫌疑人的一樁疑案進(jìn)行分析：（1）A、B至少有一人作案；（2）A、E、F三人中至少有兩人參與作案；（3）A、D不可能是同案犯；（4）B、C或同時(shí)作案，或與本案無(wú)關(guān)；（5）C、D中有且僅有一人作案；（6）如果D沒(méi)有參與作案，則E也不可能參與作案。試設(shè)計(jì)算法將作案人找出來(lái)。2. 將1,2.9共9個(gè)數(shù)分成三組,分別組成三個(gè)三位數(shù),且使這三個(gè)三位數(shù)構(gòu)成1:2:3的比例,試求出所有滿足條件的三個(gè)三位數(shù)。四、 實(shí)驗(yàn)步驟理解算法思想和問(wèn)題要求；編程實(shí)現(xiàn)題目要求；上機(jī)輸入和調(diào)試自己所編的程序；驗(yàn)證分析實(shí)驗(yàn)結(jié)果；整理出實(shí)驗(yàn)報(bào)告。五、 實(shí)驗(yàn)程序/*1題程序*/#include using namespace std; int main() int A,B,C,D,E,F; /每個(gè)罪犯只有01兩種情況，1是罪犯0清白 for(A=0;A2;A+) /A for(B=0;B2;B+)/Bfor(C=0;C2;C+)/Cfor(D=0;D2;D+)/Dfor(E=0;E2;E+)/Efor(F=0;F0) /AB至少一人作案 &(A+E+F1) /AEF至少兩人作案 &(A+D=1) /AD不可能是同案犯 &(B+C!=1) /BC或同案 或與本案無(wú)關(guān) &(C+D=1) /CD只有一人作案 &(!(!D&E)/如果D沒(méi)有參與作案，則E也不可能參與作案 coutA:;if(A=1)cout作案endl;elsecout非作案endl;coutB:;if(B=1)cout作案endl;elsecout非作案endl;coutC:;if(C=1)cout作案endl;elsecout非作案endl;coutD:;if(D=1)cout作案endl;elsecout非作案endl;coutE:;if(E=1)cout作案endl;elsecout非作案endl;coutF:;if(F=1)cout作案endl;elsecout非作案endl; return 0; /*2題程序*/#includeusing namespace std;bool isValid(int i,int j,int k) int a3,b3,c3; a0=i%10; a1=(i/10)%10; a2=i/100; b0=j%10; b1=(j/10)%10; b2=j/100; c0=k%10; c1=(k/10)%10; c2=k/100; if(a0!=a1&a0!=a2&a0!=b0&a0!=b1&a0!=b2&a0!=c0&a0!=c1&a0!=c2 &a1!=a2&a1!=b0&a1!=b1&a1!=b2&a1!=c0&a1!=c1&a1!=c2 &a2!=b0&a2!=b1&a2!=b2&a2!=c0&a2!=c1&a2!=c2 &b0!=b1&b0!=b2&b0!=c0&b0!=c1&b0!=c2 &b1!=b2&b1!=c0&b1!=c1&b1!=c2 &b2!=c0&b2!=c1&b2!=c2 &c0!=c1&c0!=c2 &c1!=c2 &a0!=0&a1!=0&a2!=0&b0!=0&b1!=0&b2!=0&c0!=0&c1!=0&c2!=0 ) return true; else return false;int main()cout滿足條件的三個(gè)三位數(shù)分別為：endl; for(int i=123;i=329;i+) int j=2*i,k=3*i; if(isValid(i,j,k)couti j kendl; return 0;六、 實(shí)驗(yàn)結(jié)果運(yùn)行環(huán)境：操作系統(tǒng)：Windows 7 旗艦版 32位 SP1 ( DirectX 11 )處理器：AMD A6-3400M APU with Radeon HD Graphics 四核主板：宏碁 Aspire 4560 (AMD K12)內(nèi)存：3 GB ( 海力士 DDR3 1333MHz / 南亞易勝 DDR3 1333MHz )運(yùn)行結(jié)果：1題結(jié)果：2題結(jié)果：七、 實(shí)驗(yàn)分析 蠻力法，也稱窮舉法，是一種簡(jiǎn)單而直接地解決問(wèn)題的方法，常常直接基于問(wèn)題的描述，因此，也是最容易應(yīng)用的方法。但是用蠻力法設(shè)計(jì)的算法其時(shí)間性能往往是最低的，典型的指數(shù)時(shí)間算法一般都是通過(guò)蠻力法搜索而得到的。 蠻力法的設(shè)計(jì)思想： 蠻力法所依賴的最基本技術(shù)是掃描技術(shù)，依次處理所有元素師蠻力法的關(guān)鍵，一次處理每個(gè)元素的方法是遍歷。 雖然設(shè)計(jì)高效的算法很少來(lái)自于蠻力法，但基于以下原因，蠻力法也是一種重要的算法設(shè)計(jì)技術(shù)：（1）理論上，蠻力法可以解決可計(jì)算領(lǐng)域的各種問(wèn)題。對(duì)于一些非?；镜膯?wèn)題，例如求一個(gè)序列的最大元素，計(jì)算n個(gè)數(shù)的和等，蠻力法是一種非常常用的算法設(shè)計(jì)技術(shù)。（2）蠻力法經(jīng)常用來(lái)解決一些較小規(guī)模的問(wèn)題。如果需要解決的問(wèn)題規(guī)模不大，用蠻力法設(shè)計(jì)的算法其速度是可以接受的，此時(shí)設(shè)