第4章蠻力法4.1蠻力法概述4.2蠻力法的基本應(yīng)用4.3遞歸在蠻力法中的應(yīng)用4.4圖的深度優(yōu)先和廣度優(yōu)先遍歷

蠻力法是一種簡單直接地解決問題的方法，通常直接基于問題的描述和所涉及的概念定義，找出所有可能的解。然后選擇其中的一種或多種解，若該解不可行則試探下一種可能的解。4.1蠻力法概述使用蠻力法通常有如下幾種情況：搜索所有的解空間：問題的解存在于規(guī)模不大的解空間中。搜索所有的路徑：這類問題中不同的路徑對應(yīng)不同的解。直接計(jì)算：按照基于問題的描述和所涉及的概念定義，直接進(jìn)行計(jì)算。往往是一些簡單的題，不需要算法技巧的。模擬和仿真：按照求解問題的要求直接模擬或仿真即可。4.2.1直接采用蠻力法的一般格式

在直接采用蠻力法設(shè)計(jì)算法中，主要是使用循環(huán)語句和選擇語句，循環(huán)語句用于窮舉所有可能的情況，而選擇語句判定當(dāng)前的條件是否為所求的解。for(循環(huán)變量x取所有可能的值){┇

if(x滿足指定的條件)

輸出x;┇}4.2

蠻力法的基本應(yīng)用基本格式

【例4.1】編寫一個(gè)程序，輸出2～1000之間的所有完全數(shù)。所謂完全數(shù)，是指這樣的數(shù)，該數(shù)的各因子（除該數(shù)本身外）之和正好等于該數(shù)本身，例如：

6=1+2+3

28=1+2+4+7+14

解：先考慮對于一個(gè)整數(shù)m，如何判斷它是否為完全數(shù)。

從數(shù)學(xué)知識可知：一個(gè)數(shù)m的除該數(shù)本身外的所有因子都在1～m/2之間。算法中要取得因子之和，只要在1～m/2之間找到所有整除m的數(shù)，將其累加起來即可。如果累加和與m本身相等，則表示m是一個(gè)完全數(shù)，可以將m輸出。for(m=2;m<=1000;m++){

求出m的所有因子之和s;

if(m==s)輸出s;}對應(yīng)的程序如下：voidmain(){intm,i,s;

for(m=2;m<=1000;m++)

{s=0;for(i=1;i<=m/2;i++)if(m%i==0)s+=i; //i是m的一個(gè)因子

if(m==s)

printf("%d",m);

}

printf("\n");}

【例4.3】在象棋算式里，不同的棋子代表不同的數(shù)，有以下算式，設(shè)計(jì)一個(gè)算法求這些棋子各代表哪些數(shù)字。兵炮馬卒兵炮車卒兵卒車卒馬+

解：采用蠻力法時(shí)，設(shè)兵、炮、馬、卒和車的取值分別為a、b、c、d、e。則有：

a、b、c、d、e的取值范圍為0～9且均不相等（即a==b||a==c||a==d||a==e||b==c||b==d||b==e||c==d||c==e||d==e不成立）。設(shè)：m=a×1000+b×100+c×10+dn=a×1000+b×100+e×10+ds=e×10000+d×1000+c×100+a×10+d則有：m+n==s兵炮馬卒兵炮車卒兵卒車卒馬+voidfun(){inta,b,c,d,e,m,n,s;

for(a=1;a<=9;a++)for(b=0;b<=9;b++)

for(c=0;c<=9;c++)

for(d=0;d<=9;d++)

for(e=0;e<=9;e++)if(a==b||a==c||a==d||

a==e||b==c||b==d||b==e||c==d||c==e||d==e)continue;else

{m=a*1000+b*100+c*10+d;n=a*1000+b*100+e*10+d;s=e*10000+d*1000+c*100+a*10+d;

if(m+n==s)printf("兵:%d炮:%d馬:%d卒:%d車:%d\n", a,b,c,d,e);

}}試題編號：201509-1試題名稱：數(shù)列分段時(shí)間限制：1.0s內(nèi)存限制：256.0MB問題描述：給定一個(gè)整數(shù)數(shù)列，數(shù)列中連續(xù)相同的最長整數(shù)序列算成一段，

問數(shù)列中共有多少段？輸入格式：輸入的第一行包含一個(gè)整數(shù)n，表示數(shù)列中整數(shù)的個(gè)數(shù)。

第二行包含n個(gè)整數(shù)a1,a2,…,an，表示給定的數(shù)列，相鄰的

整數(shù)之間用一個(gè)空格分隔。輸出格式：輸出一個(gè)整數(shù)，表示給定的數(shù)列有多個(gè)段。樣例輸入8

8880121280樣例輸出5樣例說明：888是第一段，0是第二段，1212是第三段，倒數(shù)第二個(gè)整數(shù)8是第四段，最后一個(gè)0是第五段。幾個(gè)CSP試題#include<stdio.h>intmain(void){intn,first,x,sum=1;//輸入n，輸?shù)冢眰€(gè)數(shù)scanf("%d%d",&n,&first);for(inti=2;i<=n;i++) //輸入第2至第n個(gè)數(shù){scanf("%d",&x); if(x!=first) //比較統(tǒng)計(jì)：是否與前一個(gè)數(shù)相同

sum++;first=x;}printf("%d\n",sum); //輸出結(jié)果return0;}試題編號：201712-1 試題名稱：最小差值時(shí)間限制：1.0s 內(nèi)存限制：256.0MB問題描述：給定n個(gè)數(shù)，請找出其中相差（差的絕對值）最小的兩個(gè)數(shù)，輸出它

們的差值的絕對值。輸入格式：輸入第一行包含一個(gè)整數(shù)n。第二行包含n個(gè)正整數(shù)，相鄰整數(shù)之間使

用一個(gè)空格分隔。輸出格式：輸出一個(gè)整數(shù)，表示答案。樣例輸入:5

154820樣例輸出:1樣例說明：相差最小的兩個(gè)數(shù)是5和4，它們之間的差值是1。樣例輸入：5

