算法設(shè)計與分析：蠻力

算法設(shè)計與分析Narcissus數(shù)希臘神話：相傳Narcissus（那喀索斯）是河神刻斐索斯與水澤女神利里俄珀之子。他是一位長相十分清秀的美少年，卻對任何姑娘都不動心，只對自己的水中倒影愛慕不已，最終在顧影自憐中抑郁死去。Narcissus死后化作水仙花，仍留在水邊守望著自己的影子。Narcissus數(shù)：一個n位數(shù)中各數(shù)字的n次冪之和等于該數(shù)本身。如：153=1^3+5^3+3^3。其中n=3時的Narcissus數(shù)稱之為“水仙花數(shù)”。請找出所有的“水仙花數(shù)”。3位數(shù)（100～999）各位數(shù)字立方和等于該數(shù)本身枚舉算法基本思想枚舉算法也稱之為窮舉算法，就是按照問題本身的性質(zhì)，一一列舉出該問題所有可能的解，并在列舉的過程中，逐一檢驗每個可能解是否是問題的真正解。若是則采納這個解；否則拋棄它.

不能遺漏不要重復(fù)枚舉算法基本思想解的高準(zhǔn)確性和全面性

實現(xiàn)簡單，枚舉算法通過循環(huán)來逐一列舉和驗證可能解效率提升空間比較大枚舉算法也稱之為窮舉算法，就是按照問題本身的性質(zhì)，一一列舉出該問題所有可能的解，并在列舉的過程中，逐一檢驗每個可能解是否是問題的真正解。若是則采納這個解；否則拋棄它.

枚舉三步1.確定枚舉對象

枚舉對象也可以理解為是問題解的表達形式，一般需要用若干參數(shù)來描述參數(shù)之間需要相互獨立，而且，參數(shù)數(shù)目越少，問題解的搜索空間的維度也相應(yīng)地??；每個參數(shù)的取值范圍越小，問題解的搜索空間也越小。2.逐一列舉可能解根據(jù)枚舉對象的參數(shù)構(gòu)造循環(huán)，一一列舉其表達式的每一種取值情況。3.逐一驗證可能解根據(jù)問題解的要求，一一驗證枚舉對象表達式的每一個取值，如果滿足條件，則采納它，否則，拋棄之。模糊數(shù)字任務(wù)描述：一張單據(jù)上有一個5位數(shù)的編碼，因為保管不善，其百位數(shù)已經(jīng)變得模糊不請。但是知道這個5位數(shù)是57和67的倍數(shù)?，F(xiàn)在要設(shè)計一個算法，輸出所有滿足這些條件的5位數(shù)，并統(tǒng)計這樣的數(shù)的個數(shù)。輸入：每一行對應(yīng)一個測試樣例，每一行包含4個數(shù)字，依次是萬位數(shù)，千位數(shù)，十位數(shù)和個位數(shù)。最后一行包含4個-1，表示輸入結(jié)束。輸出：每組測試樣例的結(jié)果輸出占一行，第一個數(shù)字表示滿足條件的編碼個數(shù)，后面按升序輸出所有滿足條件的編碼，數(shù)字與數(shù)字之間用空格隔開。19？95模糊數(shù)字枚舉對象

Obj(h)：記h百位數(shù)數(shù)字，h

=0～9逐一列舉

for(h=0;h<10;h++)逐一驗證

19h95能否整除57和67模糊數(shù)字續(xù)任務(wù)描述：一張單據(jù)上有一個5位數(shù)的編碼，因為保管不善，其萬位數(shù)字和百位數(shù)已經(jīng)變得模糊不請。但是知道這個5位數(shù)是57和67的倍數(shù)?，F(xiàn)在要設(shè)計一個算法，輸出所有滿足這些條件的5位數(shù)，并統(tǒng)計這樣的數(shù)的個數(shù)。輸入：每一行對應(yīng)一個測試樣例，每一行包含3個數(shù)字，依次是千位數(shù)，十位數(shù)和個位數(shù)。最后一行包含3個-1，表示輸入結(jié)束。輸出：每組測試樣例的結(jié)果輸出占一行，第一個數(shù)字表示滿足條件的編碼個數(shù)，后面按升序輸出所有滿足條件的編碼，數(shù)字與數(shù)字之間用空格隔開。？9？95模糊數(shù)字續(xù)枚舉對象obj(d1,d2)萬位數(shù)數(shù)字，記為d1，d1=1～9百位數(shù)數(shù)字，記為d2，d2=0～9逐一列舉

for(d1=1;d1<10;d1++)for(d2=0;d2<10;d2++)逐一驗證

d19d295能否整除57和67模糊數(shù)字再續(xù)任務(wù)描述：一張單據(jù)上有一個5位數(shù)的編碼，因為保管不善，其萬位數(shù)字和千位數(shù)已經(jīng)變得模糊不請。但是知道這個5位數(shù)是57和67的倍數(shù)?，F(xiàn)在要設(shè)計一個算法，輸出所有滿足這些條件的5位數(shù)，并統(tǒng)計這樣的數(shù)的個數(shù)。輸入：每一行對應(yīng)一個測試樣例，每一行包含3個數(shù)字，依次是百位數(shù)，十位數(shù)和個位數(shù)。最后一行包含3個-1，表示輸入結(jié)束。輸出：每組測試樣例的結(jié)果輸出占一行，第一個數(shù)字表示滿足條件的編碼個數(shù)，后面按升序輸出所有滿足條件的編碼，數(shù)字與數(shù)字之間用空格隔開。？?095m錢n雞任務(wù)描述：我國古代數(shù)學(xué)家張丘建在《算經(jīng)》中出了一道題“雞翁一，值錢五；雞母一，值錢三；雞雛三，值錢一。百錢買百雞，問雞翁、雞母、雞雛各幾何？”，現(xiàn)在假定各雞種的價格不變，擁有的錢數(shù)為m，需要購買的雞數(shù)為n，試求出所有可能的購買方案總數(shù)。輸入：每行對應(yīng)一個測試樣例，每一行包含2個數(shù)字，分別為n和m。最后一行包含2個-1，表示輸入結(jié)束。輸出：每組測試樣例的結(jié)果輸出占一行，輸出可能購買方案總數(shù)。m錢n雞枚舉對象obj(n1，n2，n3)雞翁數(shù)，記為n1，n1=0～n雞母數(shù)，記為n2，n2=0～n雞雛數(shù)，記為n3，n3=0～n逐一列舉

