小狐狸事務所: 演算法

顯示具有 演算法 標籤的文章。顯示所有文章

2024年11月3日星期日

博客來買書 1 本 : 演算法圖解原理 x Python實作 x 創意應用王者歸來(四版)

今天在陳南宗大神臉書看到推介洪老師下面這本書 66 折好書 (今日限定) :

# 演算法圖解原理 x Python實作 x 創意應用王者歸來(四版) $

小七至興店取貨免運 514 元.

2021年12月29日星期三

Python 學習筆記 : 串列元素的排序

排序是演算法課程的 ABC, 在 Python 的容器物件中, 不可變的字串與元組 (tuple) 內容無法排序 (因為排序會改變元素的順序); 無序的字典 (dict) 與集合 (set) 當然也無法排序, 只有串列 (list) 可以排序. 本篇是最近複習串列排序時的測試紀錄, 參考書籍 :

# Python零基礎入門班 : 一次打好程式設計與邏輯訓練基本功!

# Python最強入門邁向數據科學之路：王者歸來(全彩印刷第二版)

要對串列物件之內容排序有如下兩種方式 :

使用串列的 sort() 與 reverse() 方法 : 會直接改變原串列內元素的排序
使用內建函式 sorted() : 傳回排序後的新串列 (不影響原串列)

1. 使用串列的 sort() 與 reverse() 方法排序與倒序 :

呼叫 sort() 方法預設會將串列的元素值由小到大排列 (升冪), 如果是字串元素則依據其 Unicode 編碼排序, 如果要將元素值由大到小排列 (降冪), 則可傳入參數 reverse=True, 語法如下 :

list_obj.sort([key=None, reverse=False])

另外, 與串列元素順序有關的還有 reverse() 方法, 但它並不是將元素值由大到小降冪排序, 而是前軍做後軍, 後軍做前軍, 前後順序顛倒而已 (倒序), 嚴格來說不是排序, 語法如下 :

list_obj.reverse()

注意, reverse() 沒有任何參數. 順帶一提, reverse() 的倒序操作也可以用切片 [::-1] 來達成, 但[::-1] 與呼叫 reverse() 不同的是它不會改變原串列, 而是傳回倒序後的新串列, 例如 :

>>> lot=[2, 34, 16, 7, 18, 27]

>>> new_lot=lot[::-1]

>>> new_lot

[27, 18, 7, 16, 34, 2]

>>> lot

[2, 34, 16, 7, 18, 27]

>>> lot.reverse()

>>> lot

[27, 18, 7, 16, 34, 2]

sort() 方法有兩個備選參數, 其中 key 是在排序時要對每個元素呼叫的關鍵函式, 而 reverse 則是用來設定是要升冪或降冪排序 (預設是升冪), 例如 :

>>> lot=[2, 34, 16, 7, 18, 27]

>>> lot.sort() # 預設升冪排序

>>> lot

[2, 7, 16, 18, 27, 34]

>>> lot=[2, 34, 16, 7, 18, 27]

>>> lot.sort(reverse=True) # 指定降冪排序

>>> lot

[34, 27, 18, 16, 7, 2]

>>> lot=[2, 34, 16, 7, 18, 27]

>>> lot.reverse() # 倒序排列

>>> lot

[27, 18, 7, 16, 34, 2]

元素若是字串則按照每一個字元的 Unicode 編碼值大小逐一比對排序, 可用內建函式 ord() 查詢字元的 Unicode 編碼值, 例如 :

>>> string=['cC', 'aA', 'bB', 'Aa', 'Cc', 'Bb']

>>> string.sort()

>>> string

['Aa', 'Bb', 'Cc', 'aA', 'bB', 'cC']

>>> ord('A')

>>> ord('a')

>>> ord('B')

>>> ord('b')

可見 sort() 會依序從第一個字元開始一一比對 Unicode 編碼, 由於大寫字母的 Unicode 編碼比小寫的要小, 因此會排在前面. 任何語言的字串也是依據其 Unicode 編碼排序, 例如 :

>>> list_obj=['a', '我', '我們', '愛', 'abc', '你']

>>> list_obj.sort()

>>> list_obj

['a', 'abc', '你', '愛', '我', '我們']

>>> ord('我')

25105

>>> ord('愛')

24859

>>> ord('你')

20320

因為 '你' 的 Unicode 比 '愛' 的 Unicode 小, 所以你' 排在 '愛' 的前面.

