参考文献 《算法竞赛宝典》--张新华
算法流程
//递归解决枚举问题
//
// Created by cloud on 2019/5/4.
//
//全排列算法-深搜字典序
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
int a[10000], Count, DNAsequences_length, DNABase_types;
void print() {
for (int k = 1; k < DNAsequences_length 1; k )
cout << a[k];
cout << "n";
Count ;
}
void dfs(int i) {
if (i > DNAsequences_length)//递归结束，打印结果,递归的深度即为DNAsequences_length
print();
else
for (int k = 1; k <= DNABase_types; k ) {
a[i] = k-1;//赋值 a[1]=0,
dfs(i 1);
//这个for循环一直很奇妙因为我不知道这个for循环什么时候才能停止下来
// cout<<k<<endl;
/* //1.发现DNA长度达到DNAsequences_length后才会输出k,认为是dfs函数达到条件后才退出
//2.在Test3length.txt中的结果显示
//k=1 a[1]=1
//dfs(2)
//k=1 a[2]=1
//dfs(3)
//k=1 a[3]=1
//dfs(4)
//调用print函数，依次输出a[1],a[2],a[3]
// 111--根据下一步输出是112推断程序发生了a[3]=2这种改变，即k=2,i=3
//此时程序退回到dfs(3),执行输出k=1,并将k 1
//因此a[3]=2,执行dfs(4)在执行print()函数
// 112
//程序又退回到dfs(3),执行输出k=2,并将k 1
//因此a[3]=3,执行dfs(4)在执行print()函数
// 113
//程序又退回到dfs(3),执行输出k=3,并将k 1,
//因此a[3]=4,执行dfs(4)在执行print()函数
//114
//程序又退回到dfs(3),执行输出k=4,并将k 1=5,已经不满足for循环的条件了
//则程序退回到dfs(2),k=1时，输出k,并将k 1=2
//a[2]=2
//程序进入dfs(3)，k=1,a[3]=1,程序进入dfs(4),输出121,退出dfs(4),进入dfs(3),输出k=1
//k=k 1,a[3]=2,程序进入dfs(4),输出122,退出dfs(4),进入dfs(3),输出k=2
//...*/
}
// i的值在函数调用内会不断的增加直到超越DNAsequences_length即最终终止此函数的条件是i=DNAsequences_length 1
}
int main() {
freopen("V0in.txt", "r", stdin); //输入重定向，输入数据将从V0in.txt文件中读取
freopen("V0out.txt", "w", stdout); //输出重定向，输出数据将保存在V0in.txt文件中
cin >> DNAsequences_length; // DNAsequences_length是指需要全排序使用的元素个数
cin >> DNABase_types;//表示生成序列的长度
dfs(1);
cout << Count << endl;
// Count是一个全局变量，用于统计一共生成的序列数
fclose(stdin);//关闭文件
fclose(stdout);//关闭文件
return 0;
}
结果
- V1in.txt
