遞迴樹 Recursive Tree

定義

先由下往上畫出樹幹，如果深度為0時只有樹幹；如果深度加1，在樹幹頂端增加2根互相垂直的分枝，分枝的長度比樹幹短，以下的程式中設定為0.6倍。我原來是用 tkinter 寫的，但它的畫面原點在左上角，向右為 +x 軸、向下為 +y 軸，跟我平常慣用的座標不太一樣。今天晚上再改用 VPython 重寫，並發布在 GlowScript 網站上，網頁版連結在此。

Python 及 C++ 優先佇列 (priority queue)

作者：王一哲
日期：2023年12月31日

前言

優先佇列 (priority queue) 又稱為堆積佇列 (heap queue)，Python 及 C++ 都有對應的容器，不過 Python 會將最小值放在佇列最上面，而 C++ 預設則是將最大值放在佇列最上面。以下的程式碼測試版本為 Python 3.10.12 及 C++14。

Python 語法

如果要在 Python 中使用優先佇列，需要引入函式庫 heapq；如果是在 LeetCode 網站上解題，因為網站已經引入了 heapq，不需要自己引入 heapq。語法為

import heapq

由於 Python heapq 的特性，使用時可以將它視為串列，初始化一個 heap 時，語法通常為

h = []

將資料放入 heap

語法為

heapq.heappush(heap, 資料)

例如以下的程式碼

h = []
heapq.heappush(h, 3)  # h 的內容為 [3]
heapq.heappush(h, 1)  # h 的內容為 [1, 3]
heapq.heappush(h, 2)  # h 的內容為 [1, 3, 2]

C++ 呼叫自訂函式修改二維 array 及 vector

作者：王一哲
日期：2023年10月6日

前言

由於 Python 的自訂函式可以回傳 list，如果要呼叫自訂函式修改 list 的內容相當簡單，只要將 list 的內容重設為回傳值即可，例如以下的程式碼：

# 修改1維 list
def myfunc(a):
    a[2] = -1
    return a

def myprint(a):
    for i in range(len(a)):
        print(a[i], end=" " if i < len(a)-1 else "\n")

data = [1]*5  # 內容為 [1, 1, 1, 1, 1]
print("1D List")
myprint(data)
print("Modify 1D List")
data = myfunc(data)  # 內容變為 [1, 1, -1, 1, 1]
myprint(data)

# 修改2維 list
def myfunc(a):
    a[2][2] = -1
    return a

def myprint(a):
    for i in range(len(a)):
        for j in range(len(a[i])):
            print(a[i][j], end=" " if j < len(a[i])-1 else "\n")

data = [[1]*5 for _ in range(3)]  # 內容為 [[1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1]]
print("2D List")
myprint(data)
print("Modify 2D List")
data = myfunc(data)  # 內容變為 [[1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, -1, 1, 1]]
myprint(data)

但是 C++ 呼叫自訂函式時，無法回傳 array 或 vector，如果要使用自訂函式修改 array 或 vector 的內容，需要使用傳指標呼叫 (*) 或是 傳參考呼叫 (&)，以下是簡單的例子。

C++ algorithm 函式庫

作者：王一哲
日期：2023年8月24日

前言

C++ algorithm 函式庫中有許多好用的工具，例如排序用的 sort、反轉資料用的 reverse，在 APCS 及 能力競賽中都能使用 algorithm 函式庫，善用這些工具可以少寫很多程式碼。接下來的的程式碼中都省略了以下幾行

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

不會改變容器中元素的函式

all_of 測試範圍中是否所有的元素皆符合條件

語法為

all_of(起點位址, 終點位址, 條件);

測試範圍包含起點位址，不包含終點位址，如果範圍中所有的元素皆符合條件或是範圍中沒有任何元素回傳 1，如果有任何一個元素不符合條件回傳 0。例如以下的程式碼

bool isPositive (int n) {
    return n > 0;
}

int main() {
    vector<int> a = {1, 3, 5, -2, -4, -6};
    cout << all_of(a.begin(), a.end(), isPositive) << endl;  // 印出 0
    cout << all_of(a.begin(), a.end(), [](int x){return x > 0;}) << endl;  // 印出 0
    vector<int> b = {1, 3, 5, 2, 4, 6};
    cout << all_of(b.begin(), b.end(), [](int x){return x > 0;}) << endl;  // 印出 1
    vector<int> c;
    cout << all_of(c.begin(), c.end(), [](int x){return x > 0;}) << endl;  // 印出 1
    return 0;
}

