复兴无基础第三十课 递推（二）
2025-11-23 15:31:43
发布于：上海
5阅读
0回复
0点赞
T1平面分割
#include <iostream>
using namespace std;
int a[1010]; //a[i]:第i条直线最多能将 这个圆分割成的部分数
int main() {
//1、定义变量n,进行输入,数组a进行存储
int n;
cin >> n;
//2、初始条件，1条直线最多可以将圆分割成两部分
a[1] = 2;
//3、递推出n条直线，a[i] = a[i - 1] + 交点数 + 1;
for(int i = 2; i <= n; i++){
a[i] = a[i - 1] + i; //递推式
}
//4、输出
//输出 n 条直线最多能将这个圆分割成的部分数
cout << a[n];
return 0;
}
T2格子涂色问题
#include <iostream>
using namespace std;
long long a[66]; //a[i]:把i个格子 按要求涂色的涂法
int main() {
//1、定义变量n,进行输入,定义数组a,进行存储
int n;
cin >> n;
//2、初始条件,1个格子时有3种涂法, 2个格子时有6种涂法,3个格子时有6种涂法
a[1] = 3;
a[2] = 6;
a[3] = 6;
//3、递推式:a[i]=a[i-1]+2*a[i-2]
for(int i = 4; i <= n; i++){
a[i] = a[i - 1] + 2 * a[i - 2];
}
//4、输出
cout << a[n]; //输出把 n 个格子按要求涂色的涂法
return 0;
}
T3平行线分割平面
#include <iostream>
using namespace std;
long long a[10010];
int main()
{
//1、定义变量n,进行输入,定义数组用来存储
int n;
cin >> n;
//2、初始条件,一对平行线最多能将圆分割成3部分
a[1] = 3;
//3、递推式求a[n]
for(int i = 2; i <= n; i++)
a[i] = a[i - 1] + 4 * i - 2;
//4、输出答案
cout << a[n];
return 0;
}
T4折线分割平面问题
#include <iostream>
using namespace std;
const int N = 10010;
int a[10010];
int main()
{
//1、定义变量c,进行输入,定义数组进行存储
int c;
cin >> c;
//2、初始化，1条折线能把平面分割成2部分
a[1] = 2;
//3、递推
for (int i = 2; i <= 10000; i++)
a[i] = a[i - 1] + 4 * (i - 1) + 1;
//4、处理c组样例
for (int i = 1; i <= c; i++)
{
//4.1、定义变量n,输入,输出答案
int n;
cin >> n;
cout << a[n] << endl;
}
return 0;
}
T5小码君的牛肉串
#include <iostream>
using namespace std;
long long f[50];
int main()
{
//1、定义变量n,进行输入，定义数组进行存储
int n;
cin >> n;
//2、初始化
f[1] = 3;
f[2] = 8;
//3、递推式求得答案
for(int i = 3; i <= n; i++)
f[i] = 2 * f[i - 1] + 2 * f[i - 2];
//4、输出
cout << f[n];
return 0;
}
这里空空如也
有帮助，赞一个