算法入門

教學目的內容1

教學要求2

重點難點3

教學內容4教學目的通過本章的學習，可以對算法有個初步的認識（算法的特性，算法的優(yōu)劣），并且可以用三種以上的方法（自然語言、流程圖、偽代碼等）去描述算法。教學要求了解算法的特性；了解如何用自然語言描述算法

；了解如何用流程圖描述算法

；掌握如何用偽代碼描述算法；掌握用三種基本結構表示算法

；掌握N-S流程圖。重點難點重點：用三種基本結構表示算法

；

使用N-S流程圖；用偽代碼描述算法；教學內容算法的描述方法。算法的概念；算法的特性

；算法的好壞；算法的概念什么是算法？

算法是解決問題的方法和步驟，在生活中，大多數(shù)都能涉及到算法。如洗衣機的操作指南，一道菜譜等。還記得春晚的一個小品么，“把大象裝冰箱總共分幾步”。第一步，把冰箱門打開；第二步，把大象裝進去；第三步，把冰箱門蓋上。這三步就是把大象裝進冰箱的算法。

嚴格地說，算法是對特定問題求解步驟的一種描述，是指令的有限序列。一般的，一個問題的算法并不唯一，可能有很多種，一個給定的算法解決一個特定的問題。

算法的特性在計算機領域中，算法應具有以下特性

：（1）輸入

一個算法應有零個或多個輸入，輸入是在執(zhí)行算法時需要從外界取得必要的信息即算法所需的初始量等一些信息。（2）輸出

一個算法有一個或多個輸出，編寫程序的目的就是要得到一個結果，輸出就是算法最終所求的結果。

（3）有窮性

一個算法必須在執(zhí)行有窮步之后結束且每一步都可在有窮時間內完成，不能無限的執(zhí)行下去。例如要編寫一個由小到大整數(shù)累加的程序，這時候要注意一定要設一個整數(shù)的最上限，也就是加到那個數(shù)為止，若沒有這個最上限，那么程序將無終止的運行下去，也就是常說的死循環(huán)。

算法的特性

（4）確定性

算法的每一個步驟都應當是確切定義的，對于每一個過程不能有二義性，將要執(zhí)行的每個動作必須嚴格而清楚的規(guī)定。并且，在任何條件下，對于相同的輸入只能得到相同的輸出。

（5）可行性算法中的每一步都應當能有效的運行，也就是說算法應是可行的，并要求最終得到正確的結果。

算法的好壞針對一個問題可能會有不同的算法去解決，不同的算法思路不同，有的執(zhí)行起來就會很慢，效率就很低，有的就會很快，效率自然會很高。這樣，就出現(xiàn)了算法的“好”與“壞”之分，如何衡量一個算法的好壞，通常要從以下幾個方面來分析：（1）正確性算法能滿足具體問題的需求，即對任何合法的輸入算法都會得出正確的結果。

（2）可讀性算法創(chuàng)建后由人來閱讀、理解、使用以及修改。所以可讀性的好壞直接影響到算法的好壞。如果一個算法涉及的想法很多，人就會糊涂，那么這個算法就不能更好的交流和推廣使用，自然對修改、擴展、維護就更不方便。所以要提高算法的可讀性，讓其簡明易懂。（3）健壯性一個程序完成后，運行該程序的用戶對程序的理解各有不同，并不能保證每一個人都能按照要求進行輸入，健壯性就是指對非法輸入的抵抗能力，當輸入的數(shù)據(jù)非法時，算法能識別并做出處理，而不會因為輸入的錯誤產生錯誤動作或造成癱瘓。

算法的好壞（4）時間復雜度與空間復雜度時間復雜度簡單的說就是算法運行所需要的時間。不同的算法具有不同的時間復雜度，當一個程序較小時感覺不到時間復雜度的重要性，當一個程序特別大時便會察覺到時間復雜度實際上是十分重要的。所以如何寫出更高速的算法一直是算法不斷改進的目標?？臻g復雜度是指算法運行所需的存儲空間的多少，隨著計算機硬件的發(fā)展，空間復雜度已經顯得不再那么重要。算法的描述方法算法設計者必須將自己設計的算法清楚的、正確的按步驟記錄下來，這個過程就叫描述算法。為了讓算法清晰易懂，需要選擇一種良好的描述方法，算法的描述方法有很多，其中常用的有自然語言，流程圖，N-S流程圖等。一.自然語言自然語言就是日常生活中的語言，一般描述一些簡單問題步驟可以通俗易懂。下面通過具體實例來介紹自然語言。例任意輸入三個數(shù)，求這三個數(shù)中的最大數(shù)。第一步：定義四個變量分別為x、y、z以及max。第二步：輸入大小不同的三個數(shù)分別賦給x、y、z。第三步：判斷x是否大于y，如果大于，則將x的值賦給max，否則將y的值賦給max。第四步：判斷max是否大于z，如果大于，則執(zhí)行步驟五，否則將z的值賦給max。第五步：將max的值輸出。

算法的描述方法

二.流程圖

流程圖是一種傳統(tǒng)的算法表示法，它用一些圖框來代表各種不同性質的操作，用流程線來指示算法的執(zhí)行方向。首先介紹一下流程圖符號：

算法的描述方法例求兩個整數(shù)a和b的最大公約數(shù)。流程圖如下：

算法的描述方法三.三種基本結構1.順序結構順序結構是最簡單的線性結構，在順序結構的程序里，各操作是按照他們出現(xiàn)的先后順序執(zhí)行的。如圖：

圖1圖22.選擇結構

選擇結構也叫分支結構，有兩種形式，如圖1和圖2：

算法的描述方法3.循環(huán)結構循環(huán)結構又稱作重復結構，反復執(zhí)行某一部分的操作，直到不滿足條件時才終止循環(huán)。按照判斷條件出現(xiàn)的位置劃分，可將循環(huán)結構分為當型（while）循環(huán)和直到型（until）循環(huán)。

（1）當型循環(huán)

當型循環(huán)是先判斷條件P是否成立，如果成立，則執(zhí)行A框，執(zhí)行完A框后，再判斷條件P是否成立，如果成立，接著再執(zhí)行A框，如此反復，直到條件P不成立為止，此時不執(zhí)行A框，跳出循環(huán)。當型循環(huán)如圖：算法的描述方法（2）直到型循環(huán)直到型循環(huán)是先執(zhí)行A框，然后再判斷條件P是否成立，如果條件P成立則再執(zhí)行A，然后再判斷條件P是否成立，如果成立，接著再執(zhí)行A框，如此反復，直到條件P不成立，此時不執(zhí)行A框，跳出循環(huán)。直到型循環(huán)如圖：實例求1到100之間（包括1和100）所有整數(shù)之和。用當型循環(huán)流程圖如3.11所示。用直到型循環(huán)流程圖如所示。

算法的描述方法

圖3

圖4算法的描述方法

四.N-S流程圖N-S流程圖，又叫盒圖，是算法的一種結構化描述方法，同樣也有三種基本結構。下面分別介紹：（1）順序結構的N-S流程圖（2）選擇結構的N-S流程圖（3）當型循環(huán)的N-S流程圖

（4）直到型循環(huán)的N-S流程圖算法的描述方法五.偽代碼

偽代碼是介于自然語言和計算機語言之間的文字和符號來描述算法。它采用某一程序設計語言的基本語法，如操作指令可以結合自然語言來設計。而且，它不用符號，書寫方便，沒有固定的語法和格式，具有很大的隨意性，便于向程序過渡。

例用偽代碼描述n!開始如果n=0，輸出s=1;如果n>0,