题目描述
我们要求找出具有下列性质数的个数(包括输入的自然数 nn)。先输入一个自然数 n(n≤1000)n(n≤1000)，然后对此自然数按照如下方法进行处理：
不作任何处理；
在它的左边加上一个自然数，但该自然数不能超过原数的一半；
加上数后，继续按此规则进行处理，直到不能再加自然数为止。
输入格式
自然数 n(n≤1000)n(n≤1000)。
输出格式
满足条件的数的个数。
样例1
| 输入 | 输出 |
|---|---|
| 6 | 6 |
样例解释
满足条件的数为 6 个，分别是：16、26、126、36、136
递归方法
def num(n):
global ls
if n < len(ls):
return
else:
num(int(n/2))
for i in range(len(ls), n+1):
ls.append(sum(ls[:int(i/2)+1]))
return
n = int(input())
ls = [1, 1, 2, 2]
num(n)
print(ls[n])
非递归
n = int(input())
ls = [1, 1, 2, 2]
for i in range(4, 1001):
ls.append(sum(ls[:int(i/2)+1]))
print(ls[n])
感觉递归写的很烂，求大佬救救QAQ