布林值串列也可以排序, 它是按照 Ture 與 False 相對應的整數值 1 與 0 去排序, 因此 False 會排在最前面, 例如 :

>>> list_obj=[True, True, False, True, False]

>>> list_obj.sort()

>>> list_obj

[False, False, True, True, True] # False 的值為 0, True 為 1, 故 False 排在前面

注意, 串列元素必須都是同類型資料才能呼叫 sort(), 否則會出現 TypeError 錯誤, 具體而言就是元素中有數值與字串混合情況的串列無法排序, 但布林值可以跟數值一起排序, 因為布林值其實就是 0 與 1 兩個整數. 而 reverse() 只是倒序操作而已, 並不涉及元素排序, 因此混合型態的串列呼叫 reverse() 是可以的, 例如 :

>> list_obj=['abc', 123]

>>> list_obj.sort() # 數值與字串混合的串列不可呼叫 sort()

Traceback (most recent call last):

File "<pyshell>", line 1, in <module>

TypeError: '<' not supported between instances of 'int' and 'str'

>>> list_obj.reverse() # 混合型態串列可以呼叫 reverse()

>>> list_obj

[123, 'abc']

>>> list_obj=['abc', True] # 字串與布林值為混合型態, 不可排序

>>> list_obj.sort()

Traceback (most recent call last):

File "<pyshell>", line 1, in <module>

TypeError: '<' not supported between instances of 'bool' and 'str'

>>> list_obj.reverse() # 混合型態串列可以呼叫 reverse()

>>> list_obj

[True, 'abc']

>>> list_obj=[3.14159, 123, True] # 布林值本質是整數, 與數值並非混合型態

>>> list_obj.sort()

>>> list_obj

[True, 3.14159, 123]

除了混合資料型態的串列無法呼叫 sort() 進行排序外, 複數串列也不行, 例如 :

>>> list_obj=[1+2j, 1+1j, 1-1j]

>>> list_obj.sort()

Traceback (most recent call last):

File "<pyshell>", line 1, in <module>

TypeError: '<' not supported between instances of 'complex' and 'complex'

2. 使用內建函式 sorted() 排序 :

內建函式 sorted() 會將傳入串列預設以升冪排序後傳會心串列 (傳入 reverse=True 則可降冪排序), 不會改變原串列, 語法如下 :

sorted(list_obj [, key=None, reverse=False])

備選參數的用法與 sort() 方法的一樣, 例如 :

>>> lot=[2, 34, 16, 7, 18, 27]

>>> sorted(lot) # 傳回升冪排序後的新串列

[2, 7, 16, 18, 27, 34]

>>> sorted(lot, reverse=True) # 傳回降冪排序後的新串列

[34, 27, 18, 16, 7, 2]

>>> lot # 原串列不變

[2, 34, 16, 7, 18, 27]

字串串列同樣是以 Unicode 編碼排序, 例如 :

>>> string=['cC', 'aA', 'bB', 'Aa', 'Cc', 'Bb']

>>> sorted(string) # 傳回升冪排序後的新串列

['Aa', 'Bb', 'Cc', 'aA', 'bB', 'cC']

>>> sorted(string, reverse=True) # 傳回降冪排序後的新串列

['cC', 'bB', 'aA', 'Cc', 'Bb', 'Aa']

>>> string # 原串列不變

['cC', 'aA', 'bB', 'Aa', 'Cc', 'Bb']

與 sort() 方法一樣, 數值與字串混合的串列, 以及複數串列都無法用 sorted() 排序, 例如 :

>>> list_obj=['abc', 123] # 數值與字串混合 : 無法排序

>>> sorted(list_obj)

Traceback (most recent call last):

File "<pyshell>", line 1, in <module>

TypeError: '<' not supported between instances of 'int' and 'str'

>>> list_obj=['abc', True]

>>> sorted(list_obj)

Traceback (most recent call last):

File "<pyshell>", line 1, in <module>

TypeError: '<' not supported between instances of 'bool' and 'str'

>>> list_obj=[1+2j, 1+1j, 1-1j] # 複數串列無法排序

>>> sorted(list_obj)

Traceback (most recent call last):

File "<pyshell>", line 1, in <module>

TypeError: '<' not supported between instances of 'complex' and 'complex'

參考 :

# Python List 的 sort 與 sorted 排序用法教學與範例

# Python List Sort Key

# Python List reverse()

2021年12月28日星期二