93613樣例輸出0樣例說明：有兩個(gè)相同的數(shù)3，它們之間的差值是0.數(shù)據(jù)規(guī)模和約定：對于所有評測用例，2≤n≤1000，每個(gè)給定的整數(shù)都是不超過10000的正整數(shù)。#include<iostream>#include<algorithm>usingnamespacestd;intmain(){intn;inta[1005];scanf("%d",&n);for(inti=0;i<n;i++)scanf("%d",&a[i]);sort(a,a+n);intans=100000;for(inti=1;i<n;i++)if(ans>a[i]-a[i-1])ans=a[i]-a[i-1];printf("%d\n",ans);return0;}試題編號：201409-1 試題名稱：相鄰數(shù)對時(shí)間限制：1.0s 內(nèi)存限制：256.0MB問題描述：給定n個(gè)不同的整數(shù)，問這些數(shù)中有多少對整數(shù)，

它們的值正好相差1。輸入格式：輸入的第一行包含一個(gè)整數(shù)n，表示給定整數(shù)的個(gè)數(shù)。

第二行包含所給定的n個(gè)整數(shù)。輸出格式：輸出一個(gè)整數(shù)，表示值正好相差1的數(shù)對的個(gè)數(shù)。樣例輸入：6

1026378樣例輸出：3樣例說明：值正好相差1的數(shù)對包括(2,3),(6,7),(7,8)。評測用例規(guī)模與約定：1<=n<=1000，給定的整數(shù)為不超過10000的非負(fù)整數(shù)。#include"stdio.h"#include<algorithm>usingnamespacestd;constintN=1000+10;inta[N],n;intmain(){scanf("%d",&n);for(inti=0;i<n;i++)scanf("%d",&a[i]);sort(a,a+n);intans=0;for(inti=1;i<n;i++)if(a[i]-a[i-1]==1)ans++;printf("%d\n",ans);return0;}201712-2問題描述：有n個(gè)小朋友圍成一圈玩游戲，小朋友從1至n編號，2號小朋友坐在1號小朋友的順時(shí)針方向，3號小朋友坐在2號小朋友的順時(shí)針方向，……，1號小朋友坐在n號小朋友的順時(shí)針方向。

游戲開始，從1號小朋友開始順時(shí)針報(bào)數(shù)，接下來每個(gè)小朋友的報(bào)數(shù)是上一個(gè)小朋友報(bào)的數(shù)加1。若一個(gè)小朋友報(bào)的數(shù)為k的倍數(shù)或其末位數(shù)（即數(shù)的個(gè)位）為k，則該小朋友被淘汰出局，不再參加以后的報(bào)數(shù)。當(dāng)游戲中只剩下一個(gè)小朋友時(shí)，該小朋友獲勝。

例如，當(dāng)n=5,k=2時(shí)：

1號小朋友報(bào)數(shù)1；

2號小朋友報(bào)數(shù)2淘汰；

3號小朋友報(bào)數(shù)3；

4號小朋友報(bào)數(shù)4淘汰；

5號小朋友報(bào)數(shù)5；

1號小朋友報(bào)數(shù)6淘汰；

3號小朋友報(bào)數(shù)7；

5號小朋友報(bào)數(shù)8淘汰；

3號小朋友獲勝。

給定n和k，請問最后獲勝的小朋友編號為多少？輸入格式：輸入一行，包括兩個(gè)整數(shù)n和k，意義如題目所述。輸出格式：輸出一行，包含一個(gè)整數(shù)，表示獲勝的小朋友編號。樣例輸入：

52

樣例輸出：

3

樣例輸入：

73樣例輸出：

4數(shù)據(jù)規(guī)模和約定：對于所有評測用例，1≤n≤1000，1≤k≤9。#include"stdio.h"#include<queue>usingnamespacestd;intmain(){intn,k;queue<int>q;scanf("%d%d",&n,&k);for(inti=1;i<=n;i++)q.push(i);intt=1,u=1;while(!q.empty()){u=q.front();q.pop();if(t%k==0||t%10==k); //為k的倍數(shù)或其末位數(shù)為kelseq.push(u);t++;}printf("%d\n",u);return0;}4.2.2簡單選擇排序和冒泡排序

【問題描述】對于給定的含有n個(gè)元素的數(shù)組a，對其按元素值遞增排序。例如，i=3的一趟簡單選擇排序過程，其中a[0..2]是有序的，從a[3..9]中挑選最小元素a[5]，將其與a[3]進(jìn)行交換，從而擴(kuò)大有序區(qū)，減小無序區(qū)。1.簡單選擇排序12368410759有序區(qū)從無序區(qū)中通過依次比較挑選最小元素放在a[3]處12348610759有序區(qū)voidSelectSort(inta[],intn)//對a[0..n-1]元素進(jìn)行遞增簡單選擇排序{inti,j,k;for(i=0;i<n-1;i++) //進(jìn)行n-1趟排序{k=i; //用k記錄每趟無序區(qū)中最小元素的位置for(j=i+1;j<n;j++) //在a[i+1..n-1]中窮舉找最小元素a[k] if(a[j]<a[k]) k=j; if(k!=i) //若a[k]不是最小元素,將a[k]與a[i]交換 swap(a[i],a[k]);}}2.冒泡排序

例如，i=3的一趟冒泡排序過程，其中a[0..2]是有序的，從a[3..9]中通過交換將最小元素放在a[5]處，從而擴(kuò)大有序區(qū)，減小無序區(qū)。12368410759有序區(qū)從無序區(qū)中通過交換方式挑選最小元素放在a[3]處12346810579有序區(qū)voidBubbleSort(inta[],intn)//對a[0..n-1]按遞增有序進(jìn)行冒泡排序{inti,j;inttmp;boolexchange;for(i=0;i<n-1;i++) //進(jìn)行n-1趟排序{ exchange=false;

//本趟排序前置exchange為false for(j=n-1;j>i;j--) //無序區(qū)元素比較,找出最小元素

if(a[j]<a[j-1]) //當(dāng)相鄰元素反序時(shí){swap(a[j],a[j-1]);//a[j]與a[j-1]進(jìn)行交換

exchange=true; //發(fā)生交換置exchange為true

}if(exchange==false) //本趟未發(fā)生交換時(shí)結(jié)束算法return;}}4.2.3字符串匹配

【問題描述】對于字符串s和t，若t是s子串，返回t在s中的位置（t的首字符在s中對應(yīng)的下標(biāo)），否則返回-1。

