//回溯法实现排列 //应用回溯法产生排列A(m,n)。设置一维数组a,a[i]在1—n中取值,出现数字相同时返回。 //当i<m时,还未取m个数,i增1后a[i]=1继续;当i=m时,输出一个A(n,m)的排列,并设置变量s统计A(n,m)排列的个数。 //当a[i]<n时,a[i]增1继续。当a[i]=n时,回溯或调整,知道i=0时结束。 //回溯实现A(n,m)代码如下: #include <iostream> using namespace std; const int N = 30; int main() { int n,m,a[N],i,j,t; long s = 0; cout << "intput n(n < 10):"<<endl; cin>>n; cout << "input m(m <= n):" << endl; cin>>m; i = 1; a[i] = 1; while (true) { t = 1; for(j = 1;j < i;j++) if(a[j] == a[i]){t = 0;break;} if(t && i == m) { s++; for(j = 1;j <= m;j++) cout << a[j]; cout << " "; if(s % 10 == 0) cout << endl; } if(t && i < m){i++;a[i] = 1;continue;} while(a[i] == n)i--; if(i > 0) a[i]++; else break; } cout << endl << s << endl; return 0; }