网站开发学什么语音,安装wordpress中文包,html导入wordpress,百度seo原理数据结构----结构–线性结构–递归
1.递归的概念
递归#xff1a;将一个问题拆解成解决方案完全相同的子问题#xff0c;并且有一个明确的终点
看如下递归代码理解一下递归
void fun(int n){if(n4){printf(%d,n);return;}fun(n1);printf(%d,n);
…数据结构----结构–线性结构–递归
1.递归的概念
递归将一个问题拆解成解决方案完全相同的子问题并且有一个明确的终点
看如下递归代码理解一下递归
void fun(int n){if(n4){printf(%d,n);return;}fun(n1);printf(%d,n);
}int main(){int a1;fun(a);//输出的结果为 4 3 2 1
}二.斐波那契数列
1.用递归实现斐波那契数列
int Fib(int n) {if(n0) return;if (n1||n2) {return 1;}return Fib(n - 1) Fib(n - 2);}优化
保存已经算过的递归结果
时间复杂度O(n)
空间复杂度O(递归的深度)
2.用循环实现斐波那契数列
int Fib(int n) {if (n 0) return;if (n 1 || n 2) {return 1;}int a 1;//n-2int b 1;//n-1int c 0;//nfor (int i 3; i n; i) {c a b;a b;b c;}return c;
}时间复杂度O(n)
空间复杂度O(1)
3.青蛙跳台阶问题网址https://leetcode.cn/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/
题目
一只青蛙一次可以跳上1级台阶也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e971000000007如计算初始结果为1000000008请返回 1。
分析
这道题就是斐波那契数列的变形
每一次都可以选择跳1级还是2级
拿三阶台阶来说 它的总方法就是跳二阶台阶的方法加上跳一阶台阶方法 F(3)F(2)F(1)
拿四阶台阶来说 它的总方法就是跳三阶台阶的方法加上跳二阶台阶方法 F(4)F(3)F(2)
依次类推
F(n)F(n-1)F(n-2)
这里注意F(1)1 ,F(2)2
代码为
//这里的代码是c语言下的
int numWays(int n) {if (n 1 || n 0) {return 1 % (1000000007);}if (n 2) {return 2 % (1000000007);}int a 1;//n-2 台阶的方法int b 2;//n-1 台阶的方法int c0;//n 台阶的方法for (int i 3; i n; i) {c (a b)% 1000000007;a b% 1000000007;b c% 1000000007;}return c % 1000000007;
}