【問題求解】采用直接窮舉法求解，稱為BF算法。該算法從s的每一個(gè)字符開始查找，看t是否會出現(xiàn)。例如，s=“aababcde”，t=“abcd”：s:aababcdet:abcd第1趟s:aababcdet:abcd第2趟s:aababcdet:abcd第3趟s:aababcdet:abcd第4趟成功：返回7-4=3intBF(strings,stringt) //字符串匹配{inti=0,j=0;while(i<s.length()&&j<t.length()){if(s[i]==t[j]) //比較的兩個(gè)字符相同時(shí){ i++; j++;}else //比較的兩個(gè)字符不相同時(shí){i=i-j+1; //i回退j=0; //j從0開始}}if(j==t.length()) //t的字符比較完畢returni-j; //t是s的子串,返回位置else //t不是s的子串return-1; //返回-1}

【例4.5】有兩個(gè)字符串s和t，設(shè)計(jì)一個(gè)算法求t在s中出現(xiàn)的次數(shù)。例如，s="abababa"，t="aba"，則t在s中出現(xiàn)2次。

解：采用BF算法思路。用num記錄t在s中出現(xiàn)的次數(shù)（初始時(shí)為0）。

當(dāng)在s中找到t的一次出現(xiàn)時(shí)，num++，此時(shí)j=t的長度，i指向s中本次出現(xiàn)t子串的下一個(gè)字符，所以為了繼續(xù)查找t子串的下一次出現(xiàn)，只需要置j=0。s:aaaaat:aaijs:aaaaat:aajinum++;j=0;intCount(strings,stringt) //求t在s中出現(xiàn)的次數(shù){intnum=0; //累計(jì)出現(xiàn)次數(shù)inti=0,j=0;while(i<s.length()&&j<t.length()){ if(s[i]==t[j]) //比較的兩個(gè)字符相同時(shí) {i++; j++; } else //比較的兩個(gè)字符不相同時(shí) {i=i-j+1; //i回退 j=0; //j從0開始 } if(j==t.length()) {num++; //出現(xiàn)次數(shù)增1 j=0; //j從0開始繼續(xù) }}returnnum;}4.2.4求解最大連續(xù)子序列和問題

【問題描述】給定一個(gè)有n（n≥1）個(gè)整數(shù)的序列，要求求出其中最大連續(xù)子序列的和。

例如：

序列（-2，11，-4，13，-5，-2）的最大子序列和為20

序列（-6，2，4，-7，5，3，2，-1，6，-9，10，-2）的最大子序列和為16。

規(guī)定一個(gè)序列最大連續(xù)子序列和至少是0（看成0個(gè)元素構(gòu)成的子序列），如果小于0，其結(jié)果為0。

解法1：設(shè)含有n個(gè)整數(shù)的序列a[0..n-1]，其中任何連續(xù)子序列a[i..j]（i≤j，0≤i≤n-1，i≤j≤n-1）求出它的所有元素之和thisSum。

通過比較將最大值存放在maxSum中，最后返回maxSum。a[0]a[1]…

a[i]a[i+1]…

a[j]

a[j+1]…a[n-1]thisSummaxSumMAXi：0～n-1j：i～n-1k：i～jintmaxSubSum1(inta[],intn){inti,j,k;intmaxSum=0,thisSum;

for(i=0;i<n;i++)

//兩重循環(huán)窮舉所有的連續(xù)子序列

{for(j=i;j<n;j++)

{thisSum=0;

for(k=i;k<=j;k++)

thisSum+=a[k];

if(thisSum>maxSum)//通過比較求最大連續(xù)子序列之和

maxSum=thisSum;

}

}

returnmaxSum;}maxSubSum1(a,n)算法中用了三重循環(huán)，所以有：T(n)==O(n3)。

解法2：改進(jìn)前面的解法，在求兩個(gè)相鄰子序列和時(shí)，它們之間是關(guān)聯(lián)的。

例如a[0..3]子序列和=a[0]+a[1]+a[2]+a[3]，a[0..4]子序列和=a[0]+a[1]+a[2]+a[3]+a[4]，在前者計(jì)算出來后，求后者時(shí)只需在前者基礎(chǔ)上加以a[4]即可，沒有必須每次都重復(fù)計(jì)算。從而提高了算法效率。a[0]a[1]…

a[i]a[i+1]…

a[j-1]a[j]…a[n-1]thisSumthisSum+a[j]i：0～n-1j：i～n-1maxSumMAXintmaxSubSum2(inta[],intn){inti,j;

intmaxSum=0,thisSum;

for(i=0;i<n;i++){thisSum=0;for(j=i;j<n;j++)

{thisSum+=a[j];//maxSum已經(jīng)包含了a[i..j-1]的最大和

if(thisSum>maxSum)

maxSum=thisSum;

}

}

returnmaxSum;}maxSubSum2(a,n)算法中只有兩重循環(huán)，容易求出T(n)=O(n2)。

解法3：更一步改進(jìn)解法2。

如果掃描中遇到負(fù)數(shù)，當(dāng)前子序列和thisSum將會減小，若thisSum為負(fù)數(shù)，表明前面已經(jīng)掃描的那個(gè)子序列可以拋棄了，則放棄這個(gè)子序列，重新開始下一個(gè)子序列的分析，并置thisSum為0。

若這個(gè)子序列和thisSum不斷增加，那么最大子序列和maxSum也不斷增加。1-235-105thisSum=0maxSum=0jthisSum=thisSum+a[j]=1maxSum=1以a[j]結(jié)尾的一個(gè)連續(xù)子序列和thisSum=thisSum+a[j]=-1

thisSum=0maxSum=1thisSum=thisSum+a[j]=3maxSum=3thisSum=thisSum+a[j]=5maxSum=8thisSum=thisSum+a[j]=8maxSum=8thisSum=thisSum+a[j]=-2

thisSum=0maxSum=8結(jié)果maxSum=8intmaxSubSum3(inta[],intn){intj,maxSum=0,thisSum=0;

for(j=0;j<n;j++)

{thisSum+=a[j];

if(thisSum<0)//若當(dāng)前子序列和為負(fù)數(shù)，重新開始下一子序列

thisSum=0;

if(maxSum<thisSum)//比較求最大連續(xù)子序列和

maxSum=thisSum;

}

returnmaxSum;}顯然該算法中僅掃描a一次，其算法的時(shí)間復(fù)雜度為O(n)。4.2.5求解冪集問題

