算法递推

基本概念

直接或者间接调用自身的算法称为递归算法

  一般数据 n<&＃61;30用递归

步骤

优缺点

  优点&＃xff1a;结构清晰&＃xff0c;可读性强&＃xff0c;而且容易用数学归纳法来证明算法的正确性。因此它为设计算法、调试程序带来很大方便。
  缺点&＃xff1a;运行效率较低&＃xff0c;无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。

典型例题

1. 求 n 的阶乘
2. 求 斐波那契数列
3. 求 二叉树相关内容 ⭐
4. 汉诺塔问题
5. 排列 问题

ACWing 练习题

717. 简单斐波那契

#include
#include
#include
#include using namespace std;int n;
int a,b&＃61;1,c;int main()
{scanf("%d",&n);while(n--){printf("%d ",a);c&＃61;a&＃43;b;a&＃61;b,b&＃61;c;
}return 0;
}


92. 递归实现指数型枚举

#include
#include
#include using namespace std;const int N &＃61; 16;int n;
int status[N];//0 表示未使用 1表示选中 2表示未选中void dfs(int u)
{if(u > n)//判断边界{for (int i &＃61; 1; i <&＃61; n; i &＃43;&＃43; ){if(status[i]&＃61;&＃61;1) cout<<i<<" ";}puts("");return ;//一定要结束}status[u]&＃61;1;dfs(u&＃43;1);status[u]&＃61;0;status[u]&＃61;2;dfs(u&＃43;1);status[u]&＃61;0;
}int main()
{cin>>n;dfs(1);return 0;
}


94. 递归实现排列型枚举

#include
#include
#include using namespace std;const int N &＃61; 10;int n;
int sta[N];//表示位置 0 未使用 1 ~ n 放了数
bool used[N];//默认是0 0 是未使用 1 是已使用void dfs(int u)
{if (u > n){for(int i &＃61; 1; i <&＃61; n;i&＃43;&＃43;) printf("%d ",sta[i]);puts("");return;}for (int i &＃61; 1; i <&＃61; n; i &＃43;&＃43; )//遍历枚举分支 因为有多个分支{if(!used[i]){used[i]&＃61;true;sta[u]&＃61;i;//把该数放入dfs(u&＃43;1);used[i]&＃61;false;//恢复现场sta[u]&＃61;0;}}
}int main()
{cin>>n;dfs(1);return 0;
}

93. 递归实现组合型枚举

#include
#include
#include using namespace std;const int N &＃61; 30;int n,m;
int sta[N];void dfs(int u,int start)
{if(u&＃43;n-start <m) return;//剪枝if(u&＃61;&＃61;m&＃43;1) //u 从1开始 到 m&＃43;1 刚好是 m 个数{for (int i &＃61; 1; i <&＃61; m; i &＃43;&＃43; ) printf("%d ",sta[i]);puts("");return;}for (int i &＃61; start; i <&＃61; n; i &＃43;&＃43; ){sta[u]&＃61;i;dfs(u&＃43;1,i&＃43;1);sta[u]&＃61;0;//恢复现场}
}int main()
{cin>>n>>m;dfs(1,1);return 0 ;
}


1209. 带分数(难)⭐⭐⭐
暴力可以做
优化一下 dfs嵌到也可以做 但是费时

• 思路
  看成三个数&＃xff0c;根据公式能推出 cn&＃61;ca&＃43;b&＃xff0c;因此只需求出c和a就能得出b 缩小了复杂度
  因此先 枚举a&＃xff0c;然后枚举c&＃xff0c;最后判断b是否成立

#include using namespace std;const int N &＃61; 10;int n, ans;
bool st[N]; //记录是否使用
bool backup[N]; //备份数组bool check(int a, int c) //求 b 的值&＃xff0c;并且判断没有重复 而且和符合要求
{long long b &＃61; n * (long long)c - a * c;if (!a || !b || !c) //都不为0return false;memcpy(backup, st, sizeof st); //复制数组while (b){int x &＃61; b % 10; //取个位数b /&＃61; 10; //缩小if (!x || backup[x]) //判断 x 是否为0 或是 x 是否被用过return false;backup[x] &＃61; true;}for (int i &＃61; 1; i <&＃61; 9; i&＃43;&＃43;) //看b 有没有重复的if (!backup[i])return false;return true;
}void dfs_c(int u, int a, int c)
{if (u > 9) //如果十个数都用了return;if (check(a, c)) //看是否符合要求ans&＃43;&＃43;;for (int i &＃61; 1; i <&＃61; 9; i&＃43;&＃43;){if (!st[i]){st[i] &＃61; true;dfs_c(u &＃43; 1, a, c * 10 &＃43; i);st[i] &＃61; false; //恢复现场}}
}void dfs_a(int u, int a)
{if (a >&＃61; n) //这不是边界return;if (a)dfs_c(u, a, 0);for (int i &＃61; 1; i <&＃61; 9; i&＃43;&＃43;){if (!st[i]){st[i] &＃61; true;dfs_a(u &＃43; 1, a * 10 &＃43; i);st[i] &＃61; false;}}
}int main()
{cin >> n;dfs_a(0, 0); //第一个表示当前位置 第二个是a的值cout << ans << endl;return 0;
}