演算法概論 電腦解題實作 國立豐原高中 郭再興

遇到問題 ? 了解問題、分析問題、解決問題 解決模式--輸入資料、資料處理、輸出結果 設計演算法--有限性、明確性、效率 使用流程圖、虛擬碼表達演算法的概念 電腦解題教學工具 機器人克服難關問題 機器人資源

引起動機 益智遊戲題目 問題一 過河問題 問題二 河內塔問題 問題三 猜數字遊戲 3

說明猜數字遊戲規則 思考如何解題 將討論的解題法畫成流程圖 討論此策略的優缺點 電腦顯示猜數字 Y 詢問使用者反應 結束 開始 使用者任選一個 0~100 之間的數字X 電腦顯示猜數字 Y 詢問使用者反應 Y太小 輸入”1” Y太大 輸入”2” X = Y 輸入”3” 調整 Y 大一些 調整 Y 小一些 猜對了 結束 說明猜數字遊戲規則 思考如何解題 將討論的解題法畫成流程圖 討論此策略的優缺點

演算法 演算法是解決問題每個步驟的細節與順序，可用圖表(流程圖)、文字(虛擬碼)表達 由有限個步驟所構成 連接各步驟的流程明確、每個步驟意義明確 開始執行後，經過有限步驟會達成目標

猜數字虛擬碼 X <= 出題、任選 0~ 100 之間的整數 Y <= 隨機猜一個數字 While (X< >Y) { If (X > Y) THEN 增加Y值 If (X < Y) THEN 減少Y值 } Display (“猜對了”)

應用流程圖 7

使用「流程圖」的優點 讓人容易了解整個作業流程。 使程式除錯的工作容易進行。 方便程式工作的移交。 有助於程式的修改與維護。

變數與資料型態 資料處理模式 電腦如何儲存資料? 變數與資料型態 成績處理程式練習 資料輸入 -> 處理 -> 資料輸出 平均 = (國+英+數+社)/4 加權平均=(國*3+英*3+數*2+社*2)/10

成績處理程式 ‘宣告變數 Dim A1, A2, A3, A4 as single ‘宣告變數 存放成績 Dim BB as single ‘宣告變數 存放平均成績 ‘輸入 A1 = 75 ‘輸入國文成績 A2 = 84 ‘輸入英文成績 A3 = 77 ‘輸入數學成績 A4 = 92 ‘輸入社會成績 ‘處理 BB = (A1 + A2 + A3 + A4)/4 ‘成績處理 ‘輸出 PRINT “平均成績 =” ; BB ‘輸出平均成績

陣列介紹 一維陣列 二維陣列 三維陣列

成績處理程式 ‘宣告變數 Dim A(5) as single ‘宣告變數 存放成績 Dim BB as single ‘宣告變數 存放平均成績 ‘輸入 A(1) = 75 ‘輸入國文成績 A(2) = 84 ‘輸入英文成績 A(3) = 77 ‘輸入數學成績 A(4) = 92 ‘輸入社會成績 ‘處理 BB = 0 FOR I=1 to 4 BB = BB + A(I) / 4 ‘成績處理 NEXT I ‘輸出 PRINT “平均成績 =” ; BB ‘輸出平均成績

資料結構 資料結構說明 常見資料結構概念

