2022年12月3日 星期六

[演算法, algorithms, fChart,Python] 以 fChart 馭 Python:演算法(Algorithms)(10/11)

  以 fChart 馭 Python:

演算法(Algorithms)


Dec. 3, 2022
[1]

演算法為陳述問題解決(problem solving)的方法,在資訊科學(Computer Science,CS)領域裡,比較關心的是「用電腦」工具來解決問題。在圖1 的「10 大項目之 9」的 7 個實例(可從 https://reurl.cc/RXXDqr 下載)中將探討搜尋(search)排序(sorting)兩大古典問題

圖 1:10 大項目之 9

搜尋與排序問題

首先,我們先定義資料的搜尋與排列問題。給定一串數字資料:5, 7, 1, 1, 4, 3, 8

搜尋問題:找出 9 是否在這串資料中?(找不到)
排序問題:將這串資料由小到大遞增(ascending)排好?(1, 1, 3, 4, 5, 7, 8)
初學者可能會很納悶:這不是一眼就能看出答案的小事,怎麼需要如此的大陣仗的在此討論呢?(如果是一千萬筆大數據資料呢?)這其中的關鍵就在:人類的一眼看不等於電腦的看一眼!
再細部追問題:是否能把人類如何一眼望穿的步驟鉅細靡遺地列出來教會只懂 0101... 的笨電腦呢?
因此,如何定性的陳述一種搜尋/排序的方法就成為古典電腦科學家所關心的問題了。例如,在 Google 設計的搜尋引擎中,我們下達「泰布布」這個關鍵字後,Google 就會將之與從全網路上所爬(crawl)來的庫儲網頁做比對(搜尋)。然後依照它們的關聯性大小依序列出(排序)。所以,我們就能從圖 2 中找到筆者長期筆耕的部落格入口網址了。
 
圖 2:Google 搜尋引擎

原始問題

從圖 1 的 7 個實例中,我們各挑了循序搜尋(sequential search)選擇排序(selection sort)來說明以流程圖來表示將演算法後人工轉換到 Python 程式的過程。其中,前者的處理方法是依序「從到到尾」和原始資料比對要尋找的鍵值(key)https://reurl.cc/aaenZG);關於後者,每一回合都從尚未排序的資料中選出其值是最小的,並將之依序放到最左手邊以形成由小到大的資料遞增方式放置https://reurl.cc/x1N9NE)。

1. 09-01.循序搜尋法:在資料 [89, 34, 78, 45, 92] 中搜尋輸入的鍵值
2. 
09-05.選擇排序法:將資料 [12, 11, 10, 15, 1, 2] 以由小到大的遞增方式排列之

流程圖與 Python 語法對轉

1. 09-01.循序搜尋法:根據流程圖將 Python 程式轉換妥後以「09-01.循序搜尋法.py」存檔執行後就能看到如圖 3 所對應的執行結果。

圖 3:循序搜尋演算法

2. 09-05.選擇排序法根據流程圖將 Python 程式轉換妥後以「09-05.選擇排序法.py」存檔執行後就能看到如圖 4 所對應的執行結果。

圖 4:選擇排序演算法,資料以遞增方式排妥