Python 學習筆記 : 在串列中搜尋資料

本篇主要是閱讀借自母校的幾本 Python 基礎書籍後所整理的搜尋測試紀錄, 參考書目 :

# Python零基礎入門班 : 一次打好程式設計與邏輯訓練基本功!

資料搜尋是序列型態常見的操作, 以下是 Python 中常用的搜尋方式 :

1. 使用 index() 方法搜尋 :

Python 的串列 (list) 與元組 (tuple) 物件都內建了 index() 方法, 傳入欲搜尋的元素會傳回該元素之索引, 但若該元素不存在則會出現 ValueError 錯誤, 例如 :

>>> lot=[2, 34, 16, 7, 18, 27]

>>> lot.index(34) # 元素存在傳回索引

>>> lot.index(27) # 元素存在傳回索引

>>> lot.index(6) # 元素不存在會出現錯誤

Traceback (most recent call last):

File "<pyshell>", line 1, in <module>

ValueError: 6 is not in list

故使用 index() 搜尋資料必須做例外處理, 例如 :

>>> lot=[2, 34, 16, 7, 18, 27]

>>> try:

print(f'index={lot.index(5)}')

except Exception: # 或 ValueError

print(f'not found!')

not found!

>>> try:

print(f'index={lot.index(27)}')

except Exception: # 或 ValueError

print(f'not found!')

index=5

可以將此搜尋功能寫成一個 search() 函式, 傳入序列物件與搜尋標的後會傳回索引 (有找到) 或 None (沒找到), 例如 :

>>> def search(series, target):

try:

index=series.index(target)

return index

except ValueError:

return None

>>> lot=[2, 34, 16, 7, 18, 27]

>>> search(lot, 27) # 有找到 : 傳回索引

>>> search(lot, 2) # 有找到 : 傳回索引

>>> if not search(lot, 21): # 沒找到 : 傳回 None

print('not found')

not found

2. 使用迴圈循序搜尋 :

此方法以迴圈從序列物件的開頭依序搜尋標的, 此法缺點是效率較差, 若標的是在序列的最尾端, 則花費的搜尋時間最多. 可將此程序寫成函式, 找到標的時傳回索引, 否則傳回 None, 例如 :

>>> def search(series, target):

index=None # 傳回索引初始值

for i in range(len(series)): # 以迴圈走訪序列中的元素

if series[i]==target: # 比對是否為找尋之標的

index=i # 找到就將傳回值設為目前索引

break # 中止搜尋

return index # 傳回索引或 None

>>> search(lot, 2) # 有找到 : 傳回索引

>>> search(lot, 27) # 有找到 : 傳回索引

>>> print(search(lot, 21)) # 沒找到 : 傳回 None

None

可見功能與上面用 index() 方法實作的一樣.

3. 使用二分搜尋法 :

二元搜尋法的對象必須是已排序 (從小至大) 的序列物件 (list 或 tuple), 它的搜尋作法是先將這由小到大排序的序列中間切開分成兩半, 左半部是較小的部分, 右半部是較大的部分. 然後將正中央的元素與搜尋標的比較, 如果相同就是找到了標的, 可結束搜尋; 否則就要看標的比正中央元素大還是小, 若是比正中央元素大, 那就到右半部繼續搜尋, 反之就到左半部繼續搜尋.

串列由小到大排序可用內建函式 sort(), 此函式會改變原本的串列內容, 例如 :

>>> lot=[2, 34, 16, 7, 18, 27]

>>> lot.sort()

>>> lot

[2, 7, 16, 18, 27, 34]

如果要自行實作排序, 可以使用最簡單的氣泡排序, 參考 :

# Python 學習筆記 : 排序之 (一) 氣泡排序

以下是寫成函式的氣泡排序 :

>>> def bubble_sort(arr):

for i in range(len(arr)-1, -1, -1):

for j in range(i):

if arr[j] > arr[j+1]:

arr[j], arr[j+1]=arr[j+1], arr[j]

>>> lot=[2, 34, 16, 7, 18, 27]

>>> bubble_sort(lot)

>>> lot

[2, 7, 16, 18, 27, 34]

排序好後就可以開始實作二元搜尋法, 寫成函式如下 :

>>> def binary_search(series, target):

index=None

min=0

max=len(series) - 1

cnt=0

while min <= max:

mid=int((min + max )/2)

cnt += 1

if series[mid]==target:

index=mid

