語言開發(fā)入門及項(xiàng)目實(shí)戰(zhàn)課件章算法

算法入門

教學(xué)目的內(nèi)容1

教學(xué)要求2

重點(diǎn)難點(diǎn)3

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

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

；掌握如何用偽代碼描述算法；掌握用三種基本結(jié)構(gòu)表示算法

；掌握N-S流程圖。重點(diǎn)難點(diǎn)重點(diǎn)：用三種基本結(jié)構(gòu)表示算法

；

使用N-S流程圖；用偽代碼描述算法；教學(xué)內(nèi)容算法的描述方法。算法的概念；算法的特性

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

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

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

算法的特性在計(jì)算機(jī)領(lǐng)域中，算法應(yīng)具有以下特性

：（1）輸入

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

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

（3）有窮性

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

算法的特性

（4）確定性

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

（5）可行性算法中的每一步都應(yīng)當(dāng)能有效的運(yùn)行，也就是說算法應(yīng)是可行的，并要求最終得到正確的結(jié)果。

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

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

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

算法的描述方法

二.流程圖

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

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

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

圖1圖22.選擇結(jié)構(gòu)

選擇結(jié)構(gòu)也叫分支結(jié)構(gòu)，有兩種形式，如圖1和圖2：

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

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

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

算法的描述方法

圖3

圖4算法的描述方法

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

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

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

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