A26534. 数的计数
填空题
中等
知识点
题目描述
数的计数
题目描述
我们要求找出具有下列性质数的个数（包括输入的自然数n）。先输入一个自然数n(n≤1000)，然后对此自然数按照如下方法进行处理：
不作任何处理；
在它的左边加上一个自然数，但该自然数不能超过原数的一半；
加上数后，继续按此规则进行处理，直到不能再加自然数为止。
输入
自然数n(n≤1000)。
输出
满足条件的数。
输入样例
6输出样例
6提示
样例解释
满足条件的数为如下所示：
6
16
26
126
36
136参考答案
#include<bits/stdc++.h>
using namespace std;
int a[1005];//a[i]:数字i能生成的数字数量
int main()
{
int n;
cin >> n;
a[0] = 1;
for(int i = 1; i <= n; ++i)
for(int j = 0; j <= i/2; ++j)
a[i] += a[j];
cout << a[n];
return 0;
}答案解析
#include<bits/stdc++.h>
using namespace std;
int num[1005];//num[i]:数字i能生成的数字数量
int getNum(int k)//获取数字k能生成的数字数量
{
if(k == 0)
return 1;
if(num[k] > 0)//记忆化递归
return num[k];
int s = 0;
for(int i = 0; i <= k/2; ++i)//n坐标的数字
s += getNum(i);
return num[k] = s;//记忆状态
}
int main()
{
int n;
cin >> n;
cout << getNum(n);
return 0;
}
上一题
下一题