【問題描述】對于給定的正整數(shù)n（n≥1），求1～n構(gòu)成的集合的所有子集（冪集）。

解法1：采用直接蠻力法求解，將1～n的存放在數(shù)組a中，求解問題變?yōu)闃?gòu)造集合a的所有子集。設(shè)集合a[0..2]={1，2，3}，其所有子集對應(yīng)的二進(jìn)制位及其十進(jìn)制數(shù)如下。子集對應(yīng)的二進(jìn)制位對應(yīng)的十進(jìn)制數(shù){}－－{1}0011{2}0102{1,2}0113{3}1004{1,3}1015{2,3}1106{1,2,3}1117對于含有n（n≥1）個(gè)元素的集合a，求冪集的過程如下：for(i=0;i<2n;i++) //窮舉a的所有子集并輸出{將i轉(zhuǎn)換為二進(jìn)制數(shù)b;

輸出b中為1的位對應(yīng)的a元素構(gòu)成一個(gè)子集;}顯然該算法的時(shí)間復(fù)雜度為O(n×2n)，屬于指數(shù)級的算法。voidinc(intb[],intn) //將b表示的二進(jìn)制數(shù)增1{for(inti=0;i<n;i++) //遍歷數(shù)組b{if(b[i]) //將元素1改為0 b[i]=0;else //將元素0改為1并退出for循環(huán){b[i]=1;break;}}}首先b[0..2]=000，每調(diào)用一次，b表示十進(jìn)制數(shù)的增加1例如：b[0..2]=000b=100第1次調(diào)用：b[0]=0，改為b[0]=1b=010第2次調(diào)用：第1個(gè)1改為0，第2個(gè)0改為=1b=110第3次調(diào)用：第1個(gè)0改為1b=001第4次調(diào)用：前2個(gè)1改為0，第3個(gè)0改為1第5次調(diào)用：前第1個(gè)0改為1b=101…voidPSet(inta[],intb[],intn) //求冪集{inti,k;intpw=(int)pow(2,n); //求2^nprintf("1～%d的冪集:\n",n);for(i=0;i<pw;i++) //執(zhí)行2^n次{ printf("{"); for(k=0;k<n;k++) //執(zhí)行n次 if(b[k]) printf("%d",a[k]); printf("}"); inc(b,n); //b表示的二進(jìn)制數(shù)增1}printf("\n");}解法2：采用增量蠻力法求解1～n的冪集，當(dāng)n=3時(shí)的求解過程。{}添加1{1}1的冪集：{{}，{1}}添加2{{2}，{1，2}}1~2的冪集：{{}，{1}，{2}，{1，2}}添加3{{3}，{1，3}，{2，3}，{1，2，3}}1~3的冪集：{{}，{1}，{2}，{1，2}{3}，{1，3},{2，3}，{1，2，3}}這種思路也是蠻力法方法：即窮舉1～n的所有子集。先建立一個(gè)空子集，對于i（1≤i≤n），每次都是在前面已建立的子集上添加元素i而構(gòu)成若干個(gè)子集，對應(yīng)的過程如下：voidf(intn) //求1～n的冪集ps{置ps={{}}; //在ps中加入一個(gè)空子集元素for(i=1;i<=n;i++)在ps的每個(gè)元素中添加i而構(gòu)成一個(gè)新子集;}

在實(shí)現(xiàn)算法時(shí)，用一個(gè)vector<int>容器表示一個(gè)集合元素，用vector<vector<int>>容器存放冪集（即集合的集合）。#include<stdio.h>#include<vector>usingnamespacestd;vector<vector<int>>ps; //存放冪集voidPSet(intn) //求1～n的冪集ps{vector<vector<int>>ps1; //子冪集vector<vector<int>>::iteratorit;//冪集迭代器vector<int>s;ps.push_back(s); //添加{}空集合元素for(inti=1;i<=n;i++) //循環(huán)添加1～n{ps1=ps; //ps1存放上一步得到的冪集for(it=ps1.begin();it!=ps1.end();++it) (*it).push_back(i); //在ps1的每個(gè)集合元素末尾添加ifor(it=ps1.begin();it!=ps1.end();++it) ps.push_back(*it); //將ps1的每個(gè)集合元素添加到ps中}}

算法分析：對于給定的n，每一個(gè)集合元素都要處理，有2n個(gè)，所以上述算法的時(shí)間復(fù)雜度為O(2n)。4.2.6求解0/1背包問題

【問題描述】有n個(gè)重量分別為{w1，w2，…，wn}的物品，它們的價(jià)值分別為{v1，v2，…，vn}，給定一個(gè)容量為W的背包。設(shè)計(jì)從這些物品中選取一部分物品放入該背包的方案，每個(gè)物品要么選中要么不選中，要求選中的物品不僅能夠放到背包中，而且具有最大的價(jià)值。并對下表所示的4個(gè)物品求出W=6時(shí)的所有解和最佳解。物品編號重量價(jià)值154234323411