三層for循環(huán)嵌套逐一驗證

n1+

n2+

n3==n,5n1+

3n2+

n3/3

==mm錢n雞-改進枚舉對象obj(n1，n2)雞翁數(shù)，記為n1，n1=0～m/5雞母數(shù)，記為n2，n2=0～m/3雞雛數(shù)，記為n3，n3=n-n1

-n2逐一列舉

二層for循環(huán)嵌套逐一驗證5n1+

3n2+

n3/3==m

算法復(fù)雜度O(m^2)牛刀小試問題描述：編寫算法解如下數(shù)字迷：ABCAB*A=DDDDDD方案1：枚舉范圍：A：3-9B：0-9C：0-9工枚舉700次方案2：將算式變形為除法：DDDDDD/A=ABCAB枚舉范圍：A：3-9D：1-9共枚舉63次查找問題

輸入樣例：n=5a={2,3,3,5,6}k=4輸出樣例：3查找問題

逐一列舉一層for循環(huán)，按照i從小到大遍歷。

查找問題

23356

23356

更加有效的枚舉方式

23356

23356

查找問題//輸入，全局變量intn,k;inta[MAX_N];intbinarySearch(){intlb=0;ub=n;//初始化解的存在范圍

while(ub-lb>0){

intmid=(lb+ub)/2;

if(a[mid]>=k)

ub=mid;//解的范圍更新為[lb,mid]

else

lb=mid+1;//解的范圍更新為[mid+1,ub]

}returnlb;//注意解空間是閉區(qū)間[lb,ub]，所以lb即為答案}一般化最優(yōu)問題查找問題是該模型的一個實例

移除石頭題目描述有一條河，河中間有一些石頭，石頭的數(shù)量以及相鄰兩塊石頭之間的距離已知?，F(xiàn)在可以移除一些石頭，假設(shè)最多可以移除m塊石頭（注意：首尾兩塊石頭不可以移除，且假定所有的石頭都處于同一條直線），問最多移除m塊石頭后相鄰兩塊石頭之間的最小距離的最大值是多少？輸入格式多組輸入（<=20組數(shù)據(jù)，讀入以EOF結(jié)尾），每組第一行輸入兩個數(shù)字：n(2<=n<=1000)為石頭的個數(shù)，m(0<=m<=n-2)為可移除的石頭數(shù)目，隨后n-1個正整數(shù)，表示順序相鄰兩個石頭的距離d(d<=1000)。輸出格式每組輸出一行結(jié)果，表示最大的點數(shù)樣例輸入41123樣例輸出31234移除石頭

逐一列舉

移除石頭

判定C(d)：應(yīng)用貪心思想：如果當(dāng)前考慮的相鄰石頭小于d，則去掉一個石頭如果任意相鄰石頭的距離都不小于d，則返回true；如果移除的石頭個數(shù)大于m，或者最后兩個相鄰石頭距離小于d，則返回false移除石頭驗證：C(d)，即最多移除m個石頭后任意相鄰兩個石頭的距離不小于dintValidate(intd){intk=m;//可以移除的石頭數(shù)目intst=1;//表示最初的石頭for(inten=2;en<=n;){//表示結(jié)尾的石頭intdisCur

=dis[en]-dis[st];//st與en石頭的間距while(disCur<d){//此時可以移除第en個石頭

k--;//移除當(dāng)前石頭en++;//考慮下一個石頭if(en>n||k<0)

return0;//d比最小距離大

disCur=dis[en]-dis[st];

}st=en;//更新起點en++;}return1;}移除石頭inta[1005],dis[1005]={0};intn,m;intmain(){while(~scanf("%d%d",&n,&m)){

for(inti=2;i<=n;i++){

//a[i]表示i-1到i石頭的間距，下標(biāo)從1開始

scanf("%d",&a[i]);

dis[i]=a[i]+dis[i-1];//sum[i]表示1到i石頭的間距

}intlb=0,ub=1000*1000+5;//距離上界

while(lb<ub){

intmid=(lb+ub)/2;

if(Validate(mid))

lb=mid;//更新下界

else

ub=mid-1;//更新上界}

printf("%d\n",lb);}return0;}二分查找算法課后思考題

輸入樣例：N=4K=11L={8.02,7.43,4.57,5.39}輸出樣例：2.00(每條繩子分別可以得到4條、3條、2條、2條，共計11條。)課后思考題給一個很長的數(shù)字串S：123456891011121314…，它是由所有的自然數(shù)從小到大依次排列起來的。任意給一個數(shù)字串S1(其長度不大于10)，求出S1在S中第一次出現(xiàn)的位置。比如：輸入101，輸出為10考慮：2132按連續(xù)數(shù)字的位數(shù)來枚舉：1）一位數(shù)的連續(xù)序列？2）二位數(shù)的連續(xù)序列？3）三位數(shù)的連續(xù)序列？…212213214……320321

3