洛谷 | P1028 数的计算（递推）
题目描述
我们要求找出具有下列性质数的个数(包含输入的自然数nn):
先输入一个自然数n(n<=1000),然后对此自然数按照如下方法进行处理:
- 不作任何处理;
- 在它的左边加上一个自然数,但该自然数不能超过原数的一半;
- 加上数后,继续按此规则进行处理,直到不能再加自然数为止.
输入输出格式
输入格式：
11个自然数n(n<=1000)
输出格式：
11个整数，表示具有该性质数的个数。
输入输出样例
输入样例#1： 复制
6输出样例#1： 复制
6说明
满足条件的数为
6，16，26，126，36，136
解题思路：
这是一个比较典型的递推题目，因为用递归或者其他思路会比较低效和难以理解。
考虑数字6，第一次有16、26、36，第二次有126、136，然后还有6本身（不做任何处理）。
那么，对于数字n，我们从数字1开始递推。
显然f(1) = 1，
f(2) = f(1) + 1
f(3) = f(1) + 1
f(4) = f(1) + f(2) + 1
...
f(n) = f(1) + f(2) + f(3) + ... + f(n/2) + 1
这个是f(n)的推导公式，显然，如果我们能够归纳出一个函数公式，那么解题只需要围绕这个公式就好了，代码也会非常简单。
源代码：C++
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <set>
#include <vector>
#include <string>
#include <string.h>
using namespace std;
#ifdef __MSYS__
#define printfd printf
#else
#define printfd
#endif
int main() {
#ifdef __MSYS__
freopen("test.txt", "r", stdin);
#endif
int n;
scanf("%d", &n);
int f[10000] = {0};
//经典递推题目
for(int i=1; i<=n; ++i){
for(int j=1; j<=i/2; ++j){
f[i] += f[j];
}
f[i]++;
}
printf("%d\n", f[n]);
return 0;
}本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-05-26，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录