☰

企业官网建设流程全解析

首页 / 建站日记 / 企业官网建设流程全解析
C++递推算法的具体使用
2026/9/10 9:02:20 网站建设 项目流程

递推算法通过已知的初始条件和递推关系，逐步推导出后续结果。与递归不同，递推通常使用循环结构实现，避免了函数调用的开销，效率更高。

本文将用C++语言，通过几个经典例题，详细讲解递推算法的思想和实现。

一、递推算法基本思想

递推算法的核心是递推关系式和初始条件。

递推关系式描述了当前状态如何由前一个或多个状态推导而来，而初始条件则是递推的起点。

在C++中实现递推，通常遵循以下步骤：

  1. 定义状态数组：使用数组存储中间结果
  2. 设置初始条件：根据问题初始化数组的前几项
  3. 建立递推关系：通过循环按照递推公式计算后续项
  4. 输出结果：返回或输出目标位置的值

递推与递归的主要区别在于：递推是自底向上的迭代过程，而递归是自顶向下的函数调用过程。递推通常更高效，适合处理线性结构问题。

二、一维递推问题

1. 斐波那契数列

问题描述：斐波那契数列的第1项为1，第2项为1，从第3项开始，每一项都等于前两项之和。

递推关系：f[i] = f[i-1] + f[i-2]初始条件：f[1] = 1, f[2] = 1

C++代码实现：

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

#include <iostream>

usingnamespacestd;

intmain() {

intn;

cin >> n;

// 定义数组存储斐波那契数，假设n不超过45（保证在int范围内）

intf[46];// 第45项约为1.13e9，仍在int范围内

// 初始化初始条件

f[1] = 1;

f[2] = 1;

// 递推计算

for(inti = 3; i <= n; i++) {

f[i] = f[i-1] + f[i-2];

}

cout << f[n] << endl;

return0;

}

代码解析：

  • 数组f存储已计算的结果，避免重复计算
  • 循环从3开始，依次计算每一项
  • 当n≤45时，结果在int范围内（约21亿内）

2. 爬楼梯问题

问题描述：有n阶楼梯，每次可以爬1阶或2阶，问有多少种不同的爬法。

递推分析：设a[i]表示爬到第i阶楼梯的方法数。由于每次只能爬1阶或2阶，所以到达第i阶只能从第i-1阶爬1阶，或从第i-2阶爬2阶。

递推关系：a[i] = a[i-1] + a[i-2]初始条件：a[1] = 1（爬1阶只有1种方法），a[2] = 2（爬2阶有2种方法）

C++代码实现：

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

#include <iostream>

usingnamespacestd;

intmain() {

intn;

cin >> n;

inta[46];// 假设n不超过45

a[1] = 1;

a[2] = 2;

for(inti = 3; i <= n; i++) {

a[i] = a[i-1] + a[i-2];

}

cout << a[n] << endl;

return0;

}

代码解析：

  • 这个问题实质上是斐波那契数列的变体，只是初始条件不同

三、二维递推问题

1. 无障碍网格路径计数

问题描述：在一个m×n的网格中，从左上角(1,1)出发，每次只能向右或向下移动一步，要到达右下角(m,n)，问有多少条不同的路径。

递推分析：设b[i][j]表示从起点到达坐标(i,j)的路径数。由于只能向右或向下移动，要到达(i,j)，只能从上方(i-1,j)或左方(i,j-1)过来。

递推关系：b[i][j] = b[i-1][j] + b[i][j-1]边界条件：第一行和第一列的所有位置都只有1条路径

C++代码实现：

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

#include <iostream>

usingnamespacestd;

intmain() {

intm, n;

cin >> m >> n;

// 使用二维数组，假设m和n不超过20

intb[21] = {0};

// 初始化第一行和第一列

b[1][1] = 1;

// 递推计算

for(inti = 1; i <= m; i++) {

for(intj = 1; j <= n; j++) {

if(i == 1 && j == 1)continue;// (1,1)点是初始化条件不用递推

b[i][j] = b[i-1][j] + b[i][j-1];

}

}

cout << b[m][n] << endl;

return0;

}

代码解析：

  • 数组b[i][j]表示到达(i,j)的路径数
  • 初始化第一行和第一列为1，因为沿着边线只有一条路径
  • 双重循环从(2,2)开始递推计算

2. 有障碍网格路径计数

路径计数2（洛谷P1176）

问题描述：一个 N×N 的网格，你一开始在 (1,1)，即左上角。每次只能移动到下方相邻的格子或者右方相邻的格子，问到达 (N,N)，即右下角有多少种方法。

但是这个问题太简单了，所以现在有 M 个格子上有障碍，即不能走到这 M 个格子上。

递推分析：递推关系与无障碍情况类似，但需要额外考虑障碍物：

  1. 如果(i,j)是障碍物，则b[i][j] = true
  2. 否则，a[i][j] =a[i-1][j] + a[i][j-1]

C++代码实现：

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

#include <iostream>

usingnamespacestd;

constintMOD = 100003;// 定义模数常量，避免魔法数字

inta[1001][1001] = {0};// 显式初始化为0

boolb[1001][1001] = {false};// 显式初始化为false

intmain() {

intn, m;

cin >> n >> m;

// 读入障碍物

for(inti = 1; i <= m; i++) {

intx, y;

cin >> x >> y;

b[x][y] =true;

}

// 初始化起点

a[1][1] = 1;

// 递推

for(inti = 1; i <= n; i++) {

for(intj = 1; j <= n; j++) {

// 跳过起点和障碍物

if(i == 1 && j == 1)continue;

if(b[i][j])continue;

a[i][j] = (a[i-1][j] + a[i][j-1]) % MOD;

}

}

cout << a[n][n] << endl;

return0;

}