any_of 測試範圍中是否有任何一個元素符合條件

語法為

any_of(起點位址, 終點位址, 條件);

測試範圍包含起點位址，不包含終點位址，如果範圍中任何一個元素符合條件回傳 1，如果所有元素皆不符合條件或是範圍中沒有任何元素回傳 0。例如以下的程式碼

bool isPositive (int n) {
    return n > 0;
}

int main() {
    vector<int> a = {1, 3, 5, -2, -4, -6};
    cout << any_of(a.begin(), a.end(), isPositive) << endl;  // 印出 1
    cout << any_of(a.begin(), a.end(), [](int x){return x > 0;}) << endl;  // 印出 1
    vector<int> b = {-1, -3, -5, -2, -4, -6};
    cout << any_of(b.begin(), b.end(), [](int x){return x > 0;}) << endl;  // 印出 0
    vector<int> c;
    cout << any_of(c.begin(), c.end(), [](int x){return x > 0;}) << endl;  // 印出 0
    return 0;
}

Python 及 C++ 集合 (set)

作者：王一哲
日期：2023年8月13日

前言

集合 (set) 的性質與陣列很像，但是集合中的資料不能重複。以下的程式碼測試版本為 Python 3.10.12 及 C++14。

Python Set

Python 預設的資料容器有串列 (list)、數組 (tuple)、字典 (dictionary)、集合 (set)，使用 set 不需要引入函式庫。集合中的資料不能重複、沒有排序，無法使用索引值存取、改變資料，但是可以移除或新增資料。

建立集合

語法有以下

名稱 = set()  # 産生空的集合，如果用 名稱 = {} 會産生空的字典
名稱 = {資料1, 資料2, 資料3, ...}  # 産生集合同時指定資料
名稱 = set(可迭代的資料)  # 由可迭代的資料産生集合

例如以下的程式碼

a = set()  # 産生空的集合 a
b = {1, 3, 5, 2, 4, 6}  # 産生集合 b，print 輸出為 {1, 2, 3, 4, 5, 6}
c = {1, -3, 5, -2, 4, 6}# 産生集合 c，print 輸出為 {1, 4, 5, 6, -3, -2}
# 由串列産生集合 d，print 輸出為 {1, 2, 3, 4, 5, 6}
mylist = [1, 3, 5, 2, 4, 6]
d = set(mylist)
# 由數組産生集合 f，print 輸出為 {1, 2, 3, 4, 5, 6}
mytuple = (1, 3, 5, 2, 4, 6)
f = set(mytuple)
# 由字典産生集合 g、h、k
mydict = {1: 3, 5: 2, 4: 6}
g = set(mydict)          # 預設由 key 産生集合，print 輸出為 {1, 4, 5}
h = set(mydict.keys())   # 由 key 産生集合，print 輸出為 {1, 4, 5}
k = set(mydict.values()) # 由 value 産生集合，print 輸出為 {2, 4, 6}
# 由字串産生集合 s
hello = "Hello World!"
s = set(hello) # 産生集合 s，print 輸出為 {'d', 'e', 'l', ' ', 'r', 'o', '!', 'W', 'H'}
# 産生內容為字元的集合 t，print 輸出為 {'c', 'A', 'C', 'a', 'b', 'B'}
t = {'a', 'A', 'c', 'C', 'b', 'B'}

使用 Python 讀取、寫入 ods 的套件 pyexcel-ods3

作者：王一哲
日期：2023年8月11日

前言

這幾天有一位大學的學長問到如何用 Python 寫 LibreOffice Calc 的巨集，但是目前網路上能找到的資料很少。後來學長想到另一個作法，不要寫巨集，只要用 Pythoon 程式從 ods 檔中讀取資料，在程式中處理完資料，再將資料寫入 ods 檔中，應該也能做到類似的效果。我在網路上找到一些套件，其中一個就是 pyexcel-ods3，經過測試後可以成功地讀取、寫入 ods 檔，以下是簡單的筆記。

安裝套件

如果只要處理 ods 檔，可以在命令列界面中輸入以下指令安裝套件

pip3 install pyexcel-ods3

如果還要處理其它格式的檔案，例如 xlsx，可以在命令列界面中輸入以下指令安裝套件

pip3 install pyexcel

由於處理資料時使用 NumPy ndarray 會比較方便，建議安裝 NumPy。

pip3 install numpy

