2023年1月15日 星期日

[AI, Python, 深蹲, squat] Python 蹲的門面

 Python 蹲的門面

Line:ted2016.kpvs
Email:Lct4246@gmail.com
FBhttp://gg.gg/TedLeeFB/
Bloghttp://gg.gg/TedLeeBlog/

Jan. 15, 2023
[1]


在筆者的先前拙著《用變數傾印法玩 Python 蹲》(https://reurl.cc/LXk1qx)一文中,我們成功地在陳會安老師研發的 fChart 中的 Thonny IDE 測試了深蹲偵測及計次範例。本文將進一步地甞試以 fChart 內建的 Tinker 套件 [2] 為之再加上一套使用者介面(user interface,UI)來梳妝打扮一番


新增功能

在本文中,我們將為《用變數傾印法玩 Python 蹲》範例擴充下列兩個新功能:
  1.  改用攝影機即時取得的影像(而非事先預錄的影片)。
  2. 增設深蹲達標關卡(為了便於測試,暫訂為深蹲三下)。
 

UI 佈局(layout)

在圖 1 上方,我們設計了一個 3×2 大小的畫面,第一行顯示專案名稱(Python 蹲)與版次(V1.0),第二行顯示由攝影機取得的即時影像與相關訊息,第三行為留白及作者姓名(Ted Lee)。圖 1 下方為 Tinker 刻出來的畫面。

 
圖 1:UI 設計圖

在圖 2 中,我們先建立最外層的視窗 window 元件(component),再置入 frmTitle、frmVideo 和 frmTeam 三個框架元件(Frame)。緊接著,在 frmTitle 中擺放 lblTitle 和 lblVersion、在 frmVideo 中擺放 lblVideo 和 lblResult、在 frmTeam 中擺放 lblSpace 和 lblTeam。所有元件皆以 pack 佈局方式安排。詳如如圖 2 所示。

圖 2:UI 元件佈局

程式邏輯

我們將程式執行的流程畫成圖 3 的流程圖。此外,程式採模組化程式設計(modularized programming)的方法,將獨立的功能以下列三個副程式來達成:

  1. detectPose():偵測姿勢。
  2. updateUI():即時更新影像標籤 lblVideo。
  3. cleanUp():程式結束,釋放已配置資源(allocated resources)

圖 3:本文的流程圖

本文的執行結果請參考 https://youtu.be/Gm6o7m-QH6Y完整程式碼詳列如下(讀者亦可由 https://reurl.cc/rZ7aob 下載)。

import cv2
import numpy as np
from PIL import ImageFont, ImageDraw, Image
    
from tkinter import *
from PIL import Image, ImageTk

from PoseModule import PoseDetector
dir = 0 
count = 0

def updateUI():
    global img, lblVideo
    
    cv2image = cv2.cvtColor(img, cv2.COLOR_BGR2RGBA)
    img = Image.fromarray(cv2image)
    imgtk = ImageTk.PhotoImage(image = img)    

    lblVideo.imgtk = imgtk
    lblVideo.config(image = imgtk)
    lblVideo.after(100, detectPose)
    
    if count > 3:
       lblResult.config(text = '你已達標!')   
    
def detectPose():
    global cap, detector, dir, count, img

    success, img = cap.read()
    if success:
        img = cv2.resize(img, (640, 480))
        h, w, c = img.shape
        pose, img = detector.findPose(img, draw=True)
        
        if pose:
            lmList = pose["lmList"]
            angle, img = detector.findAngle(lmList[24], lmList[26], lmList[28], img)
            bar = np.interp(angle, (85, 180), (w//2-100, w//2+100))
            cv2.rectangle(img, (w//2-100, 50), (int(bar), 100), (0, 255, 0), cv2.FILLED)

            if angle <= 150:                
                if dir == 0:
                    count = count + 0.5
                    dir = 1
                    
            if angle >= 170: 
                if dir == 1:
                    count = count + 0.5
                    dir = 0
                    
            msg = str(int(count))        
            cv2.putText(img, msg, (100, 150), cv2.FONT_HERSHEY_SIMPLEX, 5, (255, 255, 255), 20)
            
        cv2.imshow("Pose", img)
        updateUI()

def cleanUp():
    window.destroy()
    cap.release()
    cv2.destroyAllWindows()

cap = cv2.VideoCapture(0) #####開啟攝影機
detector = PoseDetector()

#開 UI ---------------------------------------------------------------------------------------------------------   
#widow
window = Tk()
window.title('Python 蹲')
#window.geometry('1024x768')
window.attributes('-fullscreen', True)


#frame
frmTitle = Frame(window)
frmTitle.pack(side = TOP, fill = BOTH, expand = YES)

frmVideo = Frame(window)
frmVideo.pack(side = TOP, fill = BOTH, expand = YES)   

frmTeam = Frame(window)
frmTeam.pack(side = BOTTOM, fill = BOTH, expand = YES)


#Title
lblTitle = Label(frmTitle, text = "Python 蹲", fg = '#005E5E', bg = '#666666', font = ('標楷體', 70), borderwidth = 0, highlightthickness = 0, relief = "sunken") 
lblTitle.pack(side = LEFT, fill = BOTH, expand = YES)

lblVersion = Label(frmTitle, text = "V1.0", fg = '#005E5E', bg = '#666666', font = ('標楷體', 20), borderwidth = 0, highlightthickness = 0, relief = "sunken") 
lblVersion.pack(side = RIGHT, fill = BOTH, expand = YES)


#Video
lblVideo = Label(frmVideo, bg = '#005E5E', borderwidth = 0, highlightthickness = 0, relief = "ridge")
lblVideo.pack(side = LEFT, fill = BOTH, expand = YES)

lblResult = Label(frmVideo, text = "", fg = 'white', bg = '#005E5E', font = ('標楷體', 40), borderwidth = 0, highlightthickness = 0, relief = "sunken")
lblResult.pack(side = RIGHT, fill = BOTH, expand = YES)


#Team
lblSpace = Label(frmTeam, text = "", fg = '#005E5E', bg = '#666666', font = ('標楷體', 20), borderwidth = 0, highlightthickness = 0, relief = "sunken") 
lblSpace.pack(side = LEFT, fill = BOTH, expand = YES)

lblTeam = Label(frmTeam, text = "Ted Lee", fg = '#005E5E', bg = '#666666', font = ('標楷體', 20), borderwidth = 0, highlightthickness = 0, relief = "sunken") 
lblTeam.pack(side = RIGHT, fill = BOTH, expand = YES)

#姿勢識別 ---------------------------------------------------------------------------------------------------
detectPose()
    
window.bind('<Escape>', lambda e: cleanUp())
mainloop()


進階問題

  1. 建置一「分數雲端排行榜」來記錄玩家的深蹲分數。
  2. 修改程式,使得深蹲次數達標後出現是否「重新訓練」詢問。

[2] 請參考拙著《AI 成績查詢系統》(https://reurl.cc/aaWlKl)一文

2023年1月14日 星期六

[AI, Python, 深蹲, squat] 用變數傾印法玩 Python 蹲

用變數傾印法玩 Python 蹲

Line:ted2016.kpvs
Email:Lct4246@gmail.com
FBhttp://gg.gg/TedLeeFB/
Bloghttp://gg.gg/TedLeeBlog/

Jan. 14, 2023
[1]

本文將一門深入陳會安老師在 https://reurl.cc/mZ1mD1 分享的《看圖學Python人工智慧程式設計》(https://reurl.cc/rZW79r)一書中的範例。此範例使用了 Google  MediaPipehttps://reurl.cc/nZg8mX)跨平台機器學習解決方案,讓我們得以使用短短的 4x 行 Python 程式碼就能實現深蹲(squat)姿勢的判別並能計次。

會安老師說:「只要懂得程式語言三大結構(循序、選擇與重複),再了解一點 Python 程式語言的語法,就能開始玩 AI了!讀者們,Python 蹲、Python 蹲,Python 蹲完換你們蹲了喔!


開發環境建置

本文使用會安老師開發的 fChart 流程圖轉語法中的 Thonny IDE [2],它已裝妥了 CVZone 與 Tinker 套件。

下載 英文版「fChartThonny6_cvzone_en.zip可由 https://reurl.cc/gQ59Vb 下載。此外,深蹲範例程式的原始碼「Squat.zip」可由 https://reurl.cc/x1qzE5 下載。
解壓縮 將上述的兩支 .zip 檔解壓縮至磁機的」目錄(root directory)下(例如:c:\),如圖 1 所示。

 

圖 1:將「fChartThonny6_cvzone_en.zip」和「Squat.zip」解壓縮至 c:\

Thonny 雙撃「C:\fChartThonny6_cvzone_en\WinPython」路徑下的「thonny.vbs」以開啟 Thonny(圖 2)。

圖 2:開啟 Thonny IDE

Squat.py 在視窗左手邊的 Files 檔案管理中切換到「C:\Squat」後再雙撃「Squat.py」(圖 3)以載入原始碼(source code)

圖 3:在 Thonny 中開啟 Squat.py

程式碼追蹤

Squat.py 援用了「PoseModule.py」中的「PoseDetector」類別(class),並載入「squat3_clip.mp4」預錄的影像檔做為測試資料。 在 4x 行的程式碼中,最核心(core)的指令為第 17 行定義於的 PoseDetector 類別的 findAngle() 方法(method)!讀者們可先學習呼叫它的方法和需傳入的參數列(parameter list)。有需要再鑽進該類別去深究它是如何從影像資料中計算出深蹲的夾角的。
本小節將使用「變數傾印(dump)」暴力法(紮實的蹲馬步)將範例程式中插入「print(變數名)」,將用到變數一一印出來觀察其內容,藉以了解程式的設計邏輯。我們以
L行號 變數名稱
方式來標示查看程式碼的第幾行變數值。

L10 img 在第 10 和第 11 行中插入 print(img) 指令,我們可以看到變數 img 的第一筆內容如下:

[[[  0  44  37]
  [  2  50  43]
  [  7  63  54]
  ...
  [ 20  48  78]
  [ 19  47  77]
  [ 18  46  76]]

 [[  0  44  37]
  [  2  50  43]
  [  7  63  54]
  ...
  [ 18  46  76]
  [ 17  45  75]
  [ 16  44  74]]

 [[  0  45  37]
  [  0  51  43]
  [  4  62  53]
  ...
  [ 15  43  73]
  [ 12  40  70]
  [ 11  39  69]]

 ...

 [[121 115 110]
  [123 117 112]
  [127 121 116]
  ...
  [ 19  40  71]
  [ 22  43  74]
  [ 23  44  75]]

 [[144 138 133]
  [146 140 135]
  [152 146 141]
  ...
  [ 23  44  75]
  [ 23  44  75]
  [ 23  44  75]]

 [[153 147 142]
  [152 146 141]
  [152 146 141]
  ...
  [ 23  44  75]
  [ 21  42  73]
  [ 19  40  71]]]

圖 4:變數傾印法

L12 img 
[[[  1  47  40]
  [ 10  66  57]
  [ 12  70  61]
  ...
  [ 16  44  74]
  [ 20  48  78]
  [ 18  46  76]]

 [[  0  48  40]
  [  8  66  57]
  [  1  56  47]
  ...
  [ 16  44  74]
  [ 16  44  74]
  [ 13  41  71]]

 [[  1  50  42]
  [  8  66  57]
  [  5  61  52]
  ...
  [ 15  43  73]
  [ 13  41  71]
  [  9  37  67]]

 ...

 [[151 145 140]
  [143 137 132]
  [133 127 122]
  ...
  [ 15  36  67]
  [ 12  33  64]
  [ 15  36  67]]

 [[128 122 117]
  [135 129 124]
  [145 139 134]
  ...
  [ 17  38  69]
  [ 19  40  71]
  [ 23  44  75]]

 [[151 145 140]
  [153 147 142]
  [156 150 145]
  ...
  [ 22  43  74]
  [ 23  44  75]
  [ 21  42  73]]]

L13 h, w, c 「480 640 3」 color channel, 彩色圖片是3

L14 detector.findPose(img, draw=True) 
({'lmList': [[331, 126], [334, 121], [336, 121], [338, 121], [328, 121], [326, 121], [324, 121], [339, 124], [321, 124], [335, 133], [328, 132], [355, 164], [306, 163], [357, 213], [302, 210], [371, 198], [289, 200], [376, 194], [283, 193], [375, 190], [281, 190], [372, 191], [284, 192], [344, 253], [315, 254], [358, 328], [301, 332], [368, 399], [291, 400], [365, 407], [294, 410], [374, 422], [283, 423]], 'bbox': (282, 97, 97, 337), 'center': (330, 265)}, array([[[ 1, 47, 40],
[ 10, 66, 57],
[ 12, 70, 61],
...,
[ 16, 44, 74],
[ 20, 48, 78],
[ 18, 46, 76]],
[[ 0, 48, 40],
[ 8, 66, 57],
[ 1, 56, 47],
...,
[ 16, 44, 74],
[ 16, 44, 74],
[ 13, 41, 71]],
[[ 1, 50, 42],
[ 8, 66, 57],
[ 5, 61, 52],
...,
[ 15, 43, 73],
[ 13, 41, 71],
[ 9, 37, 67]],
...,
[[151, 145, 140],
[143, 137, 132],
[133, 127, 122],
...,
[ 15, 36, 67],
[ 12, 33, 64],
[ 15, 36, 67]],
[[128, 122, 117],
[135, 129, 124],
[145, 139, 134],
...,
[ 17, 38, 69],
[ 19, 40, 71],
[ 23, 44, 75]],
[[151, 145, 140],
[153, 147, 142],
[156, 150, 145],
...,
[ 22, 43, 74],
[ 23, 44, 75],
[ 21, 42, 73]]], dtype=uint8))

L14 pose 
{'lmList': [[331, 126], [334, 121], [336, 121], [338, 121], [328, 121], [326, 121], [324, 121], [339, 124], [322, 124], [335, 133], [328, 132], [355, 163], [306, 163], [357, 215], [299, 214], [371, 199], [289, 199], [376, 194], [283, 191], [376, 191], [281, 188], [374, 192], [283, 189], [344, 254], [316, 255], [358, 328], [301, 332], [368, 400], [291, 400], [365, 409], [294, 410], [374, 422], [283, 423]], 'bbox': (282, 97, 97, 337), 'center': (330, 265)}

L14 img 
[[[ 1 47 40]
[ 10 66 57]
[ 12 70 61]
...
[ 16 44 74]
[ 20 48 78]
[ 18 46 76]]
[[ 0 48 40]
[ 8 66 57]
[ 1 56 47]
...
[ 16 44 74]
[ 16 44 74]
[ 13 41 71]]
[[ 1 50 42]
[ 8 66 57]
[ 5 61 52]
...
[ 15 43 73]
[ 13 41 71]
[ 9 37 67]]
...
[[151 145 140]
[143 137 132]
[133 127 122]
...
[ 15 36 67]
[ 12 33 64]
[ 15 36 67]]
[[128 122 117]
[135 129 124]
[145 139 134]
...
[ 17 38 69]
[ 19 40 71]
[ 23 44 75]]
[[151 145 140]
[153 147 142]
[156 150 145]
...
[ 22 43 74]
[ 23 44 75]
[ 21 42 73]]]

L16 lmList 
[[331, 126], [334, 121], [336, 121], [338, 121], [328, 121], [326, 121], [324, 121], [339, 124], [322, 124], [335, 133], [328, 132], [355, 163], [306, 163], [357, 215], [299, 214], [371, 199], [289, 199], [376, 194], [283, 191], [376, 191], [281, 188], [374, 192], [283, 189], [344, 254], [316, 255], [358, 328], [301, 332], [368, 400], [291, 400], [365, 409], [294, 410], [374, 422], [283, 423]]

L17 detector.findAngle(lmList[24], lmList[26], lmList[28], img) 
[ 15, 36, 67],
[ 12, 33, 64],
[ 15, 36, 67]],
[[128, 121, 118],
[135, 128, 125],
[145, 138, 135],
...,
[ 17, 38, 69],
[ 19, 40, 71],
[ 23, 44, 75]],
[[151, 144, 141],
[153, 146, 143],
[156, 149, 146],
...,
[ 22, 43, 74],
[ 23, 44, 75],
[ 21, 42, 73]]], dtype=uint8))
(178.20385684750428, array([[[ 1, 47, 40],
[ 10, 66, 57],
[ 12, 70, 61],
...,
[ 16, 44, 74],
[ 20, 48, 78],
[ 18, 46, 76]],
[[ 0, 48, 40],
[ 8, 66, 57],
[ 1, 56, 47],
...,
[ 16, 44, 74],
[ 16, 44, 74],
[ 13, 41, 71]],
[[ 1, 50, 42],
[ 8, 66, 57],
[ 5, 61, 52],
...,
[ 15, 43, 73],
[ 13, 41, 71],
[ 9, 37, 67]],
...,
[[151, 144, 141],
[143, 136, 133],
[133, 126, 123],
...,
[ 15, 36, 67],
[ 12, 33, 64],
[ 15, 36, 67]],
[[128, 121, 118],
[135, 128, 125],
[145, 138, 135],
...,
[ 17, 38, 69],
[ 19, 40, 71],
[ 23, 44, 75]],
[[151, 144, 141],
[153, 146, 143],
[156, 149, 146],
...,
[ 22, 43, 74],
[ 23, 44, 75],
[ 21, 42, 73]]], dtype=uint8))

L17 angle 177.34243016028947

L17 img 
  [ 15  36  67]
  [ 12  33  64]
  [ 15  36  67]]

 [[128 122 117]
  [135 129 124]
  [145 139 134]
  ...
  [ 17  38  69]
  [ 19  40  71]
  [ 23  44  75]]

 [[151 145 140]
  [153 147 142]
  [156 150 145]
  ...
  [ 22  43  74]
  [ 23  44  75]
  [ 21  42  73]]]