【問題求解】對于n個(gè)物品、容量為W的背包問題，采用前面求冪集的方法求出所有的物品組合。對于每一種組合，計(jì)算其總重量sumw和總價(jià)值sumv，當(dāng)sumw小于等于W時(shí)，該組合是一種解，并通過比較將最佳方案保存在maxsumw和maxsumv中，最后輸出所有的解和最佳解。#include<stdio.h>#include<vector>usingnamespacestd;vector<vector<int>>ps; //存放冪集voidPSet(intn) //求1～n的冪集ps{vector<vector<int>>ps1; //子冪集vector<vector<int>>::iteratorit;//冪集迭代器vector<int>s;ps.push_back(s); //添加{}空集合元素for(inti=1;i<=n;i++) //循環(huán)添加1～n{ ps1=ps; //ps1存放上一步得到的冪集 for(it=ps1.begin();it!=ps1.end();++it) (*it).push_back(i); //在ps1的每個(gè)集合元素末尾添加i for(it=ps1.begin();it!=ps1.end();++it) ps.push_back(*it); //將ps1的每個(gè)集合元素添加到ps中}}voidKnap(intw[],intv[],intW) //求所有的方案和最佳方案{intcount=0; //方案編號intsumw,sumv; //當(dāng)前方案的總重量和總價(jià)值intmaxi,maxsumw=0,maxsumv=0; //最佳方案的編號、總重量和總價(jià)值vector<vector<int>>::iteratorit; //冪集迭代器vector<int>::iteratorsit; //冪集集合元素迭代器printf("序號\t選中物品\t總重量\t總價(jià)值\t能否裝入\n");for(it=ps.begin();it!=ps.end();++it) //掃描ps中每一個(gè)集合元素{ printf("%d\t",count+1); sumw=sumv=0; printf("{"); for(sit=(*it).begin();sit!=(*it).end();++sit) {printf("%d",*sit); sumw+=w[*sit-1]; //w數(shù)組下標(biāo)從0開始 sumv+=v[*sit-1]; //v數(shù)組下標(biāo)從0開始 }printf("}\t\t%d\t%d",sumw,sumv);if(sumw<=W){printf("能\n");if(sumv>maxsumv) //比較求最優(yōu)方案{maxsumw=sumw;maxsumv=sumv;maxi=count;}}elseprintf("否\n");count++; //方案編號增加1}printf("最佳方案為:");printf("選中物品");printf("{");for(sit=ps[maxi].begin();sit!=ps[maxi].end();++sit) printf("%d",*sit);printf("},");printf("總重量:%d,總價(jià)值:%d\n",maxsumw,maxsumv);}voidmain(){intn=4,W=6;intw[]={5,3,2,1};intv[]={4,4,3,1};PSet(n);printf("0/1背包的求解方案\n",n);Knap(w,v,W);}程序執(zhí)行結(jié)果如下：0/1背包的求解方案序號 選中物品 總重量 總價(jià)值 能否裝入

1 {} 0 0 能

2 {1} 5 4 能

3 {2} 3 4 能

4 {12} 8 8 否

5 {3} 2 3 能

6 {13} 7 7 否

7 {23} 5 7 能

8 {123} 10 11 否

9 {4} 1 1 能

10 {14} 6 5 能

11 {24} 4 5 能

12 {124} 9 9 否

13 {34} 3 4 能

14 {134} 8 8 否

15 {234} 6 8 能

16 {1234} 11 12 否最佳方案為選中物品:{234},總重量:6,總價(jià)值:84.2.7求解全排列問題【問題描述】對于給定的正整數(shù)n（n≥1），求1～n的所有全排列?！締栴}求解】這里采用增量蠻力法求解。產(chǎn)生1～3全排列的過程如下：初始為11將2插入到各位上將3插入到各位上1221123132312213231321求解所需的最終結(jié)果求解的中間結(jié)果voidInsert(vector<int>s,inti,vector<vector<int>>&ps1)//在每個(gè)集合元素中間插入i得到ps1{vector<int>s1;vector<int>::iteratorit;for(intj=0;j<i;j++) //在s(含i-1個(gè)整數(shù))的每個(gè)位置插入i{s1=s;it=s1.begin()+j; //求出插入位置s1.insert(it,i); //插入整數(shù)ips1.push_back(s1); //添加到ps1中}}例如：12插入3312132123voidPerm(intn) //求1～n的所有全排列{vector<vector<int>>ps1; //臨時(shí)存放子排列vector<vector<int>>::iteratorit;//全排列迭代器vector<int>s,s1;s.push_back(1);ps.push_back(s); //添加{1}集合元素for(inti=2;i<=n;i++) //循環(huán)添加1～n{ps1.clear(); //ps1存放插入i的結(jié)果for(it=ps.begin();it!=ps.end();++it)

Insert(*it,i,ps1); //在每個(gè)集合元素中間插入i得到ps1ps=ps1;}}

【算法分析】對于給定的正整數(shù)n，每一種全排列都必須處理，有n!種，所以上述算法的時(shí)間復(fù)雜度為O(n*n!)。4.2.8求解任務(wù)分配問題

【問題描述】有n（n≥1）個(gè)任務(wù)需要分配給n個(gè)人執(zhí)行，每個(gè)任務(wù)只能分配給一個(gè)人，每個(gè)人只能執(zhí)行一個(gè)任務(wù)。

第i個(gè)人執(zhí)行第j個(gè)任務(wù)的成本是c[i][j]（1≤i，j≤n）。求出總成本最小的分配方案。

【問題求解】所謂一種分配方案就是由第i個(gè)人執(zhí)行第j個(gè)任務(wù)，用（a1，a2，…，an）表示，即第1個(gè)人執(zhí)行第a1個(gè)任務(wù)，第2個(gè)人執(zhí)行第a2個(gè)任務(wù)，以此類推。全部的分配方案恰好是1～n的全排列。

這里采用增量窮舉法求出所有的分配方案ps（全排列），再計(jì)算出每種方案的成本，比較求出最小成本的方案，即最優(yōu)方案。以n=4，成本如下表所示為例討論。人員任務(wù)1任務(wù)2任務(wù)3任務(wù)4192782643735818476944個(gè)人員、4個(gè)任務(wù)的信息//問題表示intn=4;intc[MAXN][MAXN]={{9,2,7,8},{6,4,3,7},{5,8,1,8},{7,6,9,4}};vector<vector<int>>ps; //存放全排列voidInsert(vector<int>s,inti,vector<vector<int>>&ps1)//在每個(gè)集合元素中間插入i得到ps1{vector<int>s1;vector<int>::iteratorit;for(intj=0;j<i;j++) //在s(含i-1個(gè)整數(shù))的每個(gè)位置插入i{ s1=s; it=s1.begin()+j; //求出插入位置 s1.insert(it,i); //插入整數(shù)i ps1.push_back(s1); //添加到ps1中}}voidPerm(intn) //求1～n的所有全排列{vector<vector<int>>ps1; //臨時(shí)存放子排列vector<vector<int>>::iteratorit;//全排列迭代器vector<int>s,s1;s.push_back(1);ps.push_back(s); //添加{1}集合元素for(inti=2;i<=n;i++) //循環(huán)添加1～n{ ps1.clear(); //ps1存放插入i的結(jié)果 for(it=ps.begin();it!=ps.end();++it) Insert(*it,i,ps1); //在每個(gè)集合元素中間插入i得到ps1 ps=ps1;}}voidAllocate(intn,int&mini,int&minc)//求任務(wù)分配問題的最優(yōu)方案{Perm(n); //求出全排列psfor(inti=0;i<ps.size();i++) //求每個(gè)方案的成本{intcost=0;for(intj=0;j<ps[i].size();j++) cost+=c[j][ps[i][j]-1];if(cost<minc) //比較求最小成本的方案{minc=cost;mini=i;}}}voidmain(){intmincost=INF,mini;