雖然在以下的程式中會使用到 json 及 collections，但這兩個套件是預設的，不需要另外安裝。

基本語法

以下的程式碼中，假設已經引入函式庫

import pyexcel_ods3 as pe
import json
import numpy as np
from collections import OrderedDict

Python 及 C++ 由純文字檔輸入資料

作者：王一哲
日期：2023年8月8日

前言

在程式競賽及 APCS 檢定中，需要從標準輸入讀取測資，通常測資會是用空格分隔的純文字檔，而且經常沒有說明測資的行數，要一直讀取到檔案結尾 (end-of-file, EOF)，甚至每行的資料數量也不固定。假設純文字檔 data.txt 的內容為

1
2 3
4 5 6
7 8 9 10

以下是用 Python 及 C++ 從純文字檔讀取資料的方法。

Python 方法1：使用 sys.stdin

例如以下的程式碼

import sys

a = []  # 儲存資料用的空白串列 a

for line in sys.stdin:  # 如果 sys.stdin 有讀到資料，將資料儲存到字串 line，繼續執行 for 迴圈
    a.append(list(map(int, line.split())))     # 讀取用空格分隔的資料
    #a.append(list(map(int, line.split(',')))) # 讀取用逗號分隔的資料

print(a) # 印出串列 a

其中最難看懂的是第6行，因為 Python 經常把好幾毎個工具擠在同一行，解讀程式碼的原則為

1. 由最內層的括號向外、向左讀
2. 同層的括號內由左向右讀

第6行的功能是

1. line.split()：將字串 line 使用 split() 依照空格拆解成數個字串。
2. map(int, line.split())：將拆解後的字串用 map 轉換成整數 int。
3. list(...)：將轉換後的一串整數用 list 組成串列。
4. a.append(...)：將轉換後的串列用 append 加到串列 a 最後面，因此 a 是二維串列。

Python 字典 (dictionary) 及 C++ STL map

作者：王一哲
日期：2023年8月7日

前言

Python 的字典 (dictionary) 及 C++ STL map 非常相似，都是關聯式的容器，利用 key 值存取資料，以下是兩種的使用方法。

Python 字典 (dictionary)

建立字典

語法為

字典 = {key1: value1, key2: value2, ...}

key 的資料格式通常用是整數或字串，如果使用字串要在前後加上引號，單引號或雙引號皆可，只要有成對使用即可。key 不能重複，每個 key 會對應到一筆資料，資料可以是任意的格式。例如以下的程式碼，a 是以字串作為 key，資料為整數；b 的 key 與資料皆為整數。

a = {"A": 10, "B": 20, "C": 30, "D": 40, "E": 50}
b = {1: 10, 2: 20, 3: 30, 4: 40, 5: 50}

由已存在的資料作為 key 建立字典

語法為

字典 = dict.fromkeys(keys, value)

例如以下的程式碼，以數組 keys 的內容作為 key，所有的資料皆為 1。

keys = ('A', 'B', 'C', 'D', 'E')
b = dict.fromkeys(keys, 1)

讀取資料

語法為

字典[key]

例如以下的程式碼，如果想要讀取 a 當中 key 為 "A" 的資料，以及讀取 b 當中 key 為 1 的資料，語法為

a = {"A": 10, "B": 20, "C": 30, "D": 40, "E": 50}
b = {1: 10, 2: 20, 3: 30, 4: 40, 5: 50}
print(a["A"])  # 印出 10
print(b[1])    # 印出 10

但如果 key 不存在，會回傳錯誤訊息 keyError 並停止程式。
另一種語法為 get

字典.get(key, key不存在時的預設回傳值)

如果 key不存在時的預設回傳值可省略，如果沒有設定會回傳 None。例如以下的程式碼

a = {"A": 10, "B": 20, "C": 30, "D": 40, "E": 50}
tmp = a.get("A", -1)    # 回傳 10
tmp = a.pop("F", -1)    # key 不存在，回傳 -1
tmp = a.pop("F")        # key 不存在，回傳 None

C++ 陣列 array 及 STL vector

作者：王一哲
日期：2023年8月6日

傳統的陣列 array

C++ 傳統的陣列 array，可以用來儲存多筆相同格式的資料，儲存這些資料的記憶體位址是連續的，所以讀取資料時，是依據陣列開頭的記憶體位址再加上索引值，索引值由 0 開始。以下是關於 array 的基礎知識。

産生 array