break

elif series[mid]>target:

max=mid - 1

else:

min=mid + 1

return index

>>> lot=[2, 34, 16, 7, 18, 27]

>>> lot.sort()

>>> lot

[2, 7, 16, 18, 27, 34]

>>> binary_search(lot, 27)

>>> binary_search(lot, 7)

>>> binary_search(lot, 34)

>>> print(binary_search(lot, 21))

None

從程式碼長度來看, 似乎是用 index() 加上 try except 例外處理比較簡單.

2021年10月5日星期二

好書 : The Self-Taught Computer Scientist

今天看到一本 Willey 今年出版的演算法好書 :

# The Self-Taught Computer Scientist: The Beginner's Guide to Data Structures & Algorithms

Source : Wiley

此書使用 Python 語言來介紹演算法, 全書分成兩大部分, 第一部分為 Python 語法 (主要是 list, tuple, dic, set 等容器物件用法), 第二部分是資料結構與演算法 (鏈結串列, 堆疊, 佇列, 雜湊表, 排序, 搜尋, 圖等), 是一本自修 CS 內功的好書.

2020年4月10日星期五

Python 學習筆記 : 排序之 (一) 氣泡排序

程式語法熟練度是程式員的馬步功, 而演算法則是程式員的內功, 不學演算法只能算是花拳繡腿, 所以我打算有計畫地透過寫筆記徹底把 Python 演算法與資料結構基礎建立起來以備隨時查考.

演算法參考書籍如下 :

# 圖說演算法-使用 Python (博碩, 吳燦銘, 胡昭民)

# 動畫圖解資料結構使用Python (深石, 李春雄)

線上視頻教學參考 :

# Data Structures and Algorithms in JavaScript - Full Course for Beginners
# Data structures and algorithms with python

演算法第一課應該是寫程式最常用的排序吧! 本篇為排序中最好理解的的氣泡排序 (bubble sort), 此排序法目標是要將一個陣列的 n 個元素由小到大排列, 首先從陣列的第一個元素開始, 將其與相鄰的第二個元素比較大小, 若比第二個元素大就交換位置, 否則不做動作; 接著指標往下移到第二個元素, 繼續與下一個元素 (第三個) 相比.

如此這般依序往下比較, 當我們完成第一輪的 n-1 次比較時, 陣列中最大的元素必定會被移到陣列最後面. 但整個排序尚未完成, 我們還要將指標移回陣列之首再進行好幾輪同樣的比較, 但因為最大的元素已經在第一輪時被移到陣列尾端, 在第二輪比較時不需要再管它, 所以第二輪時只要比較前 n-1 個元素即可, 亦即要做 n-2 次比較, 完成第二輪比較時, 陣列中次大的元素必然被移到從陣列尾部倒數第二個元素.

這個程序每完成一輪, 下次掃描比較的個數就少一個, 直到需要被比較的元素只剩最前面那個時就可停止了, 那個元素必定是最小的, 因為這過程很像氣泡由水底往上升, 故稱為氣泡排序. n 個元素的陣列需經過 n-1 輪的掃瞄 (因為最後只剩第一個元素最小), 總共需要做 1+2+ ...+(n-1)=(n-1)*(1+n-1)/2=n*(n-1)/2 次比較, 整個演算法須使用兩層迴圈來做, 第一層為掃描之輪數, 第二層為每輪之比較次數, Python 程式碼如下 :

範例 1 : 氣泡排序 bubble_sort_1.py

#bubble_sort_1.py
arr=[99, 6, 7, 3, 78, 56, 72, 12]
print('陣列排序前 : ', arr)
n=0 #比較次數
for i in range(len(arr)-1, -1, -1): #掃描輪數=元素個數-1
for j in range(i): #掃描各輪內之元素
if arr[j] > arr[j+1]: #比大小
arr[j], arr[j+1]=arr[j+1], arr[j] #大於就互換位置
n += 1
print('第 %d 次排序結果 :' %(len(arr)-i), end='')
print(arr)
print('陣列排序後 : ', arr)
print('比較次數 : ', n)

執行結果 :

