wikioi1011 数的计算 （2001年NOIP全国联赛普及组）
题目描述 Description我们要求找出具有下列性质数的个数(包含输入的自然数n):
先输入一个自然数n(n<=1000),然后对此自然数按照如下方法进行处理:
1. 不作任何处理;
2. 在它的左边加上一个自然数,但该自然数不能超过原数的一半;
3. 加上数后,继续按此规则进行处理,直到不能再加自然数为止.
输入描述 Input Description一个数n
输出描述 Output Description满足条件的数的个数
样例输入 Sample Input6
样例输出 Sample Output6
数据范围及提示 Data Size & Hint6个数分别是：
6
16
26
126
36
136
#include <iostream>using namespace std;int main(){ int i,n,a,sum[1001]; sum[0] = 0,sum [1] = 1; cin>>n; for(i = 2 ; i <= n ; i++) { a = sum[i/2] + 1; sum [i] = sum[i-1] + a; } cout<<sum[n] - sum[n-1]<<endl; return 0;}
分析：
我们要求找出具有下列性质数的个数(包含输入的自然数n):
先输入一个自然数n(n<=1000),然后对此自然数按照如下方法进行处理:
1. 不作任何处理;
2. 在它的左边加上一个自然数,但该自然数不能超过原数的一半;
3. 加上数后,继续按此规则进行处理,直到不能再加自然数为止.
一个数n
输出描述 Output Description满足条件的数的个数
样例输入 Sample Input6
样例输出 Sample Output6
数据范围及提示 Data Size & Hint6个数分别是：
6
16
26
126
36
136
#include <iostream>using namespace std;int main(){ int i,n,a,sum[1001]; sum[0] = 0,sum [1] = 1; cin>>n; for(i = 2 ; i <= n ; i++) { a = sum[i/2] + 1; sum [i] = sum[i-1] + a; } cout<<sum[n] - sum[n-1]<<endl; return 0;}
分析：
满足条件的数的个数
6
样例输出 Sample Output6
数据范围及提示 Data Size & Hint6个数分别是：
6
16
26
126
36
136
#include <iostream>using namespace std;int main(){ int i,n,a,sum[1001]; sum[0] = 0,sum [1] = 1; cin>>n; for(i = 2 ; i <= n ; i++) { a = sum[i/2] + 1; sum [i] = sum[i-1] + a; } cout<<sum[n] - sum[n-1]<<endl; return 0;}
分析：
6
6个数分别是：
6
16
26
126
36
136
#include <iostream>using namespace std;int main(){ int i,n,a,sum[1001]; sum[0] = 0,sum [1] = 1; cin>>n; for(i = 2 ; i <= n ; i++) { a = sum[i/2] + 1; sum [i] = sum[i-1] + a; } cout<<sum[n] - sum[n-1]<<endl; return 0;}分析：
递推
sum[6]表示不超过6的数开始，所有可能组合的和。若ans[6]表示所求值，则：sum[6] = ans[6]+sum[5]，以此类推。