---
# System prepended metadata

title: C++ 基礎語法練習題：Unit-10 遞迴 (Recursion)
tags: [演算法, C++, APCS, Python]

---

# C++ 基礎語法練習題：Unit-10 遞迴 (Recursion)

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


## [ZeroJudge: c002. 10696 - f91](https://zerojudge.tw/ShowProblem?problemid=c002)

### Python 程式碼

執行時間最久約為 25 ms，使用記憶體最多約為 3.3 MB，通過測試。
```python=
def f91(x):
    if x >= 101: return x-10
    return f91(f91(x+11))

while True:
    n = int(input())
    if n == 0: break
    print(f"f91({n:d}) = {f91(n):d}")
```

### C++ 程式碼

執行時間最久約為 2 ms，使用記憶體最多約為 348 kB，通過測試。
```cpp=
#include <iostream>
using namespace std;

int f91(int x) {
    if (x >= 101) return x-10;
    return f91(f91(x+11));
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    while(true) {
        int n; cin >> n;
        if (n == 0) break;
        cout << "f91(" << n << ") = " << f91(n) << "\n";
    }
    return 0;
}
```


## [ZeroJudge: c813. 11332 - Summing Digits](https://zerojudge.tw/ShowProblem?problemid=c813)

### Python 程式碼

執行時間最久約為 0.1 ms，使用記憶體最多約為 3.3 MB，通過測試。
```python=
def f(x):
    tot = 0
    while x > 0:
        tot += x%10
        x //= 10
    return tot

def g(x):
    tot = f(x)
    if 1 <= tot <= 9: return tot
    return g(tot)

while True:
    n = int(input())
    if n == 0: break
    print(g(n))
```

### C++ 程式碼

執行時間最久約為 7 ms，使用記憶體最多約為 340 kB，通過測試。
```cpp=
#include <iostream>
using namespace std;

int f(int x) {
    int tot = 0;
    while(x > 0) {
        tot += x%10;
        x /= 10;
    }
    return tot;
}

int g(int x) {
    int tot = f(x);
    if (tot >= 1 && tot <= 9) return tot;
    return g(tot);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    while(true) {
        int n; cin >> n;
        if (n == 0) break;
        cout << g(n) << "\n";
    }
    return 0;
}
```


## [ZeroJudge: f640. 函數運算式求值](https://zerojudge.tw/ShowProblem?problemid=f640)

### Python 程式碼

遞迴版，執行時間最久約為 19 ms，使用記憶體最多約為 3.3 MB，通過測試。
```python=
data = list(input().split())
idx = 0

def solve():
    global idx
    s = data[idx]
    if s == "f":
        idx += 1; x = solve()
        return 2*x - 3
    elif s == "g":
        idx += 1; x = solve()
        idx += 1; y = solve()
        return 2*x + y - 7
    elif s == "h":
        idx += 1; x = solve()
        idx += 1; y = solve()
        idx += 1; z = solve()
        return 3*x - 2*y + z
    else:
        return int(s)

print(solve())
```

### C++ 程式碼

遞迴版，執行時間最久約為 3 ms，使用記憶體最多約為 376 kB，通過測試。
```cpp=
#include <iostream>
#include <vector>
#include <string>
using namespace std;

vector<string> data;
int idx = 0;

int solve() {
    string s = data[idx];
    if (s == "f") {
        idx++; int x = solve();
        return 2*x - 3;
    } else if (s == "g") {
        idx++; int x = solve();
        idx++; int y = solve();
        return 2*x + y - 7;
    } else if (s == "h") {
        idx++; int x = solve();
        idx++; int y = solve();
        idx++; int z = solve();
        return 3*x - 2*y + z;
    } else {
        return stoi(s);
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    string s;
    while(cin >> s) data.push_back(s);
    cout << solve() << "\n";
    return 0;
}
```


## [ZeroJudge: e446. 排列生成](https://zerojudge.tw/ShowProblem?problemid=e446)