四、马走日（过河卒）问题

问题描述：棋盘上有一个卒需要从A点(1,1)走到B点(n,m)，卒只能向右或向下移动。棋盘上有一个马，马走"日"字，马所在位置及其控制点（马能走到的8个位置）卒不能通过。

递推分析：这是网格路径计数问题的变体，增加了障碍点（马的控制点）。设b[i][j]表示卒从起点到达(i,j)的路径数，stop[i][j]表示(i,j)是否为障碍点。

递推关系与有障碍网格类似：

  1. 如果(i,j)是障碍点，则b[i][j] = 0
  2. 否则，b[i][j] = b[i-1][j] + b[i][j-1]

C++代码实现：

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

#include<bits/stdc++.h>

usingnamespacestd;

// 定义 long long 类型别名，用于存储可能的大数结果

#define ll long long

// 马的控制点方向数组：包括马本身及其8个走日位置，共9个方向

// dx和dy分别对应行和列的变化量，其中(0,0)表示马自身位置

intdx[] = {-2, -2, -1, -1, 0, 1, 1, 2, 2};

intdy[] = {-1, 1, -2, 2, 0, -2, 2, -1, 1};

// 标记数组：s[i][j]=true表示(i,j)是障碍点（马的控制点）

bools[40];

// 动态规划数组：ans[i][j]表示从起点到达(i,j)的路径数

ll ans[40];

// 变量定义：bx,by为目标点坐标，mx,my为马的位置坐标

intbx, by, mx, my;

intmain() {

// 读入目标点坐标和马的位置坐标（原始坐标从(0,0)开始）

cin >> bx >> by >> mx >> my;

// 所有坐标加2：偏移操作，防止后续计算马的控制点时数组越界

// 这样棋盘有效坐标从(2,2)开始，对应原坐标(0,0)

bx+=2, by+=2, mx+=2, my+=2;

// 标记马的控制点为障碍（包括马自身）

// dx和dy数组长度为9，索引0~8

for(inti = 0; i < 9; i++) {

s[mx+dx[i]][my+dy[i]] =true;

}

// 递推初始化：起点(2,2)的路径数为1

ans[2][2] = 1;

// 递推：遍历从起点到目标点的所有位置

for(inti = 2; i <= bx; i++) {

for(intj = 2; j <= by; j++) {

// 如果当前位置是障碍点或是起点，则跳过（起点已初始化）

if(s[i][j] || i==2&&j==2)continue;

// 状态转移方程：到达(i,j)的路径数等于从左边(i,j-1)和从上方(i-1,j)的路径数之和

// 由于卒只能向右或向下移动，因此只需考虑这两个方向

ans[i][j] = ans[i][j-1] + ans[i-1][j];

}

}

// 输出结果：到达目标点(bx,by)的路径数

cout << ans[bx][by];

return0;

}

五、递推算法的核心要点

1. 确定递推状态

递推状态是问题的关键，通常用一个或多个变量表示问题的某个状态。例如：

  • 爬楼梯问题：a[i]表示到达第i阶的方法数
  • 网格路径问题：b[i][j]表示到达(i,j)的路径数

状态的定义需要能够完整描述问题的当前情况，并且能够通过递推关系转移到其他状态。

2. 建立递推关系

递推关系描述了状态之间的转移方式，通常基于问题的限制条件。

例如：

  • 爬楼梯：一次只能爬1或2阶 →a[i] = a[i-1] + a[i-2]
  • 网格路径：只能向右或向下 →b[i][j] = b[i-1][j] + b[i][j-1]

3. 设置初始条件

初始条件是递推的起点，必须明确给出。例如：

  • 爬楼梯：a[1] = 1, a[2] = 2
  • 网格路径：第一行和第一列都为1（无障碍时）
标签： 网站建设 企业官网 项目流程 UI设计 前端开发

热门文章

文章分类

标签云

网站建设 响应式设计 用户体验 SEO优化 前端开发 小程序 电商平台 性能优化

相关文章

您可能感兴趣的其他内容

Java继承从入门到实战：extends、super、方法重写与多态详解
2026/9/10 9:02:10 网站建设

Java继承从入门到实战：extends、super、方法重写与多态详解

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …...

阅读更多 →
Flipper Zero BadUSB 渗透测试实战：从跑通第一个 Payload 到排错
2026/9/10 9:00:21 网站建设

Flipper Zero BadUSB 渗透测试实战：从跑通第一个 Payload 到排错

Flipper Zero BadUSB 渗透测试实战&#xff1a;从跑通第一个 Payload 到排错 【免费下载链接】Flipper Playground (and dump) of stuff I make or modify for the Flipper Zero 项目地址: https://gitcode.com/GitHub_Trending/fl/Flipper 你刚拿到一台用于练习的二手 …...

阅读更多 →
华为Mate 80关机也能定位？一文读懂手机防丢新机制
2026/9/10 8:59:10 网站建设

华为Mate 80关机也能定位？一文读懂手机防丢新机制

手机丢了还被关机&#xff1f;华为Mate 80系列关机状态下照样能响铃定位&#xff0c;轻松找回&#xff01; 先说结论&#xff1a;手机被捡走、对方长按电源键关机、屏幕一黑就彻底失联——这种过去让人绝望的丢机剧本&#xff0c;从华为Mate 80系列开始真的可以改了。华为在Ma…...

阅读更多 →

需要专业的网站建设服务？

联系我们获取免费的网站建设咨询和方案报价，让我们帮助您实现业务目标

立即咨询