克希荷夫定律與矩陣運算

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

原理

當電路上只有電池與電阻器，但又不是單純的串聯、並聯電路時，可以利用克希荷夫定律 (Kirchhoff's circuit laws) 求所有的分支電流。克希荷夫定律有兩個定則

1. 節點定則：對於電路上的某個節點而言，流入、流出的電流量值相等，實際上就是電荷守恆。
2. 迴路定則：對於電路上的某個迴路而言，繞一圈回到出發點時電位相等，實際上就是能量守恆。

下圖是 WikiPedia 克希荷夫定律英文版條目的例子

圖片來源：https://upload.wikimedia.org/wikipedia/commons/7/77/Kirshhoff-example.svg

由圖中右方的節點可得 $$ i_1 = i_2 + i_3 $$ 由上方的迴路可得 $$ \varepsilon_1 - i_1 R_1 - i_2 R_2 = 0 $$ 由下方的迴路可得 $$ -i_3 R_3 - \varepsilon_2 - \varepsilon_1 + i_2 R_2 = 0 $$ 整理以上3式可得 $$ \begin{cases} i_1 - i_2 - i_3 = 0 \\ i_1 R_1 - i_2 R_2 = \varepsilon_1 \\ i_2 R_2 - i_3 R_3 = \varepsilon_1 + \varepsilon_2 \end{cases} ~\Rightarrow~ \begin{cases} 1 \cdot i_1 + (-1) \cdot i_2 + (-1) \cdot i_3 = 0 \\ R_1 \cdot i_1 + (-R_2) \cdot i_2 + 0 \cdot i_3 = \varepsilon_1 \\ 0 \cdot i_1 + R_2 \cdot i_2 + (-R_3) \cdot i_3 = \varepsilon_1 + \varepsilon_2 \end{cases} $$ 如果轉換成矩陣型式 $$ \begin{bmatrix} 1 & -1 & -1 \\ R_1 & R_2 & 0 \\ 0 & R_2 & -R_3 \end{bmatrix} \begin{bmatrix} i_1 \\ i_2 \\ i_3 \end{bmatrix} = \begin{bmatrix} 0 \\ \varepsilon_1 \\ \varepsilon_1 + \varepsilon_2 \end{bmatrix} $$ 假設代入的數值分別為 $$ R_1 = 100 ~\mathrm{\Omega},~ R_2 = 200 ~\mathrm{\Omega},~ R_3 = 300 ~\mathrm{\Omega},~ \varepsilon_1 = 3 ~\mathrm{V},~ \varepsilon_2 = 4 ~\mathrm{V} $$ 電流分別為 $$ i_1 = \frac{1}{1100} ~\mathrm{A},~ i_2 = \frac{4}{275}~\mathrm{A},~ i_3 = -\frac{3}{220} ~\mathrm{A} $$

使用 Python 及 C++ 計算矩陣乘法、反矩陣

作者：王一哲
日期：2024年7月7日

前言

矩陣乘法及反矩陣的運算會出現在高中數學教材之中，同時也可以運用在物理課程之中，例如克希荷夫定律求分支電流。我之前都是直接用 NumPy 處理，為了更了解運算的過程，我再花了一些時間研究不使用 NumPy 的寫法。

矩陣乘法

運算原則

矩陣橫的部分為列 (row)、直的部分為欄 (column)，如果某個矩陣共有 $m$ 列、$n$ 欄，則這個矩陣的維度 (dimension) 為 $m \times n$。假設 $A$ 矩陣的維度為 $m \times n$，$B$ 矩陣的維度為 $n \times p$，則兩個矩陣相乘 $AB$ 的維度為 $m \times p$。如果兩個矩陣要相乘，第一個矩陣的欄與第二個矩陣的列數量必須相等。需要特別注意，矩陣乘法沒有交換性。 假設矩陣 $$ A = \begin{bmatrix} a_{0, 0} & a_{0, 1} & a_{0, 2} & \dots \\ a_{1, 0} & a_{1, 1} & a_{1, 2} & \dots \\ \vdots & \vdots & \vdots & \ddots \end{bmatrix} = \begin{bmatrix} A_1 & A_2 & \dots \end{bmatrix} $$ $$ B = \begin{bmatrix} b_{0, 0} & b_{0, 1} & b_{0, 2} & \dots \\ b_{1, 0} & b_{1, 1} & b_{1, 2} & \dots \\ \vdots & \vdots & \vdots & \ddots \end{bmatrix} = \begin{bmatrix} B_1 \\ B_2 \\ \vdots \end{bmatrix} $$ 相乘的結果 $$ AB = \begin{bmatrix} a_{0, 0} b_{0, 0} + a_{0, 1} b_{1, 0} + \dots & a_{0, 0} b_{0, 1} + a_{0, 1} b_{1, 1} + \dots & \dots \\ a_{1, 0} b_{0, 0} + a_{1, 1} b_{1, 0} + \dots & a_{1, 0} b_{1, 1} + a_{0, 1} b_{1, 1} + \dots & \dots \\ \vdots & \vdots & \ddots \end{bmatrix} = A_1 B_1 + A_2 B_2 + \dots $$

遞迴樹 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