P1028 [NOIP2001 普及组] 数的计算
计算 普及
2023-09-27 14:28:12 时间
一、深度优先搜索
#include <bits/stdc++.h>
using namespace std;
int n;
//毫不意外,只通过了5个测试点,TLE了15个点~
int dfs(int x) {
//1就没法继续分了,同时,由于题目说:原数列不做任何修改就直接统计为一种合法数列。所以返回1
if (x == 1) return 1;
//不是1,可以分
int ans = 1;//它自己就是一种
//在它后面不断加入[1,x/2]的数字,都可以增加方法数量
for (int i = 1; i <= x / 2; i++) ans += dfs(i);
//返回方法数量
return ans;
}
int main() {
//输入
cin >> n;
//计算并输出
cout << dfs(n) << endl;
return 0;
}
二、记忆化搜索
#include <bits/stdc++.h>
using namespace std;
int n;
const int N = 1010;
int f[N];
int dfs(int x) {
//存在就返回
if (f[x]) return f[x];
//1就没法继续分了,同时,由于题目说:原数列不做任何修改就直接统计为一种合法数列。所以返回1
if (x == 1) return f[x] = 1;
//不是1,可以分
int ans = 1;//它自己就是一种
//在它后面不断加入[1,x/2]的数字,都可以增加方法数量
for (int i = 1; i <= x / 2; i++) ans += dfs(i);
//返回方法数量
return f[x] = ans;
}
int main() {
//输入
cin >> n;
//计算并输出
cout << dfs(n) << endl;
return 0;
}
三、递推
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int f[N];
int n;
int main() {
//输入
cin >> n;
//边界条件:1
f[1] = 1;
for (int i = 2; i <= n; i++) {
//任何数字,独立成为一个
f[i] = 1;
//所有从1到它的一半的,都可以增加进来
for (int j = 1; j <= i / 2; j++) f[i] += f[j];
}
//总个数
cout << f[n] << endl;
return 0;
}
相关文章
- php计算距离现在的时间
- 初入云计算行业,可以考取哪些云计算证书?
- 全球云计算巨头盯上云游戏,吹响全面战争集结号
- 甲骨文微软再次结盟,SAP转型云计算,全球云计算格局将生变?
- 《云计算:概念、技术与架构》一3.3 目标与收益
- 张北将成规模150万台服务器的云计算产业基地
- 云计算的高增长将持续推动光模块行业景气度
- 大型云计算提供商进一步拉大中小型厂商的差距
- 大数据流式计算的应用特征和技术挑战
- 保障G20峰会网络空间安全阿里云给出云计算和大数据药方
- 瞩望“大计算+大数据”
- 计算坡度与坡向
- 阿里巴巴2017财年收入1582亿元 云计算业务增长
- AMD在SC16超算大会上宣布“Radeon开放计算平台”1.3版本
- 互联网大佬口口声声的人工智能,笑到最后的也许是马云的云计算
- 云端流计算、在线业务、实时分析 闭环设计 - 阿里云RDS、HybridDB for PostgreSQL最佳实践