复兴无基础第二十九课 递推（一）
2025-11-23 15:29:48
发布于：上海
0阅读
0回复
0点赞
T1【递推】走楼梯
#include <iostream>
using namespace std;
const int N = 60;
long long f[N]; //f[i]：上到第 i 级台阶的方案数）
int main()
{
//1、定义变量 n 和 f数组，f数组用来存储方案数
int n;
cin >> n;
//2、初始条件，第一级的方案数和第二级的方案数
f[1] = 1; //上到第 1 级台阶的方案数为 1
f[2] = 2; //上到第 2 级台阶的方案数为 2
//3、递推关系，上到第i级台阶的方案数 = 上到第i-1级台阶的方案数 + 上到第i-2级台阶的方案数
for(int i = 3; i <= n; i++)
f[i] = f[i-1] + f[i-2];
//4、输出答案，上到第n级台阶的方案数
cout << f[n];
return 0;
}
T2【递推】蜜蜂路线
#include<iostream>
using namespace std;
const int N = 60;
long long a[N];
int main()
{
//1、定义变量n和a数组，a[i]表示爬i个格子的方案数。
int n;
cin >> n;
//2、初始化，爬一个格子和两个格子的方案数能直接求出
a[1] = 1;
a[2] = 2;
//3、递推，求爬i个格子的方案数，爬i个格子的方案数 = 爬i-1个格子的方案数 + 爬i-2个格子的方案数
for (int i = 3; i <= 50; i++)
a[i] = a[i - 1] + a[i - 2];
//4、处理n组样例
while (n--)
{
//4.1、定义变量x和y，示从x到y
int x, y;
cin >> x >> y;
//4.2、从x到y，一共爬的格子数为y-x，直接输出答案
cout << a[y - x] << endl; //从x格到y格，爬上y-x个格子的方案数
}
return 0;
}
T3【递推】走楼梯plus
#include <iostream>
using namespace std;
const int N = 60;
long long f[N]; //用来存储方案数（f[i]：上到第 i 级台阶的方案数）
int main()
{
//1、定义变量 n 和 f数组，f数组用来存储方案数
int n;
cin >> n;
//2、初始条件，第一级的方案数、第二级的方案数和第三级的方案数
f[1] = 1; // 上到第 1 级台阶的方案数为 1
f[2] = 2; // 上到第 2 级台阶的方案数为 2
f[3] = 4; // 上到第 3 级台阶的方案数为 4
//3、递推关系，上到第i级台阶的方案数 = 上到第i-1级台阶的方案数 + 上到第i-2级台阶的方案数 + 上到第i-3级台阶的方案数
for(int i = 4; i <= n; i++)
f[i] = f[i - 1] + f[i - 2] + f[i - 3];
//4、输出答案，上到第n级台阶的方案数
cout << f[n];
return 0;
}
T4骨牌铺法
#include <iostream>
using namespace std;
const int N = 60;
long long x[N]; // 用来存储方案数（x[i]：2 ×i的方格的铺法总数）
int main()
{
//1、定义变量n和x数组，x[i]表示2 ×i的方格的铺法总数
int n;
cin >> n;
//2、初始化，1*1的方格铺法和1*2的方格铺法
x[1] = 1;
x[2] = 2;
//3、递推式，求2*i的方格铺法 x[i]=x[i-1]+x[i-2]
for(int i = 3; i <= n; i++)
x[i] = x[i-1] + x[i-2];
//4、输出答案
cout << x[n]; // 输出2×n的方格的铺法总数
return 0;
}
T5兔子数列
#include <iostream>
using namespace std;
const int N = 60;
long long f[N]; //用来存储兔子数（f[i]：第 i 个月的兔子数）
int main()
{
//1、定义变量n和数组f，f[i]表示第i个月的兔子数
int n;
cin >> n;
//2、初始化第一个月和第二个月的兔子数量
f[1] = 1;
f[2] = 1;
//3、递推式，求出每个月的兔子数量 f[i]=f[i-1]+f[i-2]
for(int i = 3; i <= n; i++)
{
/* 第i个月兔子数 =
第i-1个月兔子数+第i-2个月兔子数 */
f[i] = f[i-1] + f[i-2];
}
//4、输出答案
cout << f[n]; // 输出第 n 个月的兔子数
return 0;
}
T6流感传染
#include<iostream>
using namespace std;
const int N = 110;
int a[N][N];
int main()
{
//1、定义变量n,m,数组a来表示状态,sum统计最终感染的人数
int n, m, sum = 0;
//2、输入n、地图、天数
//2.1、输入地图的根据字符的不同，重新赋状态
cin >> n;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
char s;
cin >> s;
if (s == '.') a[i][j] = 0; //未被感染的
if (s == '@') a[i][j] = 1; //已被感染的
if (s == '#') a[i][j] = -1;//空的
}
}
cin >> m;
//3、遍历每一天
while (m > 1) //m-1天
{
m--;
//3.1、找到流感的人，把他健康的邻居感染，用数字2来表示
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (a[i][j] == 1) //防止在这一轮中，感染后的人感染下一轮的人，将邻居置为2
{
if (a[i + 1][j] == 0) a[i + 1][j] = 2;
if (a[i - 1][j] == 0) a[i - 1][j] = 2;
if (a[i][j + 1] == 0) a[i][j + 1] = 2;
if (a[i][j - 1] == 0) a[i][j - 1] = 2;
}
}
}
//3.2、再次遍历a数组，把刚才标记的状态，变成感染的状态
for (int i = 1; i <= n; i++) //这一轮被感染的人置为1
{
for (int j = 1; j <= n; j++)
{
if (a[i][j] == 2) a[i][j] = 1;
}
}
}
//4、遍历整个地图，统计被感染的人数，输出
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (a[i][j] == 1)
sum++;
}
}
cout << sum;
return 0;
}
这里空空如也
有帮助，赞一个