# 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++`
Sign in with Wallet
Connect another wallet