演算法与程式语言.ppt

1,2,演算法與程式語言,高深、專業,難以親近,3,一、以電腦解決問題的方法,4,1、我們用電腦做什麼？,5,事先將事情交代給電腦(輸入電腦)，然後才讓電腦逐一完成，透過電腦的處理，便能達到解決問題的目的。,成績單,6,文書處理、播放影音動畫、玩遊戲等等，屬於應用層面的功能，即這些功能已經被設計好了。 預測未來的天氣 在數十萬人口資料中搜尋特定人物等等,7,為能指揮電腦解決這些問題，工程師得費心想出解決的方法，並轉換成電腦能懂的語言付諸實行。 在電腦科學中將這個解決方法稱為演算法。,8,2、程式是什麼？,電腦可以為我們解決許多問題：功課表的製作、行事歷的安排、瀏覽網路到聲光效果的遊戲娛樂等 這些並不是將電腦零件裝好就能做到的！,9,10,電腦必須接受我們給予的命令(Commamd)，才能執行命令所交代的事情，而這些命令的集合，我們就稱之為【程式】(Program)。,11,電腦依據指令行事,12,人們交辦什麼電腦就執行什麼，因為電腦無法自己變更或更改程式，而程式執行的結果，則是早就被預期得到的。,13,3、什麼時候要寫程式？,遭遇問題,寫程式,14,為了特定的目的的時候。如：簡單的數學公式計算程式、企業內部管理程式等等。 設計網頁互動程式的時候。如：動態網站、存取網站資料庫程式等等。 自己需要的程式，市面上的套裝軟體沒有的時候。如：自己的CD唱片整理程式等等。,15,通常解決問題的程式，可能有很多方法，並不侷限在單一的設計方法。,需求,程式,程式方法1,程式方法2,程式方法3,16,4、以電腦程式解決問題的過程,以往人們總以為記憶大量的程式語法、指令，然後再將程式一一輸入電腦才稱之為程式設計； 其實，撰寫程式只是解決問題當中的一個步驟，程式只是扮演著工具的角色。,17,假設：要利用電腦記錄全班各年度的考試成績、通訊錄等資料。,18,利用電腦程式解決問題的過程,思考問題,設計演算法,b,撰寫程式,測試程式與除錯,d,撰寫程式文件,19,a.思考問題,台北,高雄,20,思考問題時要先預見問題，找出可能或即將發生的問題。,21,b.設計演算法,台北,高雄,22,確定問題需求與解決方案後，接著便可以開始延伸擴展方案，設計解決問題的步驟。 簡單問題只需幾步即可解決，較為複雜的就得利用結構及判斷來描述，例如：如果則等判斷語句，或是重複直到為止等重複語句。,23,c.撰寫程式,確定演算法無誤後，便可挑選一個比較合適此方案的程式語言，並依據演算法與步驟流程，逐一將單純的文字描述，轉化為電腦裡的程式。,24,10 整理行李 20 搭車去火車站 30 排除買票 40 到月台搭車 50 從火車去高雄,將演算法寫成看得懂的程式,25,d.測試程式與除錯(Debug),程式設計所需考慮的變因很多，即使演算法正確也不能保證程式在執行時一定不會出錯。 因此測試時，除了找出程式中錯誤的語法外，還須能理出邏輯上發生的錯誤。 如：要輸入火車票價，卻意外多輸了一個0，那在計算票價時就會出錯。,26,e.撰寫程式文件,撰寫好程式的使用文件，或是注意事項，類似軟體使用手冊。 這些文件除了可讓使用程式的人，知道此程式有哪些功能、使用方法外，還可以作為開發程式時的修改依據。 與程式裡的註解不同，程式文件可視為程式開發歷程的說明與簡述。,27,1、思考問題,4、撰寫程式文件,2、設計演算法,5、測試程式與除錯,3、撰寫程式,28,二、演算法,電腦是依據安排好的步驟逐一執行，所以對其所下達的命令必須是電腦所了解的，而不能是：“給我列印課程表”、“計算學生成績總分”、“統計平均分數”等人類口語的命令。,29,利用電腦解決問題，必須事先將問題拆解成許多關鍵的步驟，且分配其先後順序，將這些拆解出來的小步驟逐一完成後，問題便解決了，當中描述問題解決的方法，稱為【演算法】。,30,1、認識演算法,演算法(Algorithm) 描述問題解決的方法 問題：到唱片行購買一張歌手專輯，有什麼步驟？,31,進入唱片行,找到所要購買的專輯CD,拿到櫃台結賬,Step4,將CD防盜線圈消磁,離開唱片行,32,進入唱片行,找到所要購買的專輯CD,拿到櫃台結賬,Step5,將CD防盜線圈消磁,離開唱片行,33,進入唱片行,找到所要購買的專輯CD,拿到櫃台結賬,離開唱片行,Step3,將CD防盜線圈消磁,34,韋氏字典裡所解釋的“演算法”是這樣的： 在有限的步驟內解決數學問題的程序,35,演算法五項特徵,準確描述的輸入(Input) 這些輸入必須有清楚的資料型別，而且提供使用者精確的描述與輸入。如求最小公倍數，就必須輸入兩個自然數。 指令必須具有明確性及有效性 每個步驟必須很明確地指出該如何動作，不能為節省空間而將原本需多步驟的動作一筆帶過。,36,正確性 必須要能證明該演算法要吧正確地解決問題。 有限性 必須在有限的步驟內產生結果。 結果的描述和輸出 輸入正確的結果，以及輸出至何處。,37,2、演算法的表示,即是將解決問題的每一個步驟、重點，利用文字、圖形或是人們看得懂的語言表示出來。,c.虛擬碼法,b.流程圖法,a.文字描述法,38,a.文字描述法,用人們的自然語言來描述直接。,39,例如：計算三角形的面積。 Step1：輸入三角形的底、高的長度 Step2：代入公式計算三角形的面積 Step3：計算結果即為三角形的面積 嚴格來講Step2不符合明確性，因它並未說明三角形面積要如何運算。,輸入三角形的底A和高B 讓S(A*B)/2 運算結果S即為三角形的面積,40,b.流程圖法,利用各種符號表示程式的動作，用帶箭頭的直線代表它們進行的順序。 透過統一的標準圖形，使流程圖具有一的流通性。,41,42,範例：三人身高比比誰最高,開始,A高於B嗎？,A高於C嗎？,輸入三人身高 A/B/C,輸出A最高,輸出C最高,輸出B最高,結束,B高於C嗎？,是,否,是,否,否,是,43,以圖形表示的好處是圖形會比文字敘述更容易讓人理解和接受。,44,繪製流程圖的幾個基本原則： 流程圖中必須使用標準符號，讓流程圖便於閱讀、分析與修改； 文字須簡明扼要，且每個流程必須明確且確實可靠； 方向應自上而下，自左而右； 線條應避免太長或交叉。,45,c.虛擬碼法,用文字加程式語言來描述演算法的過程。,46,程式開始 輸入 學生成績 若 學生成績60 印出及格 否則 印出需要重修 結束判斷 程式結束,47,虛擬碼如同寫作一樣，但事實上是採用了程式語言的語法結構，同時省略其中細部的設定。,48,三、討論與實作,49,三、討論與實作,請試著設計一個簡單的販賣機演算法，該演算法的條件限制為： 當投入3元時，將購得一瓶紅茶。,50,接受投幣,1,判斷投幣數目是否大於3元，如果小於則跳至第3步，如果等於則跳至第5步，如果大於則跳至第4步,2,退幣並結束,3,退還多余硬幣，並跳至第5步,4,售出一瓶紅茶並結束,5,51,開始,投入硬幣,退幣,是否小於3,是否等於3,售出一瓶紅茶,退還多於硬幣,結束,是,否,是,否,