信息学奥赛 数的计数

来源：长沙信息学奥赛编程培训学校时间：2023/9/12 15:11:47

　　我们要求找出具有下列性质数的个数(包括输入的自然数n)。先输入一个自然数n(n≤1000)，然后对此自然数按照如下方法进行处理：

　　不作任何处理;

　　在它的左边加上一个自然数，但该自然数不能超过原数的一半;

　　加上数后，继续按此规则进行处理，直到不能再加自然数为止。

　　【输入】

　　自然数n(n≤1000)

　　【输出】

　　满足条件的数。

　　【输入样例】

　　6

　　【输出样例】

　　6

　　【提示】

　　【样例解释】

　　满足条件的数为如下所示：

　　6

　　16

　　26

　　126

　　36

　　136

　　思路：

　　这是一道递归题。废话，这道题都在递归的标签里

　　那要怎么做呢?

　　我们想一下，6的方案总数是多少呢?

　　是1 + 3的方案总数 + 2的方案总数 + 1的方案总数

　　为什么呢?

　　首先，6是不是本身就是一个方案?为什么?因为我们可以不作任何处理

　　所以，首先要加1

　　为什么要加3的方案总数呢?

　　因为6的前面可以加上3，3还可以继续往前加上2、1

　　加上3会多出多少种方案?当然是3的方案总数种

　　同样的道理，我们还需要加上2的方案总数、1的方案总数

　　因此，我们可以找出递推式：

　　f(n)=1+ f(1)+f(2)+f(3)+……+f(n/2)

　　---------------------------------------------------------------------------------------------------------------------------------

　　代码：

　　知道思路，代码就很好写了

　　#include

　　#pragma GCC optimize(3)//解释一下，这个东西叫O3优化，可以帮助我们加速代码

　　using namespace std;

　　int main(){

　　long long dp[1010];//用数组dp来存储某个数的方案总数

　　//dp[i]表示i的方案总数

　　dp[1]=1;//1的方案总数为1

　　int n;

　　cin>>n;//读入

　　for(int i=2;i<=n;i++){

　　//解释一下为什么循环要从2到n，因为我们算2加到n/2需要知道2、3、……n/2的方案总数

　　//所以我们需要从2算到n，这样才能正确算出n的方案总数

　　long long cnt=1;//因为6本身就是6的一种方案，所以直接加1

　　for(int j=1;j<=i/2;j++){//从1加到i/2

　　cnt+=dp[j];//加起来

　　}

　　dp[i]=cnt;//cnt就是i的方案总数，所以直接存起来

　　//我们用数组存储结果，可以避免超时

　　}

　　cout<

　　return 0;

尊重原创文章，转载请注明出处与链接：http://www.peixun360.com/2132/news/659972/违者必究！ 以上就是长沙信息学奥赛编程培训学校 小编为您整理 信息学奥赛 数的计数的全部内容。