目錄：

• • • 7.1　簡(jiǎn)單枚舉
    • 7.2　枚舉排列
    • 7.3　子集生成

7.1　簡(jiǎn)單枚舉

例題7-1　除法（Division, UVa 725）
輸入正整數(shù)n，按從小到大的順序輸出所有形如abcde/fghij = n的表達(dá)式，其中a～j恰好 為數(shù)字0～9的一個(gè)排列（可以有前導(dǎo)0），2≤n≤79。
樣例輸入：
62
樣例輸出：
79546 / 01283 = 62
94736 / 01528 = 62

#include<iostream> using namespace std;int pjj(int m , int n){int k=0;int a[10]={0};while(m){a[k++]=m%10;m=m/10;}while(n){a[k++]=n%10;n=n/10;} for(int i=0;i<10;++i)for(int j=i+1;j<10;++j)if(a[i]==a[j]) return -1;return 1; }int main(){int n,k,i;cin>>n;for(i=1234;i*n<=98765;++i){k=i*n;if(pjj(i,k)==1) {cout << k << "/" ; if(i < 10000) cout <<"0"; cout << i << "=" << n <<endl;}} }

分析：只需要枚舉fghij就可以算出abcde，然后判斷是否 所有數(shù)字都不相同即可

例題7-2　最大乘積（Maximum Product, UVa 11059）
輸入n個(gè)元素組成的序列S，你需要找出一個(gè)乘積最大的連續(xù)子序列。如果這個(gè)最大的乘 積不是正數(shù)，應(yīng)輸出0（表示無解）。1≤n≤18，-10≤Si≤10。
樣例輸入：
3
2 4-3
5
2 5 -1 2 -1
樣例輸出：
8
20

#include<iostream> using namespace std; int main(){int n;int a[100];while(cin>>n){long long maxm=-100,tmp;int i,j;for(i=0;i<n;++i){cin>>a[i];} for(i=0;i<n;++i){tmp=1;for(j=i;j<n;++j){tmp*=a[j];if(maxm<tmp){maxm=tmp;}}}if(maxm<=0) cout<<'0'<<endl;else cout<<maxm<<endl;}}

分析：連續(xù)子序列有兩個(gè)要素：起點(diǎn)和終點(diǎn)，因此只需枚舉起點(diǎn)和終點(diǎn)即可，其中起點(diǎn)為i，終點(diǎn)為j。

例題7-3　分?jǐn)?shù)拆分（Fractions Again?!, UVa 10976）
輸入正整數(shù)k，找到所有的正整數(shù)x≥y，使得 1/k=1/x+1/y
樣例輸入：
2
12
樣例輸出：
2
1/2 = 1/6 + 1/3
1/2 = 1/4 + 1/4
8
1/12 = 1/156 + 1/13
1/12 = 1/84 + 1/14
1/12 = 1/60 + 1/15
1/12 = 1/48 + 1/16
1/12 = 1/36 + 1/18
1/12 = 1/30 + 1/20
1/12 = 1/28 + 1/21
1/12 = 1/24 + 1/24

#include<iostream> using namespace std; int main(){double k,x;int i,sum;while(cin>>k){sum=0;for(i=k+1;i<=2*k;++i){x=i*k/(i-k);if(x==(int)x)sum++;}cout<<sum<<endl;for(i=k+1;i<=2*k;++i){x=i*k/(i-k);if(x==(int)x)cout<<"1/"<<k<<'='<<"1/"<<x<<'+'<<"1/"<<i<<endl;}}}

分析：
既然要求找出所有的x、y，枚舉對(duì)象自然就是x、y了。可問題在于，枚舉的范圍如何？ 從1/12=1/156+1/13可以看出，x可以比y大很多。難道要無休止地枚舉下去？當(dāng)然不是。由 于x≥y，有 1/k<=1/y+1/y因此 ，即y≤2k。這樣，只需要在2k范圍之內(nèi)枚舉y，然后根據(jù)y嘗試 計(jì)算出x即可

7.2　枚舉排列

