题目描述
我们要求找出具有下列性质数的个数(包含输入的自然数n):
先输入一个自然数n(n≤1000),然后对此自然数按照如下方法进行处理:
-
不作任何处理;
-
在它的左边加上一个自然数,但该自然数不能超过原数的一半;
-
加上数后,继续按此规则进行处理,直到不能再加自然数为止.
输入输出格式
输入格式：
1个自然数n(n≤1000)
输出格式：
1个整数，表示具有该性质数的个数。
输入输出样例
输入样例#1：
6
输出样例#1：
6
说明
满足条件的数为
6，16，26，126，36，136
解题：
我们从n=1开始，列出具有该性质的数，寻找其中的规律，用f(n)表示具有该性质数的个数：
|
n |
具有该性质的数 |
f(n) |
|
1 |
1 |
1 |
|
2 |
2 |
1 |
|
3 |
3, 13 |
1+1 |
|
4 |
4, 14, 24,124 |
1+1+2 |
|
5 |
5, 15, 25,125 |
1+1+2 |
|
6 |
6, 16, 26,126, 36,136 |
1+1+2+2 |
|
7 |
7, 17, 27,127, 37,137 |
1+1+2+2 |
|
8 |
8, 18, 28,128, 38,138, 48,148,248,1248 |
1+1+2+2+4 |
|
9 |
9, 19, 29,129, 39,139, 49,149,249,1249 |
1+1+2+2+4 |
|
n |
f(n) |
|
1 |
1 |
|
2 |
1+f(1) |
|
3 |
1+f(1) |
|
4 |
1+f(1)+f(2) |
|
5 |
1+f(1)+f(2) |
|
6 |
1+f(1)+f(2)+f(3) |
|
7 |
1+f(1)+f(2)+f(3) |
|
8 |
1+f(1)+f(2)+f(3)+f(4) |
|
9 |
1+f(1)+f(2)+f(3)+f(4) |
大家看出规律了吗？f(n)=1+f(1)+f(2)+…+f(不超过n/2的最大整数）。这种寻找规律的方法叫做递推。
现在我们可以轻松地写出程序了：
using namespace std;int main(){int n,f[1001];cin>>n;for(int i=1;i<=n;i++){f[i]=1;for(int j=1;j<=i/2;j++){f[i]+=f[j];}}cout <<f[n];return 0;}
转自公众号：
冉爸学堂