ZeroJudge 解題筆記：b558. 求數列第 n 項

作者：王一哲
日期：2025年7月27日


ZeroJudge 題目連結：b558. 求數列第 n 項

解題想法

這題的測資不大，而且遞迴關係也很簡單，可以先用遞迴建表，把 $1 \leq n \leq 500$ 對應的函數值都算出來，再逐行讀取測資、查表、輸出答案。也可以找一般式，先列出前幾項找規律 $$ \begin{align*} f(1) &= 1\\ f(2) &= f(1) + 1\\ f(3) &= f(2) + 2 \\ f(4) &= f(3) + 3 \\ &\vdots \\ f(n) &= f(n-1) + (n-1) \\ \end{align*} $$ 以上的式子相加之後可得 $$ f(n) = 1 + [1 + 2 + 3 + \dots + (n-1)] = 1 + \frac{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

公式解，使用時間約為 18 ms，記憶體約為 3.4 MB，通過測試。

import sys

for line in sys.stdin:
    n = int(line)
    print(1 + n*(n-1)//2)

公式解，使用時間約為 21 ms，記憶體約為 3.3 MB，通過測試。

while True:
    try:
        n = int(input())
        print(1 + n*(n-1)//2)
    except:
        break

C++ 程式碼

建表，使用時間約為 2 ms，記憶體約為 80 kB，通過測試。

#include <cstdio>
using namespace std;

int main() {
    int table[501] = {0};
    table[1] = 1;
    for(int i=2; i<501; i++) table[i] = table[i-1] + i - 1;
    int n;
    while(scanf("%d", &n) != EOF) printf("%d\n", table[n]);
    return 0;
}

公式解，使用時間約為 2 ms，記憶體約為 68 kB，通過測試。

#include <cstdio>
using namespace std;

int main() {
    int n;
    while(scanf("%d", &n) != EOF) printf("%d\n", 1 + n*(n-1)/2);
    return 0;
}