E20742: 泰波拿契數

math, implementation, http://cs101.openjudge.cn/practice/20742/

泰波拿契数列 Tn 定义是

$T_{0} = 0, T_{1} = 1, T_{2} = 1, a n d T_{n + 3} = T_{n} + T_{n + 1} + T_{n + 2} f o r n >= 0$ .

给定n请算出Tn

n的范围:1<=n<=30

输入

一个正整数n

输出

一个正整数k

样例输入

样例输出

提示

T3 = 0 + 1 + 1 = 2 T4 = 1 + 1 + 2 = 4

python

def tribonacci(n):
    if n == 0:
        return 0
    elif n <= 2:
        return 1
    trib = [0, 1, 1] + [0] * (n - 2)
    for i in range(3, n + 1):
        trib[i] = trib[i - 1] + trib[i - 2] + trib[i - 3]
    return trib[n]

# 读取输入并处理
n = int(input())
print(tribonacci(n))

E20742: 泰波拿契數 ​

E20742: 泰波拿契數