# 0-9 函式及 0-10 遞迴

講義不是我寫的，網址在此 https://emanlaicepsa.github.io/2020/10/21/0-index/
我只是將自己寫的練習題程式碼記錄下來。
最後更新日期：2024年10月6日

## [TOJ: 170 / 各種星星樹](https://toj.tfcis.org/oj/pro/170/)

### Python 程式碼

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

def treeA(h, d=0):  # A 類樹，h 為高度，d 為向右平移的格數，預設為 0
    for i in range(1, h+1):  # 印出 h 層
        for _ in range(1, h-i+d+1): print(" ", end="")  # 印出左側空格共 h-i+d 格
        for _ in range(1, 2*i): print("*", end="")  # 印出星號共 2*i-1 個
        print()  # 換行

def treeB(h):  # A 類樹，h 為高度
    treeA(h); treeA(h)  # 只呼 treeA 兩次

def treeC(h):  # C 類樹，h 為底層高度
    for i in range(1, h+1): treeA(i, h-i)  # 呼叫 treeA 共 h 次，向右平移 h-i 格

def treeD(h):  # D 類樹，h 為高度/10
    treeA(10*h)  # 呼叫 treeA，代入 10*h

def treeE(h):  # E 類樹，h 為高度，底部左、右各加2格 #
    treeA(h, 2)  # 呼叫 treeA，代入 (h, 2)
    for _ in range(1, 2*h+4): print("#", end="")  # 印出 2*h+3 個 #
    print()   # 換行

t = int(input())
for _ in range(t):
    line = input().split()
    c = line[0]
    h = int(line[1])
    if c == 'A': treeA(h)
    elif c == 'B': treeB(h)
    elif c == 'C': treeC(h)
    elif c == 'D': treeD(h)
    elif c == 'E': treeE(h)
    elif c == 'F': treeA(2*h)
    elif c == 'G': treeA(3*h)
    elif c == 'H': treeA(7*h)
    elif c == 'I': treeA(4*h-1)
    print()

### C++ 程式碼

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

#include <iostream>
using namespace std;

void treeA(int h, int d=0) {  // A 類樹，h 為高度，d 為向右平移的格數，預設為 0
    for(int i=1; i<=h; i++) {  // 印出 h 層
        for(int j=1; j<=h-i+d; j++) cout << " ";  // 印出左側空格共 h-i+d 格
        for(int j=1; j<=2*i-1; j++) cout << "*";  // 印出星號共 2*i-1 個
        cout << "\n";  // 換行
    }
}

void treeB(int h) {  // A 類樹，h 為高度
    treeA(h); treeA(h);  // 只呼 treeA 兩次
}

void treeC(int h) {  // C 類樹，h 為底層高度
    for(int i=1; i<=h; i++) treeA(i, h-i);  // 呼叫 treeA 共 h 次，向右平移 h-i 格
}

void treeD(int h) {  // D 類樹，h 為高度/10
    treeA(10*h);  // 呼叫 treeA，代入 10*h
}

void treeE(int h) {  // E 類樹，h 為高度，底部左、右各加2格 #
    treeA(h, 2);  // 呼叫 treeA，代入 (h, 2)
    for(int i=1; i<=2*h+3; i++) cout << "#";  // 印出 2*h+3 個 #
    cout << "\n";
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t; cin >> t;
    for(int i=0; i<t; i++) {
        char c; int h; cin >> c >> h;
        if (c == 'A') treeA(h);
        else if (c == 'B') treeB(h);
        else if (c == 'C') treeC(h);
        else if (c == 'D') treeD(h);
        else if (c == 'E') treeE(h);
        else if (c == 'F') treeA(2*h);
        else if (c == 'G') treeA(3*h);
        else if (c == 'H') treeA(7*h);
        else if (c == 'I') treeA(4*h-1);
        cout << "\n";
    }        
    return 0;
}

## [ZeroJudge: a227. 河內塔](https://zerojudge.tw/ShowProblem?problemid=a227)

### Python 程式碼

執行時間最久約為 0.1 s，使用記憶體最多約為 4.4 MB，通過測試。

import sys

def hanoi(n, src, aux, dst):  # 盤子數量 n，來源 src，輔助 aux，目標 dst
    if n == 1:  # 遞迴出口
        print(f"Move ring {n:d} from {src:s} to {dst:s}")
    else:
        hanoi(n-1, src, dst, aux)  # 遞迴，盤子數量 n-1，盤子由 src 移動到 aux
        print(f"Move ring {n:d} from {src:s} to {dst:s}")  # 盤子 n 由 src 移動到 dst
        hanoi(n-1, aux, src, dst)  # 遞迴，盤子數量 n-1，編號 1，盤子由 aux 移動到 dst

for line in sys.stdin:
    n = int(line)
    hanoi(n, 'A', 'B', 'C')

執行時間最久約為 0.1 s，使用記憶體最多約為 3.4 MB，通過測試。

import sys

def hanoi(n, i, src, aux, dst):  # 盤子數量 n，編號 i，來源 src，輔助 aux，目標 dst
    if n == 1:  # 遞迴出口
        print(f"Move ring {i:d} from {src:s} to {dst:s}")
        return  # 結束遞迴
    hanoi(n-1, 1, src, dst, aux)  # 遞迴，盤子數量 n-1，編號 1，盤子由 src 移動到 aux
    hanoi(1, n, src, aux, dst)  # 遞迴，盤子數量 1，編號 n，盤子由 src 移動到 dst
    hanoi(n-1, 1, aux, src, dst)  # 遞迴，盤子數量 n-1，編號 1，盤子由 aux 移動到 dst

for line in sys.stdin:
    n = int(line)
    hanoi(n, 1, 'A', 'B', 'C')

### C++ 程式碼

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

#include <iostream>
using namespace std;

void hanoi(int n, char src, char aux, char dst) {
    if (n == 1)
        cout << "Move ring " << n << " from " << src << " to " << dst << "\n";
    else {
        hanoi(n-1, src, dst, aux);
        cout << "Move ring " << n << " from " << src << " to " << dst << "\n";
        hanoi(n-1, aux, src, dst);
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n;
    while(cin >> n) hanoi(n, 'A', 'B', 'C');
    return 0;
}

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

#include <iostream>
using namespace std;

void hanoi(int n, int i, char src, char aux, char dst) {
    if (n == 1) {
        cout << "Move ring " << i << " from " << src << " to " << dst << "\n";
        return;
    }
    hanoi(n-1, 1, src, dst, aux);
    hanoi(1, n, src, aux, dst);
    hanoi(n-1, 1, aux, src, dst);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n;
    while(cin >> n) hanoi(n, 1, 'A', 'B', 'C');
    return 0;
}

## [ZeroJudge: c296. 3定時K彈](https://zerojudge.tw/ShowProblem?problemid=c296)

以下的內容引用自另一篇講義〈[APCS實作題2016年10月第3題：定時K彈](https://hackmd.io/@yizhewang/HJlK7VrTj)〉

{%hackmd @yizhewang/HJlK7VrTj %}

------

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