//mincost為最小成本,mini為ps中最優(yōu)方案編號Allocate(n,mini,mincost);printf("最優(yōu)方案:\n");for(intk=0;k<ps[mini].size();k++) printf("第%d個(gè)人安排任務(wù)%d\n",k+1,ps[mini][k]);printf("總成本=%d\n",mincost);}程序的執(zhí)行結(jié)果：最優(yōu)方案:

第1個(gè)人安排任務(wù)2

第2個(gè)人安排任務(wù)1

第3個(gè)人安排任務(wù)3

第4個(gè)人安排任務(wù)4總成本=13人員任務(wù)1任務(wù)2任務(wù)3任務(wù)419278264373581847694

蠻力法所依賴的基本技術(shù)是遍歷技術(shù)，采用一定的策略將待求解問題的所有元素依次處理一次，從而找出問題的解。而在遍歷過程中，很多求解問題都可以采用遞歸方法來實(shí)現(xiàn)，如二叉樹的遍歷和圖的遍歷等。4.3

遞歸在蠻力法中的應(yīng)用4.3.1用遞歸方法求解冪集問題前面介紹了兩種采用蠻力法求解由1～n整數(shù)構(gòu)成的集合的冪集的方法，這里以解法2為基礎(chǔ)。

同樣采用vector<vector<int>>容器ps存放冪集，并作為全局變量。初始時(shí)ps={{}}。f(i,n,p)

輸出冪集p 當(dāng)i>nf(i,n,p)

將整數(shù)i添加到p中原有每個(gè)子集中產(chǎn)生新子集; 否則

并將所有新子集加入到p中;

f(i+1,n,p);大問題：f(i，n)用于添加i～n整數(shù)（共需添加n-i+1個(gè)整數(shù)）產(chǎn)生的冪集ps。小問題：f(i+1，n)用于添加i+1～n的整數(shù)（共需添加n-i個(gè)整數(shù)）產(chǎn)生的冪集ps。f(1，n)就是生成1～n的整數(shù)集合對應(yīng)的冪集ps。vector<vector<int>>ps; //存放冪集voidInserti(inti)//向冪集ps中每個(gè)集合元素添加i并插入到ps中{vector<vector<int>>ps1; //子冪集vector<vector<int>>::iteratorit; //冪集迭代器ps1=ps; //ps1存放原來的冪集for(it=ps1.begin();it!=ps1.end();++it)(*it).push_back(i); //在ps1的每個(gè)集合元素末尾添加ifor(it=ps1.begin();it!=ps1.end();++it)ps.push_back(*it); //將ps1的每個(gè)集合元素添加到ps中}voidPSet(inti,intn)//求1～n的冪集ps{if(i<=n){ Inserti(i); //將i插入到現(xiàn)有子集中產(chǎn)生新子集

PSet(i+1,n); //遞歸調(diào)用}}4.3.2用遞歸方法求解全排列問題

同樣采用vector<vector<int>>容器ps存放全排列，并作為全局變量。首先初始化ps={{1}}。

大問題：f(i，n)用于添加i～n整數(shù)（共需添加n-i+1個(gè)整數(shù)）產(chǎn)生的全排列ps。顯然f(2，n)就是生成1～n的整數(shù)集合對應(yīng)的全排列ps。

小問題：f(i+1，n)用于添加i+1～n整數(shù)（共需添加n-i個(gè)整數(shù)）產(chǎn)生的全排列。f(i，n)

產(chǎn)生全排序ps 當(dāng)i>n時(shí)f(i，n)

置ps為{{1}}，取出ps的每個(gè)集合元素s，

在s的每個(gè)位置插入i; 否則

將插入i后的新集合元素添加的ps1中;

置ps=ps1;

f(i+1，n);vector<vector<int>>ps; //存放全排列voidInsert(vector<int>s,inti,vector<vector<int>>&ps1)//在每個(gè)集合元素中間插入i得到ps1{vector<int>s1;vector<int>::iteratorit;for(intj=0;j<i;j++) //在s(含i-1個(gè)整數(shù))的每個(gè)位置插入i{ s1=s; it=s1.begin()+j; //求出插入位置 s1.insert(it,i); //插入整數(shù)i ps1.push_back(s1); //添加到ps1中}}voidPerm(inti,intn) //求1～n的全排列ps{vector<vector<int>>::iteratorit;//全排列迭代器if(i<=n){vector<vector<int>>ps1;//臨時(shí)存放子排列for(it=ps.begin();it!=ps.end();++it) Insert(*it,i,ps1); //在每個(gè)集合元素中間插入i得到ps1ps=ps1;Perm(i+1,n);

//繼續(xù)添加整數(shù)i+1}}4.3.3用遞歸方法求解組合問題

【問題描述】求1～n的正整數(shù)中取k（k≤n）個(gè)不重復(fù)整數(shù)的所有組合。

【問題求解】用數(shù)組元素a[0..k-1]來保存一個(gè)組合，由于一個(gè)組合中所有元素不會重復(fù)出現(xiàn)，規(guī)定a中所有元素按遞增排列。

大問題：f(n,k)從1～n中任取k個(gè)數(shù)的所有組合。

小問題：f(m,k-1)從1～m中任取k-1個(gè)數(shù)的所有組合。因?yàn)閍中元素遞增排列，所以a[k-1]的取值范圍只能為k～n，當(dāng)a[k-1]確定為i后，合并f(i-1,k-1)的一個(gè)結(jié)果便構(gòu)成f(n,k)的一個(gè)組合結(jié)果。f(n,k)a[0]a[k-2]a[k-1]：i…f(i-1,k-1)a[k-1]即i只能取k～n值對應(yīng)的遞歸模型如下：f(n，k)

輸出a中的一種組合

當(dāng)k=0f(n，k)

