程序设计培训之5：搜索算法一个从起始状态到达目标状态包含多步操作，而每一步操作又有几种可能，只有正确的操作才能达到目标（如八皇后问题），这样的问题可以看做是一个树。如果按照1-2-4-5-3-6-7的顺序，叫深度优先(DFS)如果按照1-2-3-4-5-6-7的顺序，叫广度优先(BFS)voidDFS(intk)//处理第k步{if(k==n)//已经处理到第n步，到达目的状态输出结果else//处理第k步for(inti=1;i<=m;i++)//第k步中有m种可能{处理第k步DFS(k+1)；//进入第k+1步}}输出1-m个数中取n个数的所有多重排列。例如n=2，m=3的所有多重排列为：111213212223313233//从1到m中取n个数，允许重复取数#include<iostream>usingnamespacestd;intn,m,a[10];voidDFS(intk){if(k==n){for(inti=0;i<n;i++)cout<<a[i]<<"";cout<<endl;}elsefor(inti=1;i<=m;i++){a[k]=i;DFS(k+1);}}intmain(){cin>>m>>n;DFS(0);return0;}输出1-m个数中取n个数的所有排列。例如n=2，m=3的所有排列为：121321233132//从1到m中取n个数，不允许重复取数#include<iostream>usingnamespacestd;intn,m,a[10];boolbz[10];voidDFS(intk){if(k==n){for(inti=0;i<n;i++)cout<<a[i]<<"";cout<<endl;}elsefor(inti=1;i<=m;i++)if(!bz[i]){a[k]=i;bz[i]=true;DFS(k+1);bz[i]=false;}}intmain(){cin>>m>>n;DFS(0);return0;}//从1到m中取n个数，不允许重复取数，即排列方法2#include<iostream>usingnamespacestd;intn,m,a[10];voidDFS(intk){if(k==n){for(inti=0;i<n;i++)cout<<a[i]<<"";cout<<endl;}elsefor(inti=k;i<m;i++){intt=a[k];a[k]=a[i];a[i]=t;DFS(k+1);t=a[k];a[k]=a[i];a[i]=t;}}intmain(){cin>>m>>n;for(inti=0;i<m;i++)a[i]=i+1;DFS(0);return0;}输出m个数中取n个数的所有组合。例如m=5，n=3的所有组合为：123124125134135145234235245345#include<iostream>usingnamespacestd;intm,n,a[10];//存放每个数intyes(intk){for(inti=1;i<k;i++)if(a[i]==a[i+1])return0;return1;}intmain(){voidcomb(int);scanf("%d%d",&m,&n);comb(1);//从第1个数开始}//组合问题的DFS算法voidcomb(intk){if(k>n){for(inti=1;i<=n;i++)printf("%5d",a[i]);printf("\n");}elsefor(inti=a[k-1]+1;i<=m-n+k;i++){a[k]=i;if(yes(k))comb(k+1);}}voidDFS(intk)//处理第k步{for(inti=1;i<=m;i++)//第k步中有m种可能{处理第k步if(k==n)//已经处理完n步，到达目的状态{输出结果；return；}DFS(k+1)；//进入第k+1步}}输出1-m个数中取n个数的所有多重排列。例如n=2，m=3的所有多重排列为：111213212223313233//从1到m中取n个数，允许重复取数#include<iostream>usingnamespacestd;intn,m,a[10];voidDFS(intk){for(inti=1;i<=m;i++){a[k]=i;if(k==n){for(inti=