例7-2-1：輸入整數(shù)n，按字典序從小到大的順序輸出前n個(gè)數(shù)的 所有排列。
分析：兩個(gè)序列的字典序大小關(guān)系等價(jià)于從頭開始第一個(gè)不相同位置處的大 小關(guān)系。例如，(1,3,2) < (2,1,3)，字典序最小的排列是(1, 2, 3, 4,…, n)，最大的排列是(n, n-1, n-2,…, 1)。n=3時(shí)，所有排列的排序結(jié)果是(1, 2, 3)、(1, 3, 2)、(2, 1, 3)、(2, 3, 1)、(3, 1, 2)、 (3, 2, 1)。
以1開頭的排列的特點(diǎn)是：第一位是1，后面是2～9的排列。根據(jù)字典序的定義，這些2 ～9的排列也必須按照字典序排列。換句話說，需要“按照字典序輸出2～9的排列”，不過需 注意的是，在輸出時(shí)，每個(gè)排列的最前面要加上“1”。這樣一來，所設(shè)計(jì)的遞歸函數(shù)需要以 下參數(shù)：
1.已經(jīng)確定的“前綴”序列，以便輸出。
2.需要進(jìn)行全排列的元素集合，以便依次選做第一個(gè)元素

void print_permutation(序列A, 集合S) { if(S為空) 輸出序列A; else 按照從小到大的順序依次考慮S的每個(gè)元素v { print_permutation(在A的末尾填加v后得到的新序列, S-{v}); } }

下面考慮程序?qū)崿F(xiàn)。不難想到用數(shù)組表示序列A，而集合S根本不用保存，因?yàn)樗梢?由序列A完全確定——A中沒有出現(xiàn)的元素都可以選。C語言中的函數(shù)在接受數(shù)組參數(shù)時(shí)無法 得知數(shù)組的元素個(gè)數(shù)，所以需要傳一個(gè)已經(jīng)填好的位置個(gè)數(shù)，或者當(dāng)前需要確定的元素位置 cur，代碼如下：

#include<iostream> #include<cstdio> using namespace std; int a[1000]; void print_permutation(int n,int *a,int cur); int main(){int n;cin>>n;print_permutation( n, a, 0); }void print_permutation(int n,int *a,int cur){if(cur==n) {for(int i=0;i<n;++i) printf("%d ",a[i]);printf("\n") ;}else{for(int i=1;i<=n;++i){//改變前綴int ok = 1;for(int j=0;j<cur;++j){//如果i已經(jīng)在A[0]~A[cur-1]出現(xiàn)過，則不能再選if(a[j]==i) ok = 0;}if(ok){a[cur]=i;print_permutation( n, a, cur + 1);//每一個(gè)前綴的可能排序}}} }

遞歸邊界是S為空 的情形，這很好理解：現(xiàn)在序列A就是一個(gè)完整的排列，直接輸出即可。接下來按照從小到大的順序考慮S中的每個(gè)元素，每次遞歸調(diào)用以A開頭.
循環(huán)變量i是當(dāng)前考察的A[cur]。為了檢查元素i是否已經(jīng)用過，上面的程序用到了一個(gè) 標(biāo)志變量ok，初始值為1（真），如果發(fā)現(xiàn)有某個(gè)A[j]==i時(shí)，則改為0（假）。如果最終ok仍 為1，則說明i沒有在序列中出現(xiàn)過，把它添加到序列末尾（A[cur]=i）后遞歸調(diào)用。

例7-2-2生成可重集的排列

如果把問題改成：輸入數(shù)組P，并按字典序輸出數(shù)組A各元素的所有全排列，則需要對(duì) 上述程序進(jìn)行修改——把P加到print_permutation的參數(shù)列表中，然后把代碼中的if(A[j] == i) 和A[cur] = i分別改成if(A[j] == P[i])和A[cur] = P[i]。這樣，只要把P的所有元素按從小到大的順序排序，然后調(diào)用print_permutation(n, P, A, 0)即可，如下面代碼所示。

#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int a[1000];int p[1000]; void print_permutation(int *p,int n,int *a,int cur); int main(){int n,i;cin>>n;for(i=0;i<n;++i){cin>>p[i];}sort(p,p+n);print_permutation(p, n, a, 0); }void print_permutation(int *p,int n,int *a,int cur){int i;if(cur==n) {for(int i=0;i<n;++i) printf("%d ",a[i]);printf("\n") ;}else{for(int i=0;i<n;++i){//改變前綴int ok = 1;for(int j=0;j<cur;++j){//如果i已經(jīng)在A[0]~A[cur-1]出現(xiàn)過，則不能再選if(a[j]==p[i]) ok = 0;}if(ok){a[cur]=p[i];print_permutation( p, n, a, cur + 1);//每一個(gè)前綴的可能排序}}} }

