做网站需要服务器么,温州微信网站开发,太原cms建站,专业seo服务商文章目录 1.斐波那契数列2.太波那契数列3.二维递推问题4.实战4.1 力扣509 斐波那契数4.2 力扣70 爬楼梯4.3 力扣119 杨辉三角|| 递推最通俗的理解就是数列#xff0c;递推和数列的关系就好比 算法 和 数据结构 的关系#xff0c;数列有点 像数据结构中的线性表(可以是顺序表递推和数列的关系就好比 算法 和 数据结构 的关系数列有点 像数据结构中的线性表(可以是顺序表也可以是链表一般情况下是顺序表)而递推就是一 个循环或者迭代的枚举过程。 递推本质上是数学问题所以有同学问算法是不是需要数学非常好也并不是你会发现 这些数学只不过是初中高中我们学烂的东西高考都经历了这些东西又何足为惧!? 1.斐波那契数列
斐波那契数(通常用F(n)表示)形成的序列称为 斐波那契数列 。该数列由0和1开始后面 的每一项数字都是前面两项数字的和。也就是: F(0)0F(1)1 F(n)F(n -1) F(n- 2)其中n1给定n(0 ≤n≤ 30)请计算 F(n) 拿到这个题目我们首先来看题目范围最多不超过 30那是因为斐波那契数的增长速度很 快是指数级别的。所以如果n 很大就会超过 c语言 中32位整型的范围。这是一个最基础的递 推题递推公式都已经告诉你了我们要做的就是利用一个循环来实现这个递推。 我们只需要用一个 F[31]数组初始化好 F[0]和 F[1]然后按照给定的公式循环计算就可以。
int febonacci(int n) { int F[30] {0,1}; for (int i 2; i 30; i) { F[i] F[i - 1] F[i - 2]; } return F[29]
}2.太波那契数列
泰波那契序列Tn定义如下: T(0) 0, T(1) 1,T(2)1 且在 n2的条件下 T(n)T(n-1)T(n-2)T(n-3)给你整数n请返回第n个泰波那契 数T(n)的值。 如果已经理解斐波那契数列那么这个问题也不难只不过初始化的时候需要初始化前三个数 并且在循环迭代计算的时候当前数的值需要前三个数的值累加和。像这样
int tribonacci(int n) { int F[30] {0,1,1}; for (int i 3; i 30; i) { F[i] F[i - 1] F[i - 2] F[i - 3]; } return F[29];
}3.二维递推问题
像斐波那契数列这种问题是一个一维的数组来解决的有些时候一维解决不了的时候我 们就需要升高一个维度来看问题了。 长度为n(1n40)的只由’A’、C’、M’三种字符组成的字符串(可以只有其中一种或两种字 但绝对不能有其他字符)且禁止出现 M 相邻的情况问这样的串有多少种? 考虑长度为n且以’A’ 结尾的串有f[n][0]种、以’C’ 结尾的串有f[n][1]种、以’’ 结尾的串有 f[n][2]种
4.实战
4.1 力扣509 斐波那契数
斐波那契数 通常用 F(n) 表示形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始后面的每一项数字都是前面两项数字的和。
int fib(int n){if(n 0){return 0;}else if (n 1){return 1;}return fib(n - 1) fib(n - 2);
}4.2 力扣70 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢
int climbStairs(int n) { int f[46]; f[0] 1; f[1] 1; for(int i 2; i n; i){ f[i] f[i - 1] f[i - 2]; } return f[n];
}4.3 力扣119 杨辉三角||
给定一个非负索引 rowIndex返回「杨辉三角」的第 rowIndex 行。
int* getRow(int rowIndex, int* returnSize) { int f[34][34]; for(int i 0; i rowIndex; i){ for(int j 0; j i; j){ if(j 0 || j i){ f[i][j] 1; } else { f[i][j] f[i - 1][j] f[i - 1][j - 1]; } } } int* ret (int *)malloc (sizeof(int) * (rowIndex 1)); for(int j 0; j rowIndex; j){ ret[j] f[rowIndex][j]; } *returnSize rowIndex 1; return ret;
}
