發表新討論
#40845: 解答 c++


hs210023@students.hshs.chc.edu ... (天底下最帥的那個男人)

學校 : 不指定學校
編號 : 274462
來源 : [39.9.190.55]
最後登入時間 ：
2024-06-17 21:52:54
a216. 數數愛明明 | From: [27.247.62.93] | 發表日期 : 2024-06-14 21:54
這個問題的核心是計算兩個遞迴函數 f(n) 和 g(n) 的值。根據問題描述：

 

  • f(n) = n + f(n-1)，並且 f(1) = 1
  • g(n) = f(n) + g(n-1)，並且 g(1) = 1

 

為了有效地計算這些值，我們可以使用動態規劃來避免重複計算。這樣可以在較短的時間內處理較大的 n 值。

 

以下是解決這個問題的程式碼：
 
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<long long> f(30001, 0);
    vector<long long> g(30001, 0);

    f[1] = 1;
    g[1] = 1;

    for (int i = 2; i <= 30000; ++i) {
        f[i] = i + f[i - 1];
        g[i] = f[i] + g[i - 1];
    }

    int n;
    while (cin >> n) {
        cout << f[n] << " " << g[n] << endl;
    }

    return 0;
}

 

說明

 

  1. 初始化 f 和 g：
    • 使用 vector 容器來儲存 f 和 g 的值，大小設定為 30001 以確保能夠處理最大值 n = 30000。
    • 初始化 f[1] 和 g[1] 為 1。
  2. 動態規劃計算 f 和 g：
    • 使用迴圈從 2 到 30000 計算 f 和 g 的值。
    • 對於每個 i，計算 f[i] = i + f[i - 1]。
    • 計算 g[i] = f[i] + g[i - 1]。
  3. 處理輸入和輸出：
    • 使用 cin 讀取輸入的 n 值，並輸出對應的 f[n] 和 g[n]。

 

這樣的程式碼能夠高效地計算 f(n) 和 g(n)，並且能夠處理大範圍的 n 值。希望這個解決方案對你有幫助！
 
ZeroJudge Forum