D:\test\python>python bubble_sort.py
陣列排序前 : [99, 6, 7, 3, 78, 56, 72, 12]
第 1 次排序結果 :[6, 7, 3, 78, 56, 72, 12, 99]
第 2 次排序結果 :[6, 3, 7, 56, 72, 12, 78, 99]
第 3 次排序結果 :[3, 6, 7, 56, 12, 72, 78, 99]
第 4 次排序結果 :[3, 6, 7, 12, 56, 72, 78, 99]
第 5 次排序結果 :[3, 6, 7, 12, 56, 72, 78, 99]
第 6 次排序結果 :[3, 6, 7, 12, 56, 72, 78, 99]
第 7 次排序結果 :[3, 6, 7, 12, 56, 72, 78, 99]
第 8 次排序結果 :[3, 6, 7, 12, 56, 72, 78, 99]
陣列排序後 : [3, 6, 7, 12, 56, 72, 78, 99]
比較次數 : 28

此陣列有 8 個元素, 故總比較次數 1+2+3+4+....+7=7*(1+7)/2=28 次.

如果串列元素是字串, 比大小時會以字元的 Unicode 編碼去比較, 將上面範例 1 改寫為函數, 然後傳入不同串列參數如下 :

範例 2 : 氣泡排序 bubble_sort_2.py

def bubble_sort(arr):
for i in range(len(arr)-1, -1, -1):
for j in range(i):
if arr[j] > arr[j+1]:
arr[j], arr[j+1]=arr[j+1], arr[j]
print('第 %d 次排序結果 :' %(len(arr)-i), end='')
print(arr)
return arr
arr=['f', 'e', 'd', 'c', 'b', 'a']
print('陣列排序前 : ', arr)
bubble_sort(arr)
print('陣列排序後 : ', arr)
arr=['我', '愛', '你']
print('陣列排序前 : ', arr)
bubble_sort(arr)
print('陣列排序後 : ', arr)

執行結果如下 :

D:\test\python>python bubble_sort_3.py
陣列排序前 : ['f', 'e', 'd', 'c', 'b', 'a']
第 1 次排序結果 :['e', 'd', 'c', 'b', 'a', 'f']
第 2 次排序結果 :['d', 'c', 'b', 'a', 'e', 'f']
第 3 次排序結果 :['c', 'b', 'a', 'd', 'e', 'f']
第 4 次排序結果 :['b', 'a', 'c', 'd', 'e', 'f']
第 5 次排序結果 :['a', 'b', 'c', 'd', 'e', 'f']
第 6 次排序結果 :['a', 'b', 'c', 'd', 'e', 'f']
陣列排序後 : ['a', 'b', 'c', 'd', 'e', 'f']
陣列排序前 : ['我', '愛', '你']
第 1 次排序結果 :['愛', '你', '我']
第 2 次排序結果 :['你', '愛', '我']
第 3 次排序結果 :['你', '愛', '我']
陣列排序後 : ['你', '愛', '我']

["我", "愛", "你"] 的 unicode 分別為 ['\u6211', '\u611b', '\u4f60'], '你' 的 unicode 值最小, '我' 最大, 因此排序後變成 ['你', '愛', '我'].

參考 :

# About Python's built in sort() method
# Python List 的 sort 與 sorted 排序用法教學與範例
# https://www.ifreesite.com/unicode-ascii-ansi.htm

2018年6月7日星期四

C 語言學習筆記 : 二元樹

今天看完 "動畫圖解資料結構第二版" 第六章的樹狀結構, 這本書真的很不錯, 以大量圖表扼要說明, 還有 CD-ROM 電子書輔助. 不過書中使用類似 Pascal 的虛擬語言來表示演算法, 而用六種程式語言實作的範例則是放在光碟裡.

此外, 我還參考了下列書籍 :

資料結構-使用 C 語言 (松崗, 陳會安)
圖說演算法-使用 C 語言 (博碩, 吳燦銘 & 胡昭民)
啊哈! 圖解演算法必學基礎 (碁峰, 紀磊)

樹狀結構主要有下列成分組成 :

樹根 (Root) : 最上層節點 (無父節點) 為根節點
節點 (Node) : 每一筆資料即為一個節點
葉節點 (Leaf Node) : 沒有子節點的節點, 即終端節點
子樹 (Subtree) : 節點以下與該節點相連的結構
樹林 (Forest) : 去除樹根後的結構稱為樹林

樹狀結構有三個主要參數 :

階度 (Level) : 節點在樹狀結構之階層位置, 樹根之階度為 1.
高度 (Height) : 樹的最高階度稱為高度.
分支度 (Degree) : 一個節點的子樹個數稱為其分支度. 二元樹節點分支度最多為 2.

