熱門文章

2023年12月31日 星期日

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]

2023年10月6日 星期五

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 的內容,需要使用傳指標呼叫 (*) 或是 傳參考呼叫 (&),以下是簡單的例子。


2023年8月24日 星期四

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;
}


2023年8月13日 星期日

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'}


2023年8月11日 星期五

使用 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


2023年8月8日 星期二

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 是二維串列。

2023年8月7日 星期一

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


2023年8月6日 星期日

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}


2023年8月5日 星期六

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]


2023年8月4日 星期五

Python 及 C++ 堆疊 (stack)

作者:王一哲
日期:2023年8月4日



前言


堆疊 (stack) 是一種 後進先出 (the last in is the first out, LIFO) 的資料格式,只能從最後面(最上面)填入資料,從最後面(最上面)取出資料,無法從堆疊中間存取資料,以下是在 Python 及 C++ 的實作方法。


Python 方法1:引入 queue 函式庫中的 LifoQueue


要先引入函式庫,函式庫的官方說明書在此 queue — A synchronized queue class,操作方式與 queue 基本上相同,可以參考另一篇文章〈Python 及 C++ 佇列 (queue)〉。
from queue import LifoQueue


建立堆疊


語法為
堆疊名稱 = LifoQueue(maxsize=長度)
maxsize 可以不加,預設值為 0;如果有設定 maxsize,當堆疊已滿且要填入新資料時,會回傳錯誤訊息 Full。以下的程式碼會建立名稱為 mystack、maxsize 為3的堆疊。
mystack = LifoQueue(maxsize=3)


填入資料


語法為
堆疊名稱.put(資料, block=布林, timeout=秒數)
block 可以不加,預設值為 True。timeout 可以不加,預設值為 None。
  1. 如果 block=True,當堆疊已滿且要填入新資料時,會先等待一段時間,當堆疊有空間時再填入資料,或是到達 timeout 設定的秒數時回傳錯誤訊息 Full,但如果沒有設定 timeout,程式就會停在這一行,不會執行後面的程式碼。
  2. 如果 block=False,當堆疊已滿且要填入新資料時,立刻回傳錯誤訊息 Full
延續前面的程式碼,可以試試看第5、6行程式碼執行時的差異。
mystack = LifoQueue(maxsize=3)
mystack.put(0)  # mystack 的內容為 [0]
mystack.put(1)  # mystack 的內容為 [0, 1]
mystack.put(2)  # mystack 的內容為 [0, 1, 2] 且已填滿
mystack.put(3, block=True, timeout=1)  # 等待 1 秒後回傳錯誤訊息 Full
#mystack.put(3, block=False)  # 立刻回傳錯誤訊息 Full