数的计数

发布于 2019-04-02  11 次阅读


题目描述

我们要求找出具有下列性质数的个数(包含输入的自然数n):
  先输入一个自然数n(n<=1000),然后对此自然数按照如下方法进行处理:
  1. 不作任何处理;
  2. 在它的左边加上一个自然数,但该自然数不能超过原数的一半;
  3. 加上数后,继续按此规则进行处理,直到不能再加自然数为止.

输入

6

输出

6

思路

1.我们可以发现7的拆分数个数等于6的拆分数个数,8的拆分数个数等于7的拆分数个数加上它一半(4)的拆分数个数的和,所以我们就可以得出当n是偶数时f[n]:=f[n-1]+f[n div 2];当n是奇数时F[n]:=f[n-1];
2.递归:每一个数都等于他前面的数的和加一f[n]:=1+f[1]+f[2]…+f[n div 2]
3.在递归时将每一个数储存起来,递归时直接调用;

var
  a:array[1..1000]of longint;
  i,n:longint;
begin
  a[1]:=1;
  readln(n);
  for i:=2 to n do
    if odd(i) then a[i]:=a[i-1]
    else a[i]:=a[i-1]+a[i div 2];
  writeln(a[n]);
end.
]]>