這個(gè)方法看上去不錯(cuò)，可惜有一個(gè)小問題：輸入1 1 1后，程序什么也不輸出（正確答案 應(yīng)該是唯一的全排列1 1 1），原因在于，這樣禁止A數(shù)組中出現(xiàn)重復(fù)，而在P中本來就有重 復(fù)元素時(shí)，這個(gè)“禁令”是錯(cuò)誤的。
一個(gè)解決方法是統(tǒng)計(jì)A[0]～A[cur-1]中P[i]的出現(xiàn)次數(shù)c1，以及P數(shù)組中P[i]的出現(xiàn)次數(shù) c2。只要c1 < c2，就能遞歸調(diào)用

結(jié)果又如何呢？輸入1 1 1，輸出了27個(gè)1 1 1。遺漏沒有了，但是出現(xiàn)了重復(fù)：先試著把 第1個(gè)1作為開頭，遞歸調(diào)用結(jié)束后再嘗試用第2個(gè)1作為開頭，遞歸調(diào)用結(jié)束后再嘗試用第3 個(gè)1作為開頭，再一次遞歸調(diào)用。可實(shí)際上這3個(gè)1是相同的，應(yīng)只遞歸1次，而不是3次。

換句話說，我們枚舉的下標(biāo)i應(yīng)不重復(fù)、不遺漏地取遍所有P[i]值。由于P數(shù)組已經(jīng)排過 序，所以只需檢查P的第一個(gè)元素和所有“與前一個(gè)元素不相同”的元素，即只需在“for(i = 0; i < n; i++)”和其后的花括號(hào)之前加上“if(!i || P[i] != P[i-1])”即可。

#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int a[1000];int p[1000]; void print_permutation(int *p,int n,int *a,int cur); int main(){int n,i;cin>>n;for(i=0;i<n;++i){cin>>p[i];}sort(p,p+n);print_permutation(p, n, a, 0); }void print_permutation(int *p,int n,int *a,int cur){int i;if(cur==n) {for(int i=0;i<n;++i) printf("%d ",a[i]);printf("\n") ;}else for(int i = 0; i < n; i++) { if(!i || p[i] != p[i-1]){int c1 = 0,c2 = 0; for(int j = 0; j < cur; j++) if(a[j] == p[i]) c1++; for(int j = 0; j < n; j++) if(p[i] == p[j]) c2++; if(c1 < c2) { a[cur] = p[i]; print_permutation(p,n, a, cur+1); } }}}

總結(jié)：
如果某問題的解可以由多個(gè)步驟得到，而每個(gè)步驟都有若干種選擇（這些候 選方案集可能會(huì)依賴于先前作出的選擇），且可以用遞歸枚舉法實(shí)現(xiàn)，則它的工作方式可以 用解答樹來描述。

例7-2-3，利用next_permutation解答
枚舉所有排列的另一個(gè)方法是從字典序最小排列開始，不停調(diào)用“求下一個(gè)排列”的過 程。如何求下一個(gè)排列呢？C++的STL中提供了一個(gè)庫函數(shù)next_permutation

#include<cstdio> #include<algorithm> //包含next_permutation using namespace std; int main( ) { int n, p[10]; scanf("%d", &n); for(int i = 0; i < n; i++) scanf("%d", &p[i]); sort(p, p+n); //排序，得到p的最小排列 do { for(int i = 0; i < n; i++){printf("%d ", p[i]); //輸出排列p}printf("\n"); } while(next_permutation(p, p+n)); //求下一個(gè)排列 return 0; }

上述代碼同樣適用于可重集。
總結(jié)：枚舉排列的常見方法有兩種：一是遞歸枚舉，二是用STL中的 next_permutation

7.3　子集生成

總結(jié)

以上是生活随笔為你收集整理的算法竞赛入门经典 第七章 总结的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。