樹 (Tree) 其實是圖 (Graph) 的一種特例, 它是一種無迴路 (loopless) 的無向圖, 常見的應用是家譜, 組織架構, 目錄, 或者是檔案總管的資料夾等等. 樹的特徵如下 :

任意兩節點僅有一條路徑.
N 個節點的樹剛好有 N-1 條邊

最常見的樹狀結構是二元樹, 摘要整理如下 :

一. 二元樹特徵 :

二元樹之每一節點分支度 (Degree) <= 2 (最多兩個子節點)
二元樹可以為空, 一般的樹不可為空且左右子樹無次序之分
非空二元樹具有根結點 (Root) 與左子樹和右子樹 (有次序之分)
二元樹最多只能有兩個子節點

二. 各種二元樹 :

斜曲二元樹 (skewed binary tree) :
只有左子樹之二元樹為左斜曲 (left-skewed), 而只有右子樹之二元樹為右斜曲 (left-skewed), 此種二元樹適合用鏈結串列實作, 不適合用一維陣列儲存, 因較浪費儲存空間.
嚴格二元樹 (strictly binary tree) :
若二元樹的每個非終端節點都有非空的左右子樹稱為嚴格二元樹, 亦即每個有子樹的節點不會只有一個子樹, 一定有兩個子樹 (要嘛沒有子節點, 要嘛有兩個子節點).
完滿二元樹 (strictly binary tree)
高度是 h 的二元樹, 若具有 2**h - 1 個節點, 稱為完滿二元樹, 亦即除最底下一層外, 每一節點均有兩個子節點. 完滿二元樹在第 k 階有 2**(k-1) 個節點.
完整二元樹 (complete binary tree)
高度是 h 的二元樹, 若節點不是葉節點, 一定有兩個子節點, 稱為完整二元樹. 其節點數 n 滿足 2**(h - 1) &lt b &lt= 2**h - 1 之條件.

可見, 完滿二元樹一定是嚴格二元樹; 也一定是完整二元樹; 但完整二元樹不一定是完滿二元樹, 但. 三者關係如下 :

嚴格二元樹 <= 完整二元樹 <= 完滿二元樹

三. 二元樹的資料結構 :

二元樹的資料結構可以使用鏈結串列 (linked list) 或一維陣列表示, 鏈結串列適合用來處理斜曲樹; 而陣列則適合處理完滿樹. 例如下面的三階二元樹, 最多有 2**3-1=7 個節點 (完滿), 因此可宣告一個 A[7] 陣列來儲存節點, 其中 A[0] 不使用, 空缺的節點填入特殊值 (例如 0) :

可見以一維陣列實作二元樹時, 節點與子節點之索引有如下關係 :

左子樹索引是其父節點索引的 2 倍
右子樹索引是其父節點索引的 2 倍加 1

利用這兩個規律即可在陣列中建立二元樹, 若加上下列規則, 則可建立二元搜尋樹 :

每個節點值不同
每個節點的值須大於左子樹之值, 小於右子樹之值
左右子樹也是二元樹

以 28, 23, 35, 41, 22, 23 這組資料為例, 其二元搜尋樹如下 :

五. 二元樹的走訪 :

以陣列表示的二元樹可用下列三種方式走訪 :

前序追蹤 (MLR)
中序追蹤 (LMR)
後序追蹤 (LRM)

其中 M 表示 Middle (樹根), L 表示 Left (左子樹), R 表示 Right (右子樹).

下面程式為改寫自 "動畫圖解資料結構第二版" 的完滿二元樹走訪 :

#include <stdio.h>
#include <stdlib.h>

#define Num 20

void CreateBinaryTree(int*, int);
void Postorder(int);
void Inorder(int);
void Preorder(int);

int data[Num]={0};
int BinaryTree[Num]={0};

int main(void) {
int n;
printf("請輸入節點個數：");
scanf("%d", &n);
printf("請輸入這 %d 個節點的內容：\n", n);
for (int i=0; i<n; i++) {
scanf(" %d", &data[i]);
}
CreateBinaryTree(data, n); //呼叫建立二元樹之副程式
printf("二元樹前序追蹤的結果：\n");
Preorder(1); //呼叫前序之副程式
printf("\n");
printf("二元樹中序追蹤的結果：\n");
Inorder(1); //呼叫中序之副程式
printf("\n");
printf("二元樹後序追蹤的結果：\n");
Postorder(1); //呼叫後序之副程式
printf("\n");
system("PAUSE");
return 0;
}