[[[  1  47  40]
  [ 10  66  57]
  [ 12  70  61]
  ...
  [ 16  44  74]
  [ 20  48  78]
  [ 18  46  76]]

 [[  0  48  40]
  [  8  66  57]
  [  1  56  47]
  ...
  [ 16  44  74]
  [ 16  44  74]
  [ 13  41  71]]

 [[  1  50  42]
  [  8  66  57]
  [  5  61  52]
  ...
  [ 15  43  73]
  [ 13  41  71]
  [  9  37  67]]

 ...

 [[151 144 141]
  [143 136 133]
  [133 126 123]
  ...
  [ 15  36  67]
  [ 12  33  64]
  [ 15  36  67]]

 [[128 121 118]
  [135 128 125]
  [145 138 135]
  ...
  [ 17  38  69]
  [ 19  40  71]
  [ 23  44  75]]

 [[151 144 141]
  [153 146 143]
  [156 149 146]
  ...
  [ 22  43  74]
  [ 23  44  75]
  [ 21  42  73]]]

原理探討

從上小節一步一腳印地以土法煉綱的方式將程式中的每一個存放資料的變數印在 Thonny 的「互動環境(Shell)」中一一檢視。我們試圖以達文西的解剖術,一刀刀的拆解出基元後再拼湊出藏在程式碼背後的密碼──流程圖(flowchart)