### Python 程式碼

遞迴解，第8筆測資開始超時。
```python=
def perm(depth, maxDepth, nums, tested):
    if depth == maxDepth:
        print(*nums)
        return
    for i in range(1, N+1):
        if i in tested: continue
        tested.add(i)
        nums.append(i)
        perm(depth+1, maxDepth, nums, tested)
        tested.remove(i)
        nums.pop()

N = int(input())
perm(0, N, [], set())
```

### C++ 程式碼

遞迴解，執行時間最久約為 9.3 s，使用記憶體最多約為 344 kB，通過測試。
```cpp=
#include <iostream>
#include <vector>
#include <set>
using namespace std;

int N;
void perm(int depth, int maxDepth, vector<int>& nums, set<int>& tested) {
    if (depth == maxDepth) {
        for(int i=0; i<(int)nums.size(); i++)
            cout << nums[i] << " \n"[i == (int)nums.size()-1];
        return;
    }
    for(int i=1; i<=N; i++) {
        if (tested.count(i) == 1) continue;
        tested.insert(i);
        nums.push_back(i);
        perm(depth+1, maxDepth, nums, tested);
        tested.erase(i);
        nums.pop_back();
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> N;
    vector<int> nums;
    set<int> tested;
    perm(0, N, nums, tested);
    return 0;
}
```

使用 algorithm next_permutation 作弊，執行時間最久約為 7.8 s，使用記憶體最多約為 352 kB，通過測試。
```cpp=
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int N; cin >> N;
    int nums[N];
    for(int i=0; i<N; i++) {
        nums[i] = i+1;
        cout << i+1 << " \n"[i == N-1];
    }
    while(next_permutation(nums, nums+N)) {
        for(int i=0; i<N; i++)
            cout << nums[i] << " \n"[i == N-1];
    }
    return 0;
}
```

## [ZeroJudge: f168. m4a2-分配寶物(Treasure)](https://zerojudge.tw/ShowProblem?problemid=f168)

### Python 程式碼

寫法1，執行時間最久約為 18 ms，使用記憶體最多約為 3.3 MB，通過測試。
```python=
import sys

for line in sys.stdin:
    n = int(line)  # 寶物數量
    vs = list(map(int, input().split()))  # 寶物價值
    vs.sort(reverse=True)  # 由大到小排序
    tot = sum(vs)  # 寶物價值加總
    if tot%3: print("NO")  # 如果不能被3整除，印出 NO
    else:  # 如果可以被3整除
        avg = tot//3  # 平均值
        dis = [avg]*3  # 每個人要分到的寶物價值
        i = 0  # 目前要拿寶物的人
        for v in vs:  # 依序由 vs 取出資料 v
            cnt = 0  # 目前測試的人數
            while dis[i] < v and cnt < 3:  # 如果第 i 個人還需要分配的價值小於 v 而且還有人沒有測試過
                i = (i+1)%3  # 更新 i，換下一個人，如果 i == 3 則輪回到 i == 0
                cnt += 1  # 已測試人數加 1
            if cnt == 3: break  # 如果已測試 3 個人，中止迴圈
            dis[i] -= v  # 第 i 個人還需要分配的價值扣掉 v
            i = (i+1)%3  # 更新 i，換下一個人，如果 i == 3 則輪回到 i == 0
        # end of for loop
        if dis[0] == dis[1] == dis[2] == 0: print("YES")  # 如果 dis 內容都是 0，已平分，印出 YES
        else: print("NO")  # 否則印出 NO
```

