1つの整数は合計2のべき乗の和に分割することができ、異なる分割の種数を求める.

1つの整数は、合計で2のべき乗の和に分割することができ、例えば、7=1+2+4 7=1+2+2+27=1+1+1+2+7=1+1+1+1+1+2+7=1+1+1+1+1+1+1+1+1+1+1+1+1+1の合計で6つの異なる分割方式がある.さらに、例えば、4=4、4=1+1+1、4=2+2、4=1+1+2に分割することができる.nの異なる分割の数をf(n)で表し、例えばf(7)=6である.
解析:f(1)(1)f(2)(11)(2)f(3)(111)(12)f(4)(1111)(112)(22)(4)f(11111)(122)(14)(1112)f(6)(111111)(11112)(114)(1122)(222)(24)
nが奇数である場合、各分割は必然的に1を含むので、各項は1を減らしてf(n−1)を得るので、f(n)=f(n−1)である.nが偶数である場合、すべてを2つのクラス(AクラスとBクラス)に分類することができ、Aクラスは1を含み、Bクラスは1を含まない.Aクラスでは区分ごとに1を減算f(n-1)が得られ、Bクラスでは必ず偶数であり、区分ごとに2を除算f(n/2)が得られる.従ってf(n)=f(n−1)+f(n/2)は,状態方程式を総合的に得た.
コード:

def f(n):
    if n == 1:
        return 1
    if n == 2:
        return 2
    else:
        if n % 2 != 0:
            return f(n - 1)
        else:
            return f(n - 1) + f(n // 2)


while True:
    num = int(input())
    print(f(num))