可以使用所有內建的資料格式，例如 int、float、char、string，也可以使用自訂的資料格式，但是一個 array 當中所有的資料只能是同一種格式。語法通常有以下3種

資料格式 名稱[長度];
資料格式 名稱[長度] = {資料1, 資料2, 資料3, ...};
資料格式 名稱[長度] = {0};

1. 第一種：産生 array 時沒有指定資料內容，切記在讀取 array 前一定要填入資料，否則無法預測會讀到什麼數值。
2. 第二種：可以省略長度，編譯器會自動根據資料內容決定 array 的長度。
3. 第三種：産生指定長度、所有資料皆為 0 的 array。

int a[5];           // 長度為 5 的整數 array，沒有指定資料內容
int b[] = {0, 1, 2, 3, 4};  // 長度為 5 的整數 array，內容為 {0, 1, 2, 3, 4}
int c[5] = {0};     // 長度為 5 的整數 array，內容為 {0, 0, 0, 0, 0}
int d[5] = {1};     // 不好的寫法，長度為 5 的整數 array，內容為 {1, 0, 0, 0, 0}
int e[5] = {-1};    // 不好的寫法，長度為 5 的整數 array，內容為 {-1, 0, 0, 0, 0}
bool f[5] = {true}; // 不好的寫法，長度為 5 的整數 array，內容為 {1, 0, 0, 0, 0}
bool g[5] = {false};// 長度為 5 的整數 array，內容為 {0, 0, 0, 0, 0}
char alphabet[] = {'A', 'B', 'C', 'D', 'E'};// 長度為 5 的字元 array
string names[] = {"Albert", "Bob", "Conan", "David", "Ethan"};// 長度為 5 的字串 array

搭配 memset 設定 array 內容

如果想要使用 memset，需要先引入函式庫 cstring，語法為

memset(名稱, 0, sizeof(名稱));  // 將指定名稱的 array 資料全部設定為 0
memset(名稱, -1, sizeof(名稱)); // 將指定名稱的 array 資料全部設定為 -1

例如以下的程式碼

int a[5];
memset(a, 0, sizeof(f));  // 長度為 5 的整數 array，內容為 {0, 0, 0, 0, 0}
int b[5];
memset(b, -1, sizeof(f)); // 長度為 5 的整數 array，內容為 {-1, -1, -1, -1, -1}

Python 及 C++ 雙向佇列 (deque)

作者：王一哲
日期：2023年8月5日

前言

雙向佇列 (double-ended queue, deque) 的性質與佇列很像，但是可以從最前面或最後面填入、取出資料，可以涵蓋 queue 及 stack 的功能。以下是在 Python 及 C++ 的實作方法。

Python 方法1：引入 collections 函式庫中的 deque

要先引入函式庫，函式庫的官方說明書在此 class collections.deque。

from collections import deque

建立雙向佇列

語法為

雙向佇列名稱 = deque(資料, maxlen=長度)

如果不輸入資料，會先建立空的雙向佇列，之後再填入資料。maxlen 可以不加，預設值為 None，如果有設定 maxlen，當雙向佇列已滿且要從最後面填入新資料時，會將最前面的資料推出去；反之，當雙向佇列已滿且要從最前面填入新資料時，會將最後面的資料推出去。以下的程式碼會建立名稱為 q、資料為 [0, 1, 2]、maxlen 為3的雙向佇列。

q = deque([0, 1, 2], maxlen=3)

如果想要知道 q 的內容，只要用 print 就可以了

print(q)

輸出內容為

deque([0, 1, 2], maxlen=3)

從最前面填入資料

語法為

雙向佇列名稱.appendleft(資料)

當雙向佇列已滿且要從最前面填入新資料時，會將最後面的資料推出去，例如以下的程式碼

q = deque([0, 1, 2], maxlen=3)
q.appendleft(3)  # q 的內容變為 [3, 0, 1]

如果沒有限制雙向佇列最大長度，例如以下的程式碼

q = deque([0, 1, 2])
q.appendleft(3)  # q 的內容變為 [3, 0, 1, 2]

從最後面填入資料

語法為

雙向佇列名稱.append(資料)

當雙向佇列已滿且要從最後面填入新資料時，會將最前面的資料推出去，例如以下的程式碼

q = deque([0, 1, 2], maxlen=3)
q.append(3)  # q 的內容變為 [1, 2, 3]

如果沒有限制雙向佇列最大長度，例如以下的程式碼

q = deque([0, 1, 2])
q.append(3)  # q 的內容變為 [0, 1, 2, 3]