寫法2，遞迴版，執行時間最久約為 27 ms，使用記憶體最多約為 3.4 MB，通過測試。
```python=
import sys

# 輸入寶物價值 vs，由 vs 讀資料的索引值 i，vs 長度 imax
# 每個人還要分配的寶物價值 dis，第 j 個人，jmax 為人數，cnt 為已測試人數 
def solve(vs, i, imax, dis, j, jmax, cnt):
    j %= jmax  # 避免 j 出界
    if i == imax or cnt == jmax:  # 如果 i 已出界或每個人都已測試
        if dis[0] == dis[1] == dis[2] == 0: return True  # 如果 dis 內容都是 0，回傳 True
        else: return False  # 否則回傳 False
    if dis[j] >= vs[i]:  # 如果第 j 個人還要分配的寶物價值大於等於 vs[i]
        dis[j] -= vs[i]  # 扣掉 vs[i]，再遞迴，測試下一個寶物及下一個人，cnt 歸零
        return solve(vs, i+1, imax, dis, j+1, jmax, 0)
    else:  # 遞迴，測試這個寶物及下一個人，cnt 加 1
        return solve(vs, i, imax, dis, j+1, jmax, cnt+1)

for line in sys.stdin:
    n = int(line)  # 寶物數量
    vs = list(map(int, input().split()))  # 寶物價值
    vs.sort(reverse=True)  # 由大到小排序
    tot = sum(vs)  # 寶物價值加總
    if tot%3: print("NO")  # 如果不能被3整除，印出 NO
    else:  # 如果可以被3整除
        if solve(vs, 0, n, [tot//3]*3, 0, 3, 0): print("YES")
        else: print("NO")
```

### C++ 程式碼

寫法1，執行時間最久約為 3 ms，使用記憶體最多約為 352 kB，通過測試。
```cpp=
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n;  // 寶物數量
    while(cin >> n) {
        vector<int> vs;  // vs 寶物價值
        int tmp, tot = 0;  // tmp 暫存用，tot 寶物價值加總
        for(int i=0; i<n; i++) {
            cin >> tmp; vs.push_back(tmp); tot += tmp;
        }
        sort(vs.begin(), vs.end(), greater<int>());  // 由大到小排序
        
        if (tot%3) {
            cout << "NO\n";  // 如果不能被3整除，印出 NO
        } else {  // 如果可以被3整除
            int avg = tot/3;  // 平均值
            vector<int> dis (3, avg);  // 每個人要分到的寶物價值
            int i = 0;  // 目前要拿寶物的人
            for(int v : vs) {  // 依序由 vs 取出資料 v
                int cnt = 0;  // 目前測試的人數
                while(dis[i] < v && cnt < 3) {  // 如果第 i 個人還需要分配的價值小於 v 而且還有人沒有測試過
                    i = (i+1)%3;  // 更新 i，換下一個人，如果 i == 3 則輪回到 i == 0
                    cnt++;  // 已測試人數加 1
                }
                if (cnt == 3) break;  // 如果已測試 3 個人，中止迴圈
                dis[i] -= v;  // 第 i 個人還需要分配的價值扣掉 v
                i = (i+1)%3;  // 更新 i，換下一個人，如果 i == 3 則輪回到 i == 0
            }
            if (dis[0] == 0 && dis[1] == 0 && dis[2] == 0) {
                cout << "YES\n";  // 如果 dis 內容都是 0，已平分，印出 YES
            } else {
                cout << "NO\n";  // 否則印出 NO
            }
        }
    }
    return 0;
}
```