電腦解題教學工具 Game Maker (http://www.yoyogames.com/make) Scratch (http://scratch.mit.edu/) Alice (http://www.alice.org) 益智遊戲 可程式化機器人系統 Next

Game Maker

back

Scratch back

Alice back

可程式化機器人 back

機器人學習套件 Basic Stamp BoeBot (http://www.parallax.com) Basic Commander (http://innovati.com.tw) 科學魔法車 (http://www.me.tnu.edu.tw/~me017/welcome) Lego Mindstorms (http://mindstorms.lego.com) Arduino (http://www.arduino.cc) Microsoft Robotics Developer Studio (MSRDS) RobotBasic (http://www.robotbasic.org)

LEGO Mindstorms NXT 電機控制元件 控制器 伺服馬達 感測器 積木元件 圖控式程式發展環境

電機控制元件 包含NXT 控制器、伺服馬達、感應器等组成 NXT控制器就像人的大腦，伺服馬達好比人的肌肉，提供動力，感應器就像人的五官，偵測外界環境並轉換成數位資料，再傳送回NXT控制器，驅動伺服馬達做出反應 基本運算模式 輸入->處理->輸出 圖控式程式發展環境 back

back

LEGO Mindstorms NXT

選擇結構: 若按下按鈕責執行上半側的指令，反之則走下半側 迴圈結構 開始 物件屬性

程式虛擬碼 while(true) { if (touch_sensor_is_press) { beep(); show_picture_on_screen( ) } 感測器若被壓下，則由喇叭播放音效，螢幕也會顯示笑臉畫面，學生在此可學到基本程式撰寫方法，以及三種基本流程

車身組合

自走車 組合基本車身 前進後退 控制馬達後退一小段距離 控制馬達前近一小段距離 無窮迴圈

單光感循跡 挑戰問題:如何讓機器人使用一個光感應器， 控制兩個馬達，依循地上黑線前進 ?

單光感循跡演算法 演算法說明 step 1 光感應偵測地面亮度 step 2 若偵測到亮-左馬達出力 step 3 若偵測到暗-右馬達出力 不斷重複上面步驟，即可循跡前進

參考程式 右馬達停止 左馬達運轉 光感測到亮，則走上半側路徑控制馬達左轉；反之則走下半側控制馬達右轉 無窮迴圈 NXT 單光感循跡-0.mp4

演算法虛擬碼 while(true) { if (LightSensor_detect_white) { // 若光感測為亮 motorB_stop ( ); //右馬達停 motorC_run( ); //左馬達旋轉 } else { motorB_run( ); //右馬達旋轉 motorC_stop ( ); //左馬達停 }

進階挑戰地圖

討論 討論單光感循跡演算法的特性 優點 缺點 改進演算法 光感在線的左側(或右側)，程式也要更改 演算法簡單易懂 容易脫軌 效率不佳 不適合太複雜的路線… 改進演算法 NXT 掃描式單光感循跡.mp4 NXT 單光感循跡.mp4

雙光感循跡 挑戰問題:如何讓機器人使用2個光感應器， 控制兩個馬達，依循地上黑線前進，且到達底線時自動停止 ?

請同學思考如何利用第二個光感應器來循跡，同時還能判斷是否到達底線。 綜合學生的想法，教師解釋如何使用2個光感應器偵測地面的黑色膠帶，達到控制車子依循黑色膠帶前進的演算法 可能會有多種演算法

演算法二 右光感 左馬達 右馬達 左光感 NXT 雙光感循跡.mp4

while(true) { if (left_LightSensor_detect_white) if (right_LightSensor_detect_white) { motorC_run( ); motorB_run( ); } else { motorB_stop( ); } else motorC_stop( );

演算法一 無窮迴圈 若左光感測到亮 則左馬達旋轉； 反之則左馬達停止 若右光感測到亮 則右馬達旋轉； 反之則右馬達停止

while(true) { // 若左光感偵測到地面為亮 if (left_LightSensor_detect_white) motorC_run( ); //左馬達運轉 else motorC_stop( ); //左馬達停止 // 若右光感偵測到地面為亮 if (right_LightSensor_detect_white) motorB_run( ); //右馬達運轉 motorB_stop( ); //右馬達停止 }

進階挑戰 兩點之間折返跑 繞圈前進遇橫線停止 NXT 3光感循跡.flv

機器人學習套件 Basic Stamp BoeBot (http://www.parallax.com) Basic Commander (http://innovati.com.tw) 科學魔法車(http://www.me.tnu.edu.tw/~me017/welcome) Lego Mindstorms (http://mindstorms.lego.com) Arduino (http://www.arduino.cc) Microsoft Robotics Developer Studio (MSRDS) Robot Simulator (http://www.robotsimulator.nl) Lego Mindstorms Simulator (http://ddi.uni-paderborn.de/index.php?L=1&id=4687) RobotBasic (http://www.robotbasic.org)

Basic Stamp BoeBot Basic Stamp 晶片 提供類似BASIC語法的程式發展環境 提供完整感測器模組 完整的自學手冊 支援MSRDS http://www.parallax.com BoeBot.mp4 back

Basic Commander 利基科技自行開發之控制板 軟體發展環境 innoBASIC 提供完整感測器模組 完整的自學手冊 http://www.innovati.com.tw Innobot with Sonar.mp4 back

科學魔法車 東南科技大學曹齊平老師 附有詳細實驗手冊 基本電學實驗 感測器電路實驗 自走車實驗 簡單適合初學者 科學魔法車bridge1.mpg back

Arduino 開放原始碼的電路圖設計，程式開發介面 提供類似Java,C語言的開發環境，可免費下載 可簡單地與感測器，各式各樣的電子元件連接(EX：紅外線,超音波,熱敏電阻,光敏電阻,伺服馬達,…等) 支援多樣的互動程式 ex: Flash、Max/Msp… 低價格的微處理控制器(ATMEGA8-16) USB介面，不需外接電源。另支援使用9VDC 可作為機器人的大腦，接收感測器的訊號，控制馬達動作 利用Arduino，突破以往只能使用滑鼠，鍵盤，CCD等輸入的裝置的互動內容，可以更簡單地達成單人或多人遊戲互動。 http://www.arduino.cc/ http://www.Arduino.TW Arduino 機器人.flv Audino Robot.mp4 back

Microsoft Robotics Developer Studio 微軟的機器人開發環境 Runtime Services (CCR, DSS) Visual Programming Language (VPL) Visual Simulation Environment (VSE) 更視覺化開發工具 更容易編寫程式與除錯 透過視窗或網頁介面控制機器人 利用 3D 模擬的方式實現機器人動作

介紹主題 介紹

MSRDS 啟動模擬畫面.wmv MSRS 模擬走迷宮影片.flv MSRS 模擬 KHR 影片.flv 介紹