日期：2025年7月2日
ZeroJudge 題目連結：a216. 數數愛明明
解題想法
方法1，使用函式遞迴，但是可能會因為遞迴次數太多而超時。方法2，找一般式，例如 $$ \begin{align*} f(1) &= 1\\ f(2) &= 2 + f(1)\\ f(3) &= 3 + f(3)\\ & \vdots \\ f(n) &= n + f(n-1) \end{align*} $$ 將以上式子相加可得 $$ f(n) = 1 + 2 + 3 + \dots + n = \frac{1}{2} \cdot n(n+1) $$ 接下來求 $g(n)$，先列出幾行 $$ \begin{align*} g(1) &= 1\\ g(2) &= f(2) + g(1)\\ g(3) &= f(3) + g(2)\\ & \vdots \\ g(n) &= f(n) + g(n-1) \end{align*} $$ 將以上式子相加可得 \begin{align*} g(n) &= f(1) + f(2) + f(3) + \dots + f(n)\\ &= \frac{1}{2} \sum_{i=1}^n (i^2 + i)\\ &= \frac{1}{2} \cdot \left [ \frac{1}{6} \cdot n(n+1)(2n+1) + \frac{1}{2} \cdot n(n+1) \right ]\\ &= \frac{1}{12} \cdot n(n+1) \left [ (2n+1) + 3 \right ] \\ &= \frac{1}{6} \cdot n(n+1)(n+2)\\ \end{align*}
Python 程式碼
方法1，使用函式遞迴，果然不意外地在測試題會超時。
import sys
def f(n):
if n == 1: return 1
else: return n + f(n-1)
def g(n):
if n == 1: return 1
else: return f(n) + g(n-1)
for line in sys.stdin:
n = int(line)
print("{:d} {:d}".format(f(n), g(n)))
方法2，找出一般式直接代入 n 求答案，使用時間約為 18 ms，記憶體約為 3.3 MB，通過測試。
import sys
def f(n):
return int(n*(n+1)/2)
def g(n):
return int(n*(n+1)*(n+2)/6)
for line in sys.stdin:
n = int(line)
print("{:d} {:d}".format(f(n), g(n)))