void CreateBinaryTree(int data[], int n) { //建立二元樹
int node=1, temp;
for (int i=0; i<Num; i++) {BinaryTree[i]=0;} //初值設定
for (int i=0; i<n; i++) {
BinaryTree[node]=data[i];
node=node + 1;
}
}

void Postorder(int node) { //後序追蹤
if (BinaryTree[node] != 0) {
Postorder(2*node); //遞迴左子樹
Postorder(2*node+1); //遞迴右子樹
if (BinaryTree[node] != 0) { //列印樹根
printf("%d ",BinaryTree[node]);
}
}
}

void Inorder(int node) { //中序追蹤
if (BinaryTree[node] != 0) {
Inorder(2*node); //遞迴左子樹
if (BinaryTree[node] != 0) { //列印樹根
printf("%d ", BinaryTree[node]);
}
Inorder(2*node+1); //遞迴右子樹
}
}

void Preorder(int node) { //前序追蹤
if (BinaryTree[node]!=0) {
if (BinaryTree[node]!=0) {
printf("%d ",BinaryTree[node]); //列印樹根
}
Preorder(2*node); //遞迴左子樹
Preorder(2*node+1); //遞迴右子樹
}
}

執行結果如下 :

請輸入節點個數：9
請輸入這 9 個節點的內容：
38
78
10
65
19
86
33
72
29
二元樹前序追蹤的結果：
38 78 65 72 29 19 10 86 33
二元樹中序追蹤的結果：
72 65 29 78 19 38 86 10 33
二元樹後序追蹤的結果：
72 29 65 19 78 86 33 10 38
請按任意鍵繼續 . . .

--------------------------------
Process exited with return value 0
Press any key to continue . . .

四. 二元搜尋樹 :

上面的範例僅僅是將資料依序填入陣列中, 如果填入時加入如下規則, 所建立的二元樹稱為二元搜尋樹 :

每個節點值不同
每個節點的值須大於左子樹之值, 小於右子樹之值
左右子樹也是二元樹

範例程式如下 :

#include <stdio.h>
#include <string.h>

void CreateBTree(int btree[], int data[], int n) {
int i, j; //i=原始陣列索引, j=二元搜尋樹陣列索引
btree[1]=data[1]; //以第一個資料為二元樹根節點
for (i=2; i<=n; i++) { //從第二個資料開始拜訪原始陣列
j=1; //二元樹起始索引為根結點=1
while (btree[j] != 0) { //拜訪二元樹陣列直到找到空節點
if (data[i] > btree[j]) { //值較大往右子樹走
j=j*2 + 1; //右子樹節點索引
}
else {j=j*2;} //左子樹節點索引
} //找到二元樹空節點索引就跳出來
btree[j]=data[i]; //將原始陣列元素填入二元樹空節點
}
}

int main(void) {
int length=10;
int data[]={0,5,6,4,8,2,3,7,1,9}; //第一個索引用不到填 0
int btree[16]={0}; //預設 0 表示無任何節點
printf("原始陣列內容:\n");
for (int i=0; i<length; i++) { //顯示原始資料陣列內容
printf("[%d] : %d\n", i, data[i]);
}
printf("\n");
CreateBTree(btree, data, 9); //建立二元搜尋樹
printf("二元樹內容:\n");
for (int i=0; i<16; i++) { //顯示二元搜尋樹料陣列內容
printf("[%d] : %d\n", i, btree[i]);
}
printf("\n");
return 0;
}

執行結果如下 :

原始陣列內容:

[0] : 0

[1] : 5

[2] : 6

[3] : 4

[4] : 8

[5] : 2

[6] : 3

[7] : 7

[8] : 1

[9] : 9

二元樹內容:

[0] : 0

[1] : 5

[2] : 4

[3] : 6

[4] : 2

[5] : 0

[6] : 0

[7] : 8

[8] : 1

[9] : 3

[10] : 0

[11] : 0

[12] : 0

[13] : 0

[14] : 7

[15] : 9

--------------------------------
Process exited after 0.07975 seconds with return value 0
請按任意鍵繼續 . . .

2018年2月21日星期三

幾本物聯網與機器學習原文好書

最近在亞馬遜找到幾本非常棒的書如下 :