i取值從k到n: 當(dāng)k>0{a[k-1]=i;f(i-1，k-1)}f(n,k)a[0]a[k-2]a[k-1]：i…f(i-1,k-1)a[k-1]即i只能取k～n值求1～5中取3個(gè)整數(shù)組合的過程如下所示（a[0..2]放一個(gè)組合）a[2]取3～5值k=3,考慮a[2]k=2,考慮a[1]k=1,考慮a[0]a[1]=2a[0]=1得到123a[1]=2a[0]=1a[1]=3a[1]=4得到125a[0]=1得到135a[0]=2得到235a[0]=1得到145a[0]=2得到245a[0]=3得到345a[2]=3a[2]=4a[2]=5a[1]=2a[1]=3a[0]=1得到124a[0]=1得到134a[0]=2得到234voidcomb(intn,intk) //求1..n中k個(gè)整數(shù)的組合{if(k==0) //k為0時(shí)輸出一個(gè)組合dispacomb();else{ for(inti=k;i<=n;i++){a[k-1]=i; //a[k-1]位置取k～n的整數(shù)comb(i-1,k-1);}}}鄰接矩陣鄰接表4.4

圖的深度優(yōu)先和廣度優(yōu)先遍歷4.4.1圖的存儲結(jié)構(gòu)鄰接矩陣是表示頂點(diǎn)之間相鄰關(guān)系的矩陣。設(shè)G=(V,E)是含有n（n＞0）個(gè)頂點(diǎn)的圖，各頂點(diǎn)的編號為0～(n-1)，則G的鄰接矩陣A是n階方陣，其定義如下：（1）如果G是不帶權(quán)無向圖，則：A[i][j]=1 若(i,j)∈E(G)A[i][j]=0 其他（2）如果G是不帶權(quán)有向圖，則：A[i][j]=1 若<i,j>∈E(G)A[i][j]=0 其他1.鄰接矩陣存儲方法（3）如果G是帶權(quán)無向圖，則：A[i][j]=wij

若i≠j且(i,j)∈E(G)A[i][j]=0 i=jA[i][j]=∞ 其他（4）如果G是帶權(quán)有向圖，則：A[i][j]=wij

若i≠j且<i,j>∈E(G)A[i][j]=0 i=jA[i][j]=∞ 其他鄰接矩陣的類型定義如下：#defineMAXV<最大頂點(diǎn)個(gè)數(shù)>typedefstruct{intno; //頂點(diǎn)編號chardata[MAXL]; //頂點(diǎn)其他信息}VertexType; //頂點(diǎn)類型typedefstruct{intedges[MAXV][MAXV]; //鄰接矩陣的邊數(shù)組intn,e; //頂點(diǎn)數(shù)，邊數(shù)

VertexTypevexs[MAXV]; //存放頂點(diǎn)信息}

MGraph; //完整的圖鄰接矩陣類型2.鄰接表存儲方法圖的鄰接表存儲方法是一種鏈?zhǔn)酱鎯Y(jié)構(gòu)。圖的每個(gè)頂點(diǎn)建立一個(gè)單鏈表，第i（0≤i≤n-1）個(gè)單鏈表中的結(jié)點(diǎn)表示依附于頂點(diǎn)i的邊。每個(gè)單鏈表上附設(shè)一個(gè)表頭結(jié)點(diǎn)，將所有表頭結(jié)點(diǎn)構(gòu)成一個(gè)表頭結(jié)點(diǎn)數(shù)組。typedefstructANode{intadjvex; //該邊的終點(diǎn)編號intweight; //該邊的權(quán)值structANode*nextarc; //指向下一條邊的指針}ArcNode; //邊結(jié)點(diǎn)類型typedefstructVnode{chardata[MAXL]; //頂點(diǎn)其他信息

ArcNode*firstarc; //指向第一條邊}VNode; //鄰接表頭結(jié)點(diǎn)類型typedefVNode

AdjList[MAXV]; //AdjList是鄰接表類型typedefstruct{AdjListadjlist; //鄰接表intn,e; //圖中頂點(diǎn)數(shù)n和邊數(shù)e}ALGraph;4.4.2深度優(yōu)先遍歷

從給定圖中任意指定的頂點(diǎn)（稱為初始點(diǎn)）出發(fā)，按照某種搜索方法沿著圖的邊訪問圖中的所有頂點(diǎn)，使每個(gè)頂點(diǎn)僅被訪問一次，這個(gè)過程稱為圖的遍歷。

為了避免同一個(gè)頂點(diǎn)被重復(fù)訪問，必須記住每個(gè)被訪問過的頂點(diǎn)。為此，設(shè)置一個(gè)訪問標(biāo)志數(shù)組visited[]，當(dāng)頂點(diǎn)i被訪問過時(shí)，數(shù)組中元素visited[i]置為1；否則置為0。

深度優(yōu)先搜索的過程是：（1）從圖中某個(gè)初始頂點(diǎn)v出發(fā)，首先訪問初始頂點(diǎn)v。

（2）然后選擇一個(gè)與頂點(diǎn)v相鄰且沒被訪問過的頂點(diǎn)w為初始頂點(diǎn)，再從w出發(fā)進(jìn)行深度優(yōu)先搜索。

（3）重復(fù)直到圖中與當(dāng)前頂點(diǎn)v鄰接的所有頂點(diǎn)都被訪問過為止。顯然，這個(gè)搜索過程是個(gè)遞歸過程。以鄰接矩陣為存儲結(jié)構(gòu)的深度優(yōu)先搜索算法voidDFS(MGraphg,intv) //鄰接矩陣的DFS算法{intw;printf("%3d",v); //輸出被訪問頂點(diǎn)的編號visited[v]=1; //置已訪問標(biāo)記for(w=0;w<g.n;w++) //找頂點(diǎn)v的所有相鄰點(diǎn)if(g.edges[v][w]!=0&&g.edges[v][w]!=INF &&visited[w]==0)

DFS(g,w);