本範例以右大腿和小腿間因直立/深蹲所造成的夾角(angle)變化來判斷動作的完成與否。角度計算函式 findAngle() (定義於 PoseModule.py 中)以「髖骨─膝蓋─腳踝」三點的座標計算之(圖 5):

蹲下, £ 105 
直立, ³ 170


 5深蹲動作的角度值範例判斷

另一方面,深蹲的判別及其次數計算方式為(圖 6):

dir = 0,站直,count <- count + 0.5(蹲半下)
dir = 1,蹲下,count <- count + 0.5(蹲半下)
其中,「<-」表示指定(assign),意即將符號右邊的值指定給左邊(將計次變數 count 加上蹲半下 0.5 後指定到 count 之中)。

圖 6:深蹲動作的判別及計次

因此,我們可以整理出程式的執行流程如圖 7 所示。

圖 7:本文的流程圖

進階問題

  1. 將「夾角」的偵測擴充到四足,讓程式可以判斷出四手腳的動作。
  2. 找一個運動的肢體變化過程,例如國標舞舞步,將深蹲改寫為「國標舞 AI 教練」。
  3. 請模仿我們先前拙著《AI 成績查詢系統》(https://reurl.cc/YdzLAX》一文,使用 fChart 內建的 Tinker 視窗設計工具包(GUI toolkit),替本文訂製一個使用者界面。
  4. 參考拙著《Python玩AI,你也可以 – 從CVZone入門吧!》(https://reurl.cc/AyZGkE),將測試資料置換成由攝影機餵入的即時(real-time)影像資料。

[2] https://reurl.cc/gQ59Vb 中的「fChart_CVZone工具」連結

2022年12月30日 星期五

[遞迴, Recursion, fChart, Python] 以 fChart 馭 Python:遞迴函數(Recursive Functions)(11/11)

 以 fChart 馭 Python:
遞迴函數(Recursive Functions)


Dec. 30, 2022
[1]

遞迴是程式自己呼叫自己的一種抽絲剝繭的解題計巧。
因為這類的大問題是由其相同型式(pattern)的小問題所疊代(iterate)而增長而成的。所以,當問題空間(problem space)降低至易於處理的小大(size)時,我們就很容易從小問題的答案再往上一層一層回溯(backtrack)組合出原大問題的解答。例如:欲求數列(sequence) 1, 1, 2, 3, 5, ... 的第 10 項為何數字,我們可以發現,這串數列好像有一個隱含的規律(implicit regularity)是:第 i 項是前兩項 (i-2), (i-1) 的和,當 i > 2 時。例如:5 = 3 + 2。
表 1 的「10 大項目之 10」的 4 個實例(可從 https://reurl.cc/bGbkqM 下載)中將探討電腦科學(Computer Science,CS)中這類的經典(classical)遞迴問題──

將大問題拆解(divide)為小問題,再將小問題的答案逐步組合(combine)為大問題的解答。前題:大問題和小問題具有相同的結構性(structure)
表 1:10 大項目之 10

遞迴分析

在本小節中,我們甞試使用運算思維(computational thinking)的法則來分析費式數列問題:
步驟 1:拆解(decomposition)。我們設計了表 2 的費氏數列空白觀察表(observation table)來推敲此數列的生成(generate)過程。其結果如表 3 所示。
 
表 2:空白觀察表

表 3:費氏數列前十項觀察表

步驟 2:模式辨別(pattern recognition)。從表 3 中,我們似乎可以看出 5 = 2 + 3,即
第 n 項的值為前兩項之和。
步驟 3:抽像化(abstraction)。根據以上的觀察,我們大膽的以圖 1 這個遞迴公式(recurrence formula)來猜測費氏數列的表現。註:讀者們可援用數學歸納法(athematical inducation)來證明它的正確性。

圖 1:費費數列的遞迴公式

步驟 4:演算法(algorithm)。根據圖 1 的公式,我們可以圖 2 的流程圖來表式費氏數列的演算方法。

圖 2:費式數列的流程圖

原始問題

本文只詳述「10-02.呼叫Fib函數」:請計算費氏數列(Fibnacci number)第六項的值,其他三例請讀者們自行練習

流程圖與 Python 語法對轉

首先,函數(function)的語法請參考前著「以 fChart 馭 Python:函數」(https://reurl.cc/aablVZ)一文。緊接著,從圖  中我們可以看到 Fib(n) = t1 + t2 = Fib(n - 1) + Fib(n - 2),n = 6。其中,

Fib(6)
= Fib(5) + Fib(4)
= [Fib(4) + Fib(3)] + Fib(4) = 2 * Fib(4) + Fib(3)
= 2 * [Fib(3) + Fib(2)] + Fib(2) + Fib(1) = 2 * Fib(3) + 3* Fib(2) + 1 = 2 * Fib(3) + 3 * 1 + 1 = 2 * Fib(3) + 4
= 2 * [Fib(2) + Fib(1)] + 4 = 2 * [1 + 1] + 4 = 8

遞迴程式的撰寫格式為:
def Fib(n):
    if (n <= 2):
        return (Fib(n - 1) + Fib(n - 2)
    else:
        return 1
數後,根據流程圖將 Python 程式轉換妥後以「10-02.呼叫Fib函數.py」存檔執行後就能看到如圖 3 所對應的執行結果。

圖 3:根據流程圖手動轉換為 Python 語法以求得 Fib(6) 之值

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:選擇排序演算法,資料以遞增方式排妥