每日一题Day6(递归专栏---FBI数)

个人主页:小则又沐风

个人专栏:<数据结构>

<竞赛专栏>

<C语言>

今天我们将要学习地算法是递归.

提起来递归大家一定不会陌生,因为我们地二叉树 快速排序,归并排序.....都使用了递归.那么我们要怎么借助递归来解决问题呢?

我们来看使用递归地场景.

以我们地dfs为例.我们想要前序遍历这棵二叉树,即左子树---根---右子树.

我们会发现我们在解决这个问题时我们先访问根的左子树在访问左子树地左子树,

这样地问题是一个重复地问题,当问题可以分为一个又一个子问题地时候,并且我们在重复地解决一个问题地时候,我们就可以思考我们是否可以使用递归来解决这个问题.

来看dfs的逻辑,我们设计dfs函数后我们想要使用递归来解决,既然如此那我们就认定这个dfs函数一定能够解决我们的问题,所以我们只需要写遍历的逻辑就可以了.

所以我们写出了dfs(root[left]); dfs(root[right]);

这样我们的逻辑就基本完成了,下面是我们回归的条件,什么时候就不能继续递归了,那就是遍历到了叶子节点,所以我们写上了 if root=NULL return;

这就是我们用递归解决问题的模板,先观察题目是否有重复的子问题,认定我们的函数能解决这个问题,写递归逻辑,写回归条件.

下面我们来实战:

题目:FBI 树

这道题是我特意找和二叉树遍历相似的题,我们来读题,题目将会给出我们一个字符串让我们根据如果只有1则为I串,如果只有0则为B串,最后其他的为F串.让我们以这个逻辑让我们构造一个FBI树,然后输出他的后序遍历.我们很容易的看到这个问题能够分为一个又一个的子问题,所以我们使用递归来解决他.

算法原理

我们先判断这个串是什么串.

怎么判断呢?我们可以拿到字符串的左边和右边,我们求出这个字符串的个数,然后我们求出这个字符串的总和,如果等于我们的字符串长度那么就表示这串字符串全部是1,如果字符串的总和是0那么就全部是0,最后剩下的就是F串.

下面我们直接来解决问题.

代码实现:

#include<iostream> using namespace std; const int N=1050; int a[N]; int n; int f[N]; void dfs(int left,int right) { if(left>right) { return; } char ret; int an=f[right]-f[left-1]; if(an==right-left+1) { ret='I'; }else if(an==0) { ret='B'; }else { ret='F'; } if(left==right) { cout<<ret; return; } int mid=(left+right)/2; dfs(left,mid); dfs(mid+1,right); cout<<ret; } int main() { cin>>n; for(int i=1;i<=(1<<n);i++) { char ch; cin>>ch; a[i]=ch-'0'; f[i]=f[i-1]+a[i]; } dfs(1,1<<n); return 0; }

以上就就是今天的所有内容.