//找頂點(diǎn)v的未訪問過的相鄰點(diǎn)w}以鄰接表為存儲結(jié)構(gòu)的深度優(yōu)先搜索算法：voidDFS(ALGraph*G,intv) //鄰接表的DFS算法{ArcNode*p;printf("%3d",v); //輸出被訪問頂點(diǎn)的編號visited[v]=1; //置已訪問標(biāo)記p=G->adjlist[v].firstarc; //p指向頂點(diǎn)v的第一個(gè)鄰接點(diǎn)while(p!=NULL){if(visited[p->adjvex]==0)//若p->adjvex頂點(diǎn)未訪問,遞歸訪問它

DFS(G,p->adjvex);p=p->nextarc; //p指向頂點(diǎn)v的下一個(gè)鄰接點(diǎn)}}

【例4.6】假設(shè)圖G采用鄰接表存儲，設(shè)計(jì)一個(gè)算法判斷圖G中從頂點(diǎn)u到v是否存在簡單路徑。

解：所謂簡單路徑是指路徑上的頂點(diǎn)不重復(fù)。采用深度優(yōu)先遍歷的方法，從頂點(diǎn)u出發(fā)搜索到頂點(diǎn)v的過程如下：DFS(G,u,v)DFS(G,u1,v)DFS(G,v,v)…boolExistPath(ALGraph*G,intu,intv)//判斷G中從頂點(diǎn)u到v是否存在簡單路徑{intw;ArcNode*p;visited[u]=1; //置已訪問標(biāo)記if(u==v) //找到了一條路徑，返回truereturntrue;p=G->adjlist[u].firstarc; //p指向頂點(diǎn)u的第一個(gè)相鄰點(diǎn)while(p!=NULL){ w=p->adjvex; //w為頂點(diǎn)u的相鄰頂點(diǎn) if(visited[w]==0) //若w頂點(diǎn)未訪問,遞歸訪問它 {boolflag=ExistPath(G,w,v); if(flag)returntrue; } p=p->nextarc; //p指向頂點(diǎn)u的下一個(gè)相鄰點(diǎn)}returnfalse; //沒有找到v，返回false}

【例4.7】假設(shè)圖G采用鄰接表存儲，設(shè)計(jì)一個(gè)算法輸出圖G中從頂點(diǎn)u到v的一條簡單路徑（假設(shè)圖G中從頂點(diǎn)u到v至少有一條簡單路徑）。

解：采用深度優(yōu)先遍歷的方法，f(G，u，v，apath，path)搜索圖G中從頂點(diǎn)u到v的一條簡單路徑path。

通過頂點(diǎn)u在圖G中搜索，當(dāng)u=v時(shí)說明找到一條從u到v的簡單路徑，將apath復(fù)制到path中并返回。否則繼續(xù)深度優(yōu)先遍歷。voidFindaPath(ALGraph*G,intu,intv,vector<int>apath,vector<int>&path){intw;ArcNode*p;visited[u]=1;apath.push_back(u); //頂點(diǎn)u加入到apath路徑中if(u==v) //找到一條路徑{ path=apath; //將apath復(fù)制到path return; //返回true}p=G->adjlist[u].firstarc; //p指向頂點(diǎn)u的第一個(gè)相鄰點(diǎn)while(p!=NULL){ w=p->adjvex; //相鄰點(diǎn)的編號為w if(visited[w]==0) FindaPath(G,w,v,apath,path); p=p->nextarc; //p指向頂點(diǎn)u的下一個(gè)相鄰點(diǎn)}}4.4.4廣度優(yōu)先遍歷

廣度優(yōu)先搜索的過程是：

（1）首先訪問初始頂點(diǎn)v。

（2）接著訪問頂點(diǎn)v的所有未被訪問過的鄰接點(diǎn)v1，v2，…，vt。

（3）然后再按照v1，v2，…，vt的次序，訪問每一個(gè)頂點(diǎn)的所有未被訪問過的鄰接點(diǎn)，依次類推，直到圖中所有和初始頂點(diǎn)v有路徑相通的頂點(diǎn)都被訪問過為止。

以鄰接矩陣為圖的存儲結(jié)構(gòu)，采用廣度優(yōu)先搜索圖時(shí)，需要使用一個(gè)隊(duì)列。voidBFS(MGraphg,intv) //鄰接矩陣的BFS算法{queue<int>qu; //定義一個(gè)隊(duì)列quintvisited[MAXV]; //定義存放結(jié)點(diǎn)的訪問標(biāo)志的數(shù)組intw,i;memset(visited,0,sizeof(visited)); //訪問標(biāo)志數(shù)組初始化printf("%3d",v); //輸出被訪問頂點(diǎn)的編號visited[v]=1; //置已訪問標(biāo)記qu.push(v); //v進(jìn)隊(duì)while(!qu.empty()) //隊(duì)列不空時(shí)循環(huán){w=qu.front();qu.pop(); //出隊(duì)頂點(diǎn)wfor(i=0;i<g.n;i++) //找與頂點(diǎn)w相鄰的頂點(diǎn)if(g.edges[w][i]!=0&&g.edges[w][i]!=INF&&visited[i]==0){ //若當(dāng)前鄰接頂點(diǎn)i未被訪問printf("%3d",i); //訪問相鄰頂點(diǎn)visited[i]=1; //置該頂點(diǎn)已被訪問的標(biāo)志qu.push(i); //該頂點(diǎn)進(jìn)隊(duì)}}printf("\n");}以鄰接表為圖的存儲結(jié)構(gòu)，采用廣度優(yōu)先搜索圖時(shí)，需要使用一個(gè)隊(duì)列。voidBFS(ALGraph*G,intv) //鄰接表的BFS算法{ArcNode*p;queue<int>qu; //定義一個(gè)隊(duì)列quintvisited[MAXV],w; //定義存放頂點(diǎn)的訪問標(biāo)志的數(shù)組memset(visited,0,sizeof(visited)); //訪問標(biāo)志數(shù)組初始化printf("%3d",v); //輸出被訪問頂點(diǎn)的編號visited[v]=1; //置已訪問標(biāo)記qu.push(v); //v進(jìn)隊(duì)while(!qu.empty()) //隊(duì)列不空時(shí)循環(huán){w=qu.front();qu.pop(); //出隊(duì)頂點(diǎn)wp=G->adjlist[w].firstarc; //找頂點(diǎn)w的第一個(gè)鄰接點(diǎn)while(p!=NULL){if(visited[p->adjvex]==0) //若當(dāng)前鄰接頂點(diǎn)未被訪問{printf("%3d",p