当前位置:首页 > 递推 > 正文
SSOJ1227数的计算(NOIP2001)
240+

题目大意:一个数字n,可以不操作,也可以在左边加上一个不超过自己的正整数,加的正整数还可以继续在左边加正整数,能变出多少个数来?

题目描述

我们要求找出具有下列性质数的个数(包含输入的自然数n):

先输入一个自然数n(n≤1000),然后对此自然数按照如下方法进行处理

1.不作任何处理:

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

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

输入

一个数n

输出

满足条件的数的个数

样例输入

6

样例输出

6

提示

提示:样例生成的数有6,16,26,126,36,136。

NOIP2001普及组第一题

解题思路

理解题目后,应该是比较简单的。可以用整体分析法寻找递推关系式。

f[n]表示n的方案数,n在左边加一个数i,数字i可以像n一样操作,故左边加i可多加方案数f[i]。

n的左边可以加1、2、…、n/2,也可以不加,所以f[n] = 1 + f[1] + f[2] + … + f[n/2]。

程序实现

更多

About

坚决不Copy代码!

本文标签:,,,,,,

SSOJ1227数的计算(NOIP2001):等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter