首页 > 试题广场 >

整数拆分

[编程题]整数拆分

热度指数：27672 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

一个整数总可以拆分为2的幂的和，例如： 7=1+2+4 7=1+2+2+2 7=1+1+1+4 7=1+1+1+2+2 7=1+1+1+1+1+2 7=1+1+1+1+1+1+1 总共有六种不同的拆分方式。再比如：4可以拆分成：4 = 4，4 = 1 + 1 + 1 + 1，4 = 2 + 2，4=1+1+2。用f(n)表示n的不同拆分的种数，例如f(7)=6. 要求编写程序，读入n(不超过1000000)，输出f(n)%1000000000。

输入描述:

每组输入包括一个整数：N(1<=N<=1000000)。

输出描述:

对于每组数据，输出f(n)%1000000000。

示例1

输入

输出

算法知识视频讲解

Python

TimeMac

while True:
    try:
        num = int(input())
        dp = [0,1]
        for i in range(2,num+1):
            if i & 1:
                dp.append(dp[i-1])
            else:
                dp.append(dp[i-1]+dp[i//2])
        print(dp[num]%1000000000)
    except Exception:
        break

编辑于 2018-10-11 11:24:48 回复(0)

Python

华科平凡

python

这是动态规则的题目，关键是找到转移方程。

num = int(input())
dp = [1 for i in range(num + 1)]
for i in range(1, num + 1):
    if i % 2 == 1:
        dp[i] = dp[i - 1]
    else:
        dp[i] = dp[i - 1] + dp[i // 2]
print(dp[-1] % 1000000000)

发表于 2018-03-27 12:00:42 回复(0)