寫法2，遞迴版，執行時間最久約為 2 ms，使用記憶體最多約為 336 kB，通過測試。
```cpp=
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/* 輸入寶物價值 vs，由 vs 讀資料的索引值 i，vs 長度 imax
   每個人還要分配的寶物價值 dis，第 j 個人，jmax 為人數，cnt 為已測試人數 */
bool solve(vector<int>& vs, int i, int imax, vector<int>& dis, int j, int jmax, int cnt) {
    j %= jmax;  // 避免 j 出界
    if (i == imax || cnt == jmax) {  // 如果 i 已出界或每個人都已測試
        if (dis[0] == 0 && dis[1] == 0 && dis[2] == 0) return true;  // 如果 dis 內容都是 0，回傳 true
        else return false;  // 否則回傳 false
    }
    if (dis[j] >= vs[i]) {  // 如果第 j 個人還要分配的寶物價值大於等於 vs[i]
        dis[j] -= vs[i];  // 扣掉 vs[i]，再遞迴，測試下一個寶物及下一個人，cnt 歸零
        return solve(vs, i+1, imax, dis, j+1, jmax, 0);
    } else {  // 遞迴，測試這個寶物及下一個人，cnt 加 1
        return solve(vs, i, imax, dis, j+1, jmax, cnt+1);
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n;  // 寶物數量
    while(cin >> n) {
        vector<int> vs;  // 寶物價值
        int v, tot = 0;  // v 暫存寶物價值的變數，tot 寶物價值加總
        for(int i=0; i<n; i++) {
            cin >> v; vs.push_back(v); tot += v;
        } 
        sort(vs.begin(), vs.end(), greater<int>());  // 由大到小排序
        if (tot%3) {  // 如果不能被3整除，印出 NO
            cout << "NO\n";
        } else {  // 如果可以被3整除
            vector<int> dis (3, tot/3);
            if (solve(vs, 0, n, dis, 0, 3, 0)) cout << "YES\n";
            else cout << "NO\n";
        }
    }
    return 0;
}
```

## [ZeroJudge: d044. 00640 - Self Numbers](https://zerojudge.tw/ShowProblem?problemid=d044)

### Python 程式碼

使用 set，執行時間最久約為 2.7 s，使用記憶體最多約為 161.9 MB，通過測試。
```python=
def d(n):
    tot = n
    while n > 0:
        tot += n%10
        n //= 10
    return tot

imax = 1000000
nums = set(range(1, imax+1))
tested = set()
for i in range(1, imax+1):
    x = d(i)
    if x in tested: continue
    tested.add(x)
    if x <= imax: nums.remove(x)

ans = sorted(list(nums))
for a in ans: print(a)
```

使用 list 記錄測試過的數字，執行時間最久約為 2.5 s，使用記憶體最多約為 13.7 MB，通過測試。
```python=
def d(n):
    tot = n
    while n > 0:
        tot += n%10
        n //= 10
    return tot

imax = 1000000
tested = [False]*(imax+1)
for i in range(1, imax+1):
    x = d(i)
    if x > imax or tested[x]: continue
    tested[x] = True

for x in range(1, imax+1):
    if not tested[x]:
        print(x)
```

### C++ 程式碼

使用 set，執行時間最久約為 0.5 s，使用記憶體最多約為 46.1 MB，通過測試。
```cpp=
#include <iostream>
#include <set>
using namespace std;

int d(int n) {
    int tot = n;
    while(n > 0) {
        tot += n%10;
        n /= 10;
    }
    return tot;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    const int imax = 1000000;
    set<int> nums, tested;
    for(int i=1; i<=imax; i++) nums.insert(i);
    for(int i=1; i<=imax; i++) {
        int x = d(i);
        if (tested.count(x) == 1) continue;
        tested.insert(x);
        nums.erase(x);
    }
    for(auto num : nums) cout << num << "\n";
    return 0;
}
```

使用 vector 記錄測試過的數字，執行時間最久約為 32 ms，使用記憶體最多約為 432 kB，通過測試。
```cpp=
#include <iostream>
#include <vector>
using namespace std;

int d(int n) {
    int tot = n;
    while(n > 0) {
        tot += n%10;
        n /= 10;
    }
    return tot;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    const int imax = 1000000;
    vector<bool> tested(imax+1, false);
    for(int i=1; i<=imax; i++) {
        int x = d(i);
        if (x > imax || tested[x]) continue;
        tested[x] = true;
    }
    for(int i=1; i<=imax; i++) {
        if (!tested[i]) {
            cout << i << "\n";
        }
    }
    return 0;
}
```

---

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