Algorithms For Dummies
此書以 Python 介紹演算法
Arduino Building exciting LED based projects and espionage devices
介紹家居自動化, 機器狗, 雲端監視系統等 DIY 專案
Arduino Interrupts Speed up your Arduino to be responsive to events
探討 Arduino 中斷之妙用
Bash Cookbook
Linux Bash Shell 好書
Beginning Artificial Intelligence with the Raspberry Pi (Good)
使用樹莓派與 Python 實作 AI 機器學習
Best Raspberry PI Zero Project For Home Automation
樹莓派 Zero 用於空拍機飛控
Building Smart Homes with Raspberry Pi Zero
使用 Pi Zero 建構智慧居家
Building a Quadcopter with Arduino
使用 Arduino 建構四旋翼機
Building Blockchain Projects

如果有中文譯本是最好 (簡繁均可) , 閱讀速度快; 沒有也 OK, 畢竟等翻譯可能要一年以上. 還不如直接看原文. 這裡面物聯網的東西比較好玩, 學習 ML 只是想讓物聯網更好玩而已.

2017年12月12日星期二

買實戰 R 語言預測分析 + 大數據時代的演算法

暑假時在母校高師大圖書館找到這本強國人游皓麟寫的 "R 語言預測實戰", 由於此書為數學系指定參考書無法預約, 故請圖書館幫我從燕巢調借過來, 但是只能借三天就必須還. 這本書博客來賣 474 元, 不過目前無存貨 :

# http://www.books.com.tw/products/CN11390085 $474

Source : 豆瓣

不過露天倒是買得到 :

# 【偉瀚程式04TL】全新現貨 R語言預測實戰兼具效率和價值的雙重屬性 $379+70
# 【wen2018】9787121298547 R語言預測實戰 $446+100

此書著重在預測演算法的 R 語言實作, 實用性很強. 這幾天看了一下手邊的 R 語言書籍, 想起這本書, 發現這本去年出版的書已經有繁體中文版, 但書名改為 "實戰R語言預測分析 (松崗 2017/11 出版)" :

Source : 誠品

打電話問明儀有現書, 由於昨晚公司系統切換加班今早補休, 於是中午就跑去買這本書, 原價 520 打 75 折是 390, 另外也買了 "大數據時代的演算法 (松崗, 2017/7 出版)", 原價 400 元打 75 折 300 元, 兩本合計 690, 反正昨晚有加班費, 揮霍一下買兩本書犒賞昨晚加班的辛勞, 呵呵.

2017年9月14日星期四

約瑟夫斯問題

前幾天去接二哥時問我是否聽過約瑟夫斯問題? 他說他們導師最近在思考如何用 C 來解題. 這我倒是第一次聽到這名詞, 回來一查才知道是演算法課題中的一道題目, 參考 :

# https://zh.wikipedia.org/wiki/约瑟夫斯问题
# 約瑟夫斯的問題
# 約瑟夫問題各種求解方式
# 約瑟夫問題遊戲設計與研究（Josephus）

匆匆看了說明還是不太懂, 有空再研究. 不過我倒是搜尋到 C 語言的解法 :

# 约瑟夫环问题(数组法)c语言实现

訂閱：文章 ( Atom )

小狐狸事務所

2024年11月3日星期日

博客來買書 1 本 : 演算法圖解原理 x Python實作 x 創意應用王者歸來(四版)

2021年12月29日星期三

Python 學習筆記 : 串列元素的排序

2021年12月28日星期二

Python 學習筆記 : 在串列中搜尋資料

2021年10月5日星期二

好書 : The Self-Taught Computer Scientist

2020年4月10日星期五

Python 學習筆記 : 排序之 (一) 氣泡排序

2018年6月7日星期四

C 語言學習筆記 : 二元樹

2018年2月21日星期三

幾本物聯網與機器學習原文好書

2017年12月12日星期二

買實戰 R 語言預測分析 + 大數據時代的演算法

2017年9月14日星期四

約瑟夫斯問題

文章標籤

常用連結

2024年11月3日 星期日

2021年12月29日 星期三

2021年12月28日 星期二

2021年10月5日 星期二

2020年4月10日 星期五

2018年6月7日 星期四

2018年2月21日 星期三

2017年12月12日 星期二

2017年9月14日 星期四

2024年11月3日星期日

2021年12月29日星期三

2021年12月28日星期二

2021年10月5日星期二

2020年4月10日星期五

2018年6月7日星期四

2018年2月21日星期三

2017年12月12日星期二

2017年9月14日星期四