当前位置: 首页 > news >正文

递推(C语言)

文章目录

  • 1.斐波那契数列
  • 2.太波那契数列
  • 3.二维递推问题
  • 4.实战
    • 4.1 力扣509 斐波那契数
    • 4.2 力扣70 爬楼梯
    • 4.3 力扣119 杨辉三角||

递推最通俗的理解就是数列,递推和数列的关系就好比 算法 和 数据结构 的关系,数列有点
像数据结构中的线性表(可以是顺序表,也可以是链表,一般情况下是顺序表),而递推就是一
个循环或者迭代的枚举过程。
递推本质上是数学问题,所以有同学问算法是不是需要数学非常好,也并不是,你会发现
这些数学只不过是初中高中我们学烂的东西,高考都经历了,这些东西又何足为惧!?

1.斐波那契数列

斐波那契数(通常用F(n)表示)形成的序列称为 斐波那契数列 。该数列由0和1开始,后面
的每一项数字都是前面两项数字的和。也就是:

F(0)=0,F(1)=1
F(n)=F(n -1)+ F(n- 2),其中n>1,给定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
且在 n>2的条件下 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(1<n<40)的只由’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;  
}
http://www.lryc.cn/news/398264.html

相关文章:

  • 安卓微信8.0之后如何利用缓存找回的三天之前不可见的朋友圈图片
  • ES6 Class(类) 总结(九)
  • 使用 Vue.js 和 Element Plus 实现自动完成搜索功能
  • SpringBoot自定义starter
  • 深入探索大语言模型
  • querylist多线程采集curlMulti时,报错Curl error(60)
  • Python数据分析~~美食排行榜
  • Linux下解压.tar.gz文件
  • 【电商选品干货】差异化卖点要这样打造,80%商家却做不到
  • LabVIEW比例压力控制阀自动测试系统
  • 运营商认证API在Java、Python、PHP中的使用教程
  • 用虚拟机,可以在x86的电脑上虚拟出arm的电脑吗
  • 富格林:可信观念摆脱暗箱陷阱
  • WEB前端01-HTML5基础(01)
  • JUC-常见方法与线程的状态
  • 如果你酿的酒是黄色,说明肯定是 “糊锅”了。
  • 国漫推荐07
  • 力扣刷题35.搜索查找位置
  • setContentView 流程
  • 基于STM32设计的智能手环(ESP8266+华为云IOT)178
  • EE trade:实物黄金投资的好处和坏处
  • Flutter RSA公钥转PEM
  • 下载站怎么防护DDOS攻击
  • docker拉取镜像-配置阿里云镜像加速
  • ai写作软件哪个好?亲测好用的5款工具分享
  • Blender 中导出模型fbx
  • 景联文科技以高质量多模态数据集赋能AI大模型,精准匹配提升模型性能
  • 【ROS2】中级:tf2-编写监听器(Python)
  • 用QFramework重构飞机大战(Siki Andy的)(下02)(06-0? 游戏界面及之后的所有面板)
  • Apifox报错404:网络错误,请检查网络,或者稍后再试的解决办法