日期:2025年7月27日
ZeroJudge 題目連結:b558. 求數列第 n 項
解題想法
這題的測資不大,而且遞迴關係也很簡單,可以先用遞迴建表,把 1≤n≤500 對應的函數值都算出來,再逐行讀取測資、查表、輸出答案。也可以找一般式,先列出前幾項找規律 f(1)=1f(2)=f(1)+1f(3)=f(2)+2f(4)=f(3)+3⋮f(n)=f(n−1)+(n−1) 以上的式子相加之後可得 f(n)=1+[1+2+3+⋯+(n−1)]=1+n(n−1)2
Python 程式碼
建表,使用時間約為 19 ms,記憶體約為 3.4 MB,通過測試。
import sys
table = [0]*501
table[1] = 1
for i in range(2, 501): table[i] = table[i-1] + i - 1
for line in sys.stdin:
print(table[int(line)])
建表,使用時間約為 20 ms,記憶體約為 3.3 MB,通過測試。
table = [0]*501
table[1] = 1
for i in range(2, 501): table[i] = table[i-1] + i - 1
while True:
try:
print(table[int(input())])
except:
break