递归解决遍历问题
2023-09-11 14:15:01 时间
递归解决遍历问题
觉得有用的话,欢迎一起讨论相互学习~
参考文献
《算法竞赛宝典》--张新华
算法流程
//递归解决枚举问题
//
// 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
相关文章
- linux文件夹操作及递归遍历文件夹
- 数据结构之中序遍历转兴许遍历(JAVA实现)(二)
- enumerate 遍历numpy数组
- 【Asp.Net】数组的遍历及数组元素个数统计(示例源码)
- Morris遍历判断二叉树是否为搜索二叉树
- 图的宽度优先遍历:BFS遍历
- 二叉树,二叉树的归先序遍历,中序遍历,后序遍历,递归和非递归实现
- rails应用遍历Controllers目录并取出所有的Controller和action
- Xmemcached 1.2.2发布——支持遍历所有key
- 五二不休息,今天也学习,从JS执行栈角度图解递归以及二叉树的前、中、后遍历的底层差异
- 遍历opencv中的mat像素的几种方法和概念
- TypeScript ES6-Promise 递归遍历文件夹中的文件
- 【C++】二叉树之力扣经典题目1——详解二叉树的递归遍历,二叉树的层次遍历
- 递归遍历全排列个人见解
- 二叉树遍历(前序、中序、后序)递归法
- CentOS下递归遍历文件夹下所有文件,查找指定字符
- 使用Struts2的iterator标签遍历复杂Map种类
- 史上最简明易懂非递归遍历二叉树算法
- lqb 基础练习 查找整数 (遍历)
- python第三十一课--递归(2.遍历某个路径下面的所有内容)
- javaScript遍历对象、数组总结(转载)
- Python 数组的遍历
- Map集合遍历的四种方式理解和简单使用