# C++ 基礎語法練習題：Unit-7 function 函數、內建函數 vs. 自訂函數、全域變數 vs. 區域變數

講義不是我寫的，原文連結為 [Yui Huang 演算法學習筆記：C++ 基礎語法](https://yuihuang.com/syntax/)
我只是將自己寫的練習題程式碼記錄下來。
最後更新日期：2024年11月12日

## [ZeroJudge: d039. 11044 - Searching for Nessy](https://zerojudge.tw/ShowProblem?problemid=d039)

### Python 程式碼

執行時間最久約為 27 ms，使用記憶體最多約為 3.3 MB，通過測試。

t = int(input())
for _ in range(t):
    n, m = map(int, input().split())
    print((n//3) * (m//3))

### C++ 程式碼

執行時間最久約為 3 ms，使用記憶體最多約為 348 kB，通過測試。

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t; cin >> t;
    for(int i=0; i<t; i++) {
        int n, m; cin >> n >> m;
        cout << (n/3) * (m/3) << "\n";
    }
    return 0;
}

## [ZeroJudge: a006. 一元二次方程式](https://zerojudge.tw/ShowProblem?problemid=a006)

### Python 程式碼

執行時間最久約為 21 ms，使用記憶體最多約為 3.3 MB，通過測試。

from math import sqrt

a, b, c = map(int, input().split())
D = b*b - 4*a*c
if D < 0: print("No real root")
elif D == 0: print(f"Two same roots x={-b//(2*a):d}")
else:
    x1 = (-b + int(sqrt(D)))//(2*a)
    x2 = (-b - int(sqrt(D)))//(2*a)
    print(f"Two different roots x1={x1:d} , x2={x2:d}")

### C++ 程式碼

執行時間最久約為 2 ms，使用記憶體最多約為 328 kB，通過測試。

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int a, b, c; cin >> a >> b >> c;
    int D = b*b - 4*a*c;
    if (D < 0) {
        cout << "No real root\n";
    } else if (D == 0) {
        int x = -b/(2*a);
        cout << "Two same roots x=" << x << "\n";
    } else {
        int x1 = (-b + int(sqrt(D)))/(2*a);
        int x2 = (-b - int(sqrt(D)))/(2*a);
        cout << "Two different roots x1=" << x1 << " , x2=" << x2 << "\n";
    }
    return 0;
}

## [ZeroJudge: d255. 11417 - GCD](https://zerojudge.tw/ShowProblem?problemid=d255)

### Python 程式碼

單純的寫法，理論上會比較慢，但因為測資範圍不大，實際測試時反而比下一個寫法快一點。執行時間最久約為 4.2 s，使用記憶體最多約為 3.3 MB，通過測試。

from math import gcd

while True:
    N = int(input())  # 讀取 N
    if N == 0: break  # 如果 N == 0 中止迴圈
    G = 0  # 要計算的 G 值
    for i in range(1, N):  # 依序産生 1 ~ N-1
        for j in range(i+1, N+1):  # 依序産生 i+1 ~ N 
            G += gcd(i, j)  # 更新 G 值
    print(G)  # 印出 G

寫法2，先將 N = 1 ~ 501 對應的 gcd 值都算出來儲存到表格中，計算 G 值時直接從表格讀取資料。執行時間最久約為 4.1 s，使用記憶體最多約為 23.8 MB，通過測試。

from math import gcd

table = dict()  # 儲存 gcd(i, j)，以數組 (i, j) 為 key
for i in range(1, 500):
    for j in range(i+1, 501):
        table[i, j] = gcd(i, j)

while True:
    N = int(input())  # 讀取 N
    if N == 0: break  # 如果 N == 0 中止迴圈
    G = 0  # 要計算的 G 值
    for i in range(1, N):  # 依序産生 1 ~ N-1
        for j in range(i+1, N+1):  # 依序産生 i+1 ~ N
            G += table[i, j]  # 更新 G 值
    print(G)  # 印出 G

寫法3，先將 N = 1 ~ 501 對應的 gcd 值都算出來儲存到二維串列的表格中，計算 G 值時直接從表格讀取資料。執行時間最久約為 3 s，使用記憶體最多約為 5.3 MB，通過測試。

from math import gcd

table = [[0]*501 for _ in range(500)]
for i in range(1, 500):
    for j in range(i+1, 501):
        table[i][j] = gcd(i, j)

while True:
    N = int(input())  # 讀取 N
    if N == 0: break  # 如果 N == 0 中止迴圈
    G = 0  # 要計算的 G 值
    for i in range(1, N):  # 依序産生 1 ~ N-1
        for j in range(i+1, N+1):  # 依序産生 i+1 ~ N 
            G += table[i][j]  # 更新 G 值
    print(G)  # 印出 G

### C++ 程式碼

寫法1，執行時間最久約為 0.3 s，使用記憶體最多約為 320 kB，通過測試。

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    while(true) {
        int N; cin >> N;  // 讀取 N
        if (N == 0) break;  // 如果 N == 0 中止迴圈
        int G = 0;  // 要計算的 G 值
        for(int i=1; i<N; i++)  // 依序産生 1 ~ N-1
            for(int j=i+1; j<=N; j++)  // 依序産生 i+1 ~ N
                G += __gcd(i, j);  // 更新 G 值

        cout << G << "\n";  // 印出 G
    }
    return 0;
}

寫法2，如果要用 pair 作為 key，只能使用 map，不能使用 unordered_map。執行時間最久約為 1 s，使用記憶體最多約為 7.9 MB，通過測試。

#include <iostream>
#include <map>
#include <utility>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    map<pair<int, int>, int> table;  // 儲存已經計算過的 gcd(i, j)，以 pair (i, j) 為 key
    for(int i=1; i<500; i++)
        for(int j=i+1; j<501; j++)
            table[make_pair(i, j)] = __gcd(i, j);
    
    while(true) {
        int N; cin >> N;  // 讀取 N
        if (N == 0) break;  // 如果 N == 0 中止迴圈
        int G = 0;  // 要計算的 G 值
        for(int i=1; i<N; i++)  // 依序産生 1 ~ N-1
            for(int j=i+1; j<=N; j++)  // 依序産生 i+1 ~ N
                G += table[make_pair(i, j)];  // 更新 G 值

        cout << G << "\n";  // 印出 G
    }
    return 0;
}

寫法3，先將 N = 1 ~ 501 對應的 gcd 值都算出來儲存到二維陣列的表格中，計算 G 值時直接從表格讀取資料。執行時間最久約為 11 ms，使用記憶體最多約為 1.3 MB，通過測試。

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int table[500][501] = {0};  // 儲存已經計算過的 gcd(i, j)
    for(int i=1; i<500; i++)
        for(int j=i+1; j<501; j++)
            table[i][j] = __gcd(i, j);
    
    while(true) {
        int N; cin >> N;  // 讀取 N
        if (N == 0) break;  // 如果 N == 0 中止迴圈
        int G = 0;  // 要計算的 G 值
        for(int i=1; i<N; i++)  // 依序産生 1 ~ N-1
            for(int j=i+1; j<=N; j++)  // 依序産生 i+1 ~ N
                G += table[i][j];  // 更新 G 值

        cout << G << "\n";  // 印出 G
    }
    return 0;
}

---

###### tags:`演算法`、`APCS`、`Python`、`C++`