1、程序設(shè)計培訓(xùn)之5：搜索算法2010年4月20日 一個從起始狀態(tài)到達目標狀態(tài)包含多步操作，而每一步操作又有幾種可能，只有正確的操作才能達到目標（如八皇后問題），這樣的問題可以看做是一個樹。如果按照1-2-4-5-3-6-7的順序，叫深度優(yōu)先(DFS)如果按照1-2-3-4-5-6-7的順序，叫廣度優(yōu)先(BFS)1234567概述void DFS(int k) /處理第k步 if (k=n) /已經(jīng)處理到第n步，到達目的狀態(tài) 輸出結(jié)果 else /處理第k步 for (int i=1; i=m; i+) /第k步中有m種可能 處理第k步 DFS(k+1)；/進入第k+1步 深度優(yōu)先(DFS)模板1

2、：輸出1-m個數(shù)中取n個數(shù)的所有多重排列。例如n=2，m=3的所有多重排列為：1 11 21 32 12 22 33 13 23 3例1：多重排列問題/從1到m中取n個數(shù)，允許重復(fù)取數(shù)#include using namespace std;int n,m, a10;void DFS(int k) if (k=n) for (int i=0; in; i+) coutai ; coutendl; else for (int i=1; imn; DFS(0); return 0; 輸出1-m個數(shù)中取n個數(shù)的所有排列。例如n=2，m=3的所有排列為：1 21 32 12 33 13 2例2：排列問

3、題/從1到m中取n個數(shù)，不允許重復(fù)取數(shù)#include using namespace std;int n,m, a10; bool bz10;void DFS(int k) if (k=n) for (int i=0; in; i+) coutai ; coutendl; else for (int i=1; imn; DFS(0); return 0; /從1到m中取n個數(shù)，不允許重復(fù)取數(shù)，即排列方法2#include using namespace std;int n,m, a10;void DFS(int k) if (k=n) for (int i=0; in; i+) coutai

4、 ; coutendl; else for (int i=k; imn; for (int i=0; im; i+) ai=i+1; DFS(0); return 0; 輸出m個數(shù)中取n個數(shù)的所有組合。例如m=5，n=3的所有組合為：1 2 31 2 41 2 5 1 3 41 3 51 4 5 2 3 42 3 52 4 5 3 4 5例3：組合問題#includeusing namespace std;int m,n,a10; /存放每個數(shù)int yes(int k)for (int i=1; in ) for (int i=1; i=n;i+)printf(%5d,ai);printf(

5、n); elsefor (int i=ak-1+1; i=m-n+k; i+)ak=i;if ( yes(k) ) comb(k+1); void DFS(int k) /處理第k步 for (int i=1; i=m; i+) /第k步中有m種可能 處理第k步 if (k=n) /已經(jīng)處理完n步，到達目的狀態(tài) 輸出結(jié)果； return； DFS(k+1)；/進入第k+1步 深度優(yōu)先(DFS)模板2：輸出1-m個數(shù)中取n個數(shù)的所有多重排列。例如n=2，m=3的所有多重排列為：1 11 21 32 12 22 33 13 23 3例1：多重排列問題/從1到m中取n個數(shù)，允許重復(fù)取數(shù)#includ

6、e using namespace std;int n,m, a10;void DFS(int k) for (int i=1; i=m; i+) ak=i; if (k=n) for (int i=0; in; i+) coutai ; coutmn; DFS(0); return 0; 輸出1-m個數(shù)中取n個數(shù)的所有排列。例如m=3 ，n=2的所有排列為：1 21 32 12 33 13 2例2：排列問題/從1到m中取n個數(shù)，不允許重復(fù)取數(shù)#include using namespace std;int n,m, a10; bool bz10;void DFS(int k) for (in

7、t i=1; i=m; i+) if ( !bzi ) ak=i; if (k=n) for (int i=0; in; i+) coutai ; coutmn; for (int i=0; im; i+) ai=i+1; DFS(0); return 0; /從1到m中取n個數(shù)，不允許重復(fù)取數(shù)#include using namespace std;int n,m, a10;void DFS(int k) for (int i=k; im; i+) if (k=n) for (int i=0; in; i+) coutai ; coutmn; DFS(0); return 0; 輸出m個數(shù)中取n個數(shù)的所有組合。例如m=5，n=3的所有組合為：1 2 31 2 41 2 5 1 3 41 3 51 4 5 2 3 42 3 52 4 5 3 4 5例3：組合問題#includeusing namespace std;int m,n,a10; /存放每個數(shù)int yes(int k)for (int i=1; ik; i+) if ( ai=ai+1 ) return 0;return 1; int main( ) void comb(int) ; scanf(%d%d,&m,&n);comb(1); /從第1個數(shù)開始 /組合問題的DF