废话不多说,我们先看一下位置排序的算法:
#include <iostream> using namespace std; int n = 0; int m = 2; int l = 0; int a[100]; void solve(int l); int main() { cout<<"请输入位数 n "<<endl; cin>>n; solve(l); return 0; } void solve(int l) { if(l>=n) { for(int i = 0 ; i<n; i++) { cout<<a[i]; } cout << endl; return; } for(int i = 0 ;i < m;i++) { a[l] = i; solve(l+1); } }
运行结果如下:
请输入位数 n
4
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
我们可以把这个算法应用到这样一个例子中:
递归求一个集合的所有子集:
代码如下:
#include <iostream> #include<vector> #include <stdio.h> using namespace std; void solve(int l); int n, m; int mat[100]; vector<string> collection; int main() { string firstElement; string element; int mcount = 1; cout << "Please input the element , end by #end" << endl; cin >> firstElement; while(firstElement != "#end") { element = firstElement; cout << "The element "<<mcount<< " you input is "+ element<< endl; collection.push_back(element); //cout << collection[mcount-1]; cout << "Please input the next element , end by #end" << endl; cin >> firstElement; } n = collection.size(); m = 2; solve(0); return 0; } void solve(int l)//l=0 { int i; if(l >= n)//n=4 { printf("{"); for(i=0; i<n; ++i) { if(mat[i] == 1) { cout<< collection[i] << " "; } } printf("}\n"); return; } for(i=0; i<m; ++i)//m=2 { mat[l] = i; solve(l+1); } }
运行结果如下:
Please input the element , end by #end
a
The element 1 you input is a
Please input the next element , end by #end
b
The element 1 you input is b
Please input the next element , end by #end
c
The element 1 you input is c
Please input the next element , end by #end
#end
{}
{c }
{b }
{b c }
{a }
{a c }
{a b }
{a b c }