AKSZ-递归递推
2024-04-14 17:06:30
发布于：广东
8阅读
0回复
0点赞
递归
在程序设计领域，递归式函数或方法直接或间接调用自身的一种操作。
（必须有个终止条件）
递归函数的两大要素
- 递归边界
- 递归方程
递归的缺点
- 难理解
- 重复计算
- 爆栈
栈：一个先进后出的数据结构
#include<bits/stdc++.h>
using namespace std;
void f(int n){
if(!n)return;
f(n-1);
for(int i=0;i<n;++i){
cout<<n<<" ";
}
cout<<"\n";
}
int main(){
f(5);
return 0;
}
递归不要用局部数组（RE）;
最大公因数(gcd())——辗转相除法
#include<bits/stdc++.h>
using namespace std;
int m,n;
long long gcd(int m,int n){
if(n==0)return m;
return gcd(n,m%n);
}
int main(){
cin>>m>>n;
cout<<gcd(m,n);
return 0;
}
例题
例题1：【递归的应用(一)】斐波那契
题目描述
斐波那契数列 （Fibonaccisequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契 （LeonardoFibonacci） 以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……
输入 n，求斐波那契数列的第 n 项。
注意：请用递归完成
提示
数据范围：
n(0<n≤20)
样例说明：
根据斐波那契当前项为前两项之和1、1、2、3、5、8、13、21、34、……，我们得知第四项为3
输入格式
输入一个正整数n(0<n≤20)。
输出格式
输出斐波那契数列的第 n 项。
样例组输入#1
5
样例组输出#1
5
#include<bits/stdc++.h>
using namespace std;
int n;
int f(int n){
if(n==1||n==2){
return 1;
}
return f(n-1)+f(n-2);
}
int main(){
cin>>n;
cout<<f(n);
return 0;
}
memset()函数
格式：memset(数组名,填充数,sizeof(数组名));
填充数为0或1；
memset()应用——例题1：【递归的应用(一)】斐波那契
#include<bits/stdc++.h>
using namespace std;
const int maxn=1005;
long long dp[maxn];
long long f(int n){
if(n==1||n==2)return 1;
if(dp[n]!=-1)return dp[n];
return dp[n]=f(n-1)+f(n-2);
}
int main(){
memset(dp,-1,sizeof(dp));
cout<<f(50);
return 0;
}
递推算法
1.组合数学
| 原理名称 | 加法原理 | 乘法原理 |
|---|---|---|
| 电学链接 | 串联 | 并联 |
| 相关例题 | 密码：0-9和a-z;一位密码，共用多少种选择：10+26=36 | --- |
2.分阶段讨论问题
唯一分解定理
短除法 不断除以较小的素数
int a;
cin>>a;
//带有一定塞法的思想
for(int i=2;i<=a;++i){
while(a%i==0){
cout<<i<<" ";
a/=i;
}
}
^上述输出结果会按顺序列举所有质因数，并以空格隔开每个质因数。若输入180，则会输出2 2 3 3 5
有帮助，赞一个