《什麽是演算法》PPT课件.ppt

什麼是演算法？,演算法就是為了解決各種數學問題，而用的方法，只是解決某一個問題的方法很多種所以我們比較看誰的時間複雜度低。演算法代表一系列為達成某種目標而進行的工作，通常演算法裡的工作都是針對資料所做的某種處理。,什麼是演算法？,面對問題時會研擬出解決問題的步驟，在電腦領域中對於解決問題的方法稱為演算法。一組可以用來解決特定問題的有限指令或步驟，依循這些指令或步驟可以解決問題。演算法是達成一項特定工作的程序。,什麼是演算法？,“computer”,問題problem,演算法algorithm,輸入input,輸出output,至少一個,多個或是沒有,明確有限可實現有效率,學習演算法的問題,專有名詞不了解遇到這種情形,請翻開教科書找到這些專有名詞的地方,把它 K 懂並背下來,這是你這門科目要繼續往下走的先決條件。所使用的邏輯看不懂名詞看得懂,邏輯也了解,但不會用程式解問題,學習演算法的問題,專有名詞不懂所使用的邏輯看不懂請你先用人腦的方式去想像,程式這樣做,相當於人在解決這個問題時的什麼動作,電腦因為速度快,有時候會用一些看似愚蠢,但是完全沒有例外的方法做事,這就是演算法的精神-充分利用電腦的長處,它可以用比你笨一千倍的方法做得比你好,因為它比你快十億倍。名詞看得懂,邏輯也了解,但不會用程式解問題,學習演算法的問題,專有名詞不懂所使用的邏輯看不懂名詞看得懂,邏輯也了解,但不會用程式解問題這個就比較麻煩了,如果真心想學好程式設計(“程式設計=資料結構+演算法”),那就要多練習題目了。資料結構是演算法的基礎,程式寫不出來,大多數和想不出能讓演算法變單純的資料結構有關,請回過頭多磨練資料結構的知識吧。,演算法的特性,1.完整性：演算法中的每個程序都要能清楚地定義出來，不能有模糊不清的情況，只有要求每個程序都明確可行，整個演算法才是完整的。2.明確性：演算法中的程序代表的涵義須明確，任何人來解讀都能得到一致的結果。3.可決定性（Deterministic）：在明確而定義清楚的程序被執行後，演算法所達到的結果應該是可預期的，無法具備這種特性的程序的組合，並不能算是演算法。4.有限的（Finite）：演算法必須要能在有限的步驟內完成或終止，而且所使用的資料量也是有限的。,所以我們可以把它們看成是演算法的基本定義，滿足這些條件才算是演算法,演算法的其他特性,1.健全的結構：演算法最好具有易懂易用的特性，讓別人能很快地熟悉其用法，所以一般都會要求演算法有良好的結構，組成的元件有容易替代與再用的特性。2.一般通用性（Generality）：演算法最好能用來解決很多種問題，而不是只用在罕見的特例，既然花了功夫深入去描述一種演算法，自然會要求演算法具有多種用途。3.效率（Efficiency）：演算法使用時所耗用的系統資源狀況，以及執行的效率，對於使用者而言，是非常重要的問題。因為有時候不但要求解答，還得在有限時間之內完成。,演算法的表達,演算法的表達方式，我們可以把它看成是一種溝通的方法，到目前為止，並沒有那一種表示法是公認的標準，事實上也無此必要，一般人在描述演算法時必須講求精準明確，但不必遵循嚴謹的語法，不過，一旦要把演算法交付給電腦來執行時，當然就得十分地講究，因為電腦的邏輯與算術運算是完全依照所給的指令來進行的。,演算法表示,最簡單的表示法應該算是口語，或者說白話的講法，例如我們在判定某一年份是不是閏年時，會先看看能否被4整除，若是能被4整除但不能被100整除，可算是閏年，若是能被4整除，又能被100整除，但不能被400整除，則不能算閏年。像這一類的描述就很類似演算法，只是口語的表達方式有時候太繁複了，所以我們下面要介紹一些比較方便的表示法。,演算法表示方法,一、代數的表示法二、表格式的表示法例如申報所得稅時所用的累進稅表，從表格中的資訊可計算出應該繳的所得稅。三、資料流程圖四、控制流程圖五、類程式碼,閏年的判定問題,閏年和一般年份最大的差異在於閏年的二月份有29天，一般年的二月只有28天；能被400整除的年份一定是閏年。能被100整除但不能被400整除的，不是閏年。能被4整除但不能被100整除的年份是閏年。不能被4整除的年份不是閏年。,演算法表示方法,三、資料流程圖,演算法表示方法,四、控制流程圖,閏年的判定問題,閏年的判定問題,把閏年判定的問題同時分配給幾個人來求解，所得到的答案不見得和上圖一樣,同樣的問題可能有多種可行的演算法，這些演算法的效率和使用的資源各不相同。,類程式碼（Pseudocode）,它是一種很接近程式語言的演算法敘述，假如能把一個問題的解決方式用類程式碼來表達，就可以很容易的轉換成電腦能處理的指令。類程式碼和一般的程式語言不同，比較不遵循嚴謹的語法，但是在表達與溝通上相當地方便。,類程式碼（Pseudocode）,結合數學式子，敘述與程式控制結構語法可以採用任何語言為基礎以能明確表達出演算法為主(流程與運算)，對於宣告，輸入與輸出等不會要求像程式一樣明確定義,演算法結構,演算法中的操作在組合之後，顯示出來的架構；因為某些操作可能代表一個完整的功能，而演算法的整體功能就是這些個別功能的組合。,演算法設計,從問題的需求面開始，確定演算法應該提供的主要功能，然後看看這個功能可由那些次功能來完成，一步一步地把細節規劃出來，這種設計的方法叫做 由上而下的設計（Top-down design）,演算法設計,HW1,假設華氏與攝氏溫度的轉換公式可以用 C=(F-32)n(5/9)，試用DFD來表示。試使用虛擬碼撰寫閏年計算的演算法,