粵教版高中信息算法和算法的描述市公開(kāi)課一等獎(jiǎng)?wù)n件省賽課獲獎(jiǎng)?wù)n件

高中信息技術(shù)

算法和算法描述1/232/23軟件、程序、算法軟件是包括程序有機(jī)集合體，程序是軟件必要元素。任何軟件都有可運(yùn)行程序，最少一種。算法就是程序靈魂，一種需要實(shí)現(xiàn)特定功能程序，實(shí)現(xiàn)它算法能夠有很多種，因此算法優(yōu)劣決定著程序好壞。3/23軟件、程序、算法之間關(guān)系軟件程序算法4/23算法練習(xí)1：渡河問(wèn)題：一種農(nóng)夫帶著一條狼、一只山羊和一籃蔬菜過(guò)河，但只有一條小船，并且每次只能讓農(nóng)夫帶同樣?xùn)|西過(guò)河。農(nóng)夫在場(chǎng)情況下一切相安無(wú)事，一旦農(nóng)夫不在，狼會(huì)吃羊，羊會(huì)吃蔬菜。問(wèn)農(nóng)夫如何處理過(guò)河問(wèn)題。5/23辦法河6/231、算法概念：

算法是在有限步驟內(nèi)求解某一問(wèn)題所使用一組定義明確規(guī)則，即用計(jì)算機(jī)求解某一問(wèn)題辦法，是能被機(jī)械地執(zhí)行動(dòng)作或指令有窮集合。特性：1）有零個(gè)或多種輸入。解題算法中能夠沒(méi)有數(shù)據(jù)輸入，也能夠同步輸入多

個(gè)需要算法輸入數(shù)據(jù)。2）確定性。解題辦法中任何一種操作步驟都是清楚無(wú)誤，不會(huì)讓人產(chǎn)生

歧義或誤解。3）有窮性。任何一種提出解題辦法都是在有限操作步驟內(nèi)能夠完成，哪怕是失敗解題辦法。一種算法在執(zhí)行有窮步之后必須結(jié)束。4）有一種或多種輸出。一種算法執(zhí)行結(jié)束后必須有數(shù)據(jù)處理成果輸出，哪

怕是輸犯錯(cuò)誤輸出成果，沒(méi)有輸出算法是毫無(wú)意義。5）能行性。解題辦法中任何一種操作步驟在現(xiàn)有計(jì)算機(jī)軟硬件條件下和邏

輯思維中都能夠?qū)嵭袑?shí)現(xiàn)。7/23輾轉(zhuǎn)相除法：又名歐幾里得算法，是求兩個(gè)正整數(shù)之最大條約數(shù)算法。它是已知最古老算法，其可追溯至前323年。它初次出現(xiàn)于歐幾里得《幾何原本》中，而在中國(guó)則能夠追溯至東漢出現(xiàn)《九章算術(shù)》。它并不需要把二數(shù)作質(zhì)因數(shù)分解。列1：求112和64最大條約數(shù)！1、算法淵源列2：求8192和3072最大條約數(shù)！問(wèn)題1：什么是最大條約數(shù)？問(wèn)題2：什么是最小公倍數(shù)？8/23輾轉(zhuǎn)相除法：又名歐幾里得算法，是求兩個(gè)正整數(shù)之最大條約數(shù)算法。它是已知最古老算法，其可追溯至前323年。它初次出現(xiàn)于歐幾里得《幾何原本》中，而在中國(guó)則能夠追溯至東漢出現(xiàn)《九章算術(shù)》。它并不需要把二數(shù)作質(zhì)因數(shù)分解。詳細(xì)操作：1、m÷n，令r為所得余數(shù)（0≤r<b），若r=0，n即為最大條約數(shù)，輸出n,

算法結(jié)束;不然，繼續(xù)步驟2。2、交換：置m=n，n=r，并返回第一步。

1）112除以64，余數(shù)為（

）；

2）（

）除以（

）余數(shù)為（）；

3）（）除以（

）余數(shù)為（）。答：112和64最大條約數(shù)為（）。4864481601648161、算法淵源例：求112和64最大條約數(shù)，算法如下：9/232、算法描述

表達(dá)算法語(yǔ)言有自然語(yǔ)言、流程圖、偽代碼等。用自然語(yǔ)言描述輾轉(zhuǎn)相除法：1）輸入m和n值；2）令r等于m除以n余數(shù)；3）假如r=0，則輸出n值；不然令m=n，n=r返回第2步；4）結(jié)束。自然語(yǔ)言：是人們?nèi)粘Ｋ谜Z(yǔ)言，如漢語(yǔ)、英語(yǔ)、德語(yǔ)等，使用這些語(yǔ)言不用專門(mén)訓(xùn)練，所描述算法也通俗易懂。10/23流程圖：使用流程圖描述算法，讓人感到算法流程描述清楚簡(jiǎn)潔，容易體現(xiàn)選擇構(gòu)造；它不依賴于任何詳細(xì)計(jì)算機(jī)和計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言，從而有助于不一樣環(huán)境程序設(shè)計(jì)。圖形名稱功能開(kāi)始/結(jié)束框表達(dá)算法開(kāi)始或結(jié)束輸入/輸出框表達(dá)算法中變量輸入或輸出處理框表達(dá)算法中變量計(jì)算與賦值判斷框表達(dá)算法中條件判斷流程線表達(dá)算法中流向連接點(diǎn)表達(dá)算法中連接2、算法描述表1流程圖基本圖形及其功能11/23開(kāi)始輸入正整數(shù)m和nr=m除以n余數(shù)r=0?輸出n值結(jié)束m=n，n=r是否圖1用流程圖表達(dá)輾轉(zhuǎn)相除法12/23偽代碼：是用介于自然語(yǔ)言和計(jì)算機(jī)語(yǔ)言之間文字和符號(hào)來(lái)描述算法工具。它不使用圖形符號(hào)，因此，書(shū)寫(xiě)方便，格式緊湊，易于理解，便于向計(jì)算機(jī)程序語(yǔ)言過(guò)渡。用偽代碼描述輾轉(zhuǎn)相除法：輸入m和n值r等于mmodndowhiler<>0m=nn=rr=mmodnLoop輸出n值2、算法描述13/23表2三種算法描述方式優(yōu)劣算法描述方式長(zhǎng)處缺陷自然語(yǔ)言不需要專門(mén)訓(xùn)練，通俗易懂歧義性、語(yǔ)句長(zhǎng)、循環(huán)和分支較多時(shí)難以清楚表達(dá)、不便翻譯成計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言流程圖描述清楚簡(jiǎn)潔，容易體現(xiàn)選擇構(gòu)造，利于不一樣環(huán)境程序設(shè)計(jì)無(wú)法被計(jì)算機(jī)直接接收進(jìn)行操作偽代碼書(shū)寫(xiě)方便，格式緊湊，易于理解，便于向計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言過(guò)渡種類繁多，語(yǔ)句不容易規(guī)范14/23在利用計(jì)算機(jī)程序處理問(wèn)題過(guò)程中，算法設(shè)計(jì)有著舉足輕重地位和作用，算法是程序設(shè)計(jì)關(guān)鍵，是程序設(shè)計(jì)靈魂。算法好壞，直接影響著程序通用性和有效性，影響著問(wèn)題處理效率。程序編制依賴于算法設(shè)計(jì)，程序效率主要取決于算法效率。3、算法地位15/23算法練習(xí)2：雞兔同籠問(wèn)題

一種籠子里有雞和兔，目前只懂得里面一共有35個(gè)頭，94只腳，雞和兔各有多少只？設(shè)計(jì)一種求解算法，并用自然語(yǔ)言和流程圖描述出來(lái)。16/23程序與程序設(shè)計(jì)語(yǔ)言17/231、定義：

程序是一組機(jī)器操作指令或語(yǔ)句序列，是算法一種描述。2、特性：1）每一種算法步驟對(duì)應(yīng)著程序設(shè)計(jì)語(yǔ)言一種或多種語(yǔ)句，每

個(gè)語(yǔ)句對(duì)應(yīng)著一種或多種操作，每個(gè)操作都要求有執(zhí)行對(duì)象，

并且根據(jù)對(duì)象狀態(tài)變化形成動(dòng)態(tài)效果，同步可變對(duì)象用變

量來(lái)表達(dá)，變量值變化則可通過(guò)基本操作賦值來(lái)完成。2）除非尤其申明，程序都從第一條語(yǔ)句開(kāi)始次序執(zhí)行。3）總是施行操作于某些對(duì)象，這些對(duì)象一般稱為數(shù)據(jù)。4）數(shù)據(jù)一般應(yīng)當(dāng)有屬性和取值范圍，即類型說(shuō)明。5）有時(shí)語(yǔ)句要求執(zhí)行者作出判定，即在某種條件成立情況下執(zhí)

行一條或一組語(yǔ)句，不然執(zhí)行另一條或另一組語(yǔ)句。6）一條或一組語(yǔ)句也許需要執(zhí)行一次以上，當(dāng)一條或一組語(yǔ)句要

反復(fù)時(shí)，必須指明反復(fù)次數(shù)或反復(fù)條件。7）程序本身是一種靜態(tài)實(shí)體，而執(zhí)行語(yǔ)句進(jìn)程是動(dòng)態(tài)。一、程序18/233、程序基本構(gòu)造：次序構(gòu)造：各語(yǔ)句依次按照次序執(zhí)行。選擇構(gòu)造：通過(guò)檢查條件是否成立來(lái)決定做還是不做控件構(gòu)造。循環(huán)構(gòu)造：在一定條件下需要反復(fù)執(zhí)行控件構(gòu)造。S1S2……..SnS1CCS1S2任何復(fù)雜算法都能夠用次序構(gòu)造、選擇構(gòu)造、循環(huán)構(gòu)造三種基本構(gòu)造組合而成程序表達(dá)。19/23程序設(shè)計(jì)即是編寫(xiě)程序過(guò)程。一種高質(zhì)量程序，應(yīng)具有下列條件：1）建立正確數(shù)學(xué)模型和確定有效計(jì)算辦法；2）運(yùn)行成果必須正確，且在精度和其他各方面均滿足要求；3）程序本身具有良好構(gòu)造，邏輯清楚，易讀易懂；4）程序運(yùn)行時(shí)間盡也許短，同步盡也許合理地使用內(nèi)存；5）便于檢查、修正、移植和維護(hù)。二、程序設(shè)計(jì)20/23語(yǔ)言種類優(yōu)勢(shì)不足機(jī)器語(yǔ)言能被計(jì)算機(jī)直接接收和執(zhí)行程序設(shè)計(jì)任務(wù)繁重，效率低下，與自然語(yǔ)言存在巨大鴻溝，程序員不易培養(yǎng)。匯編語(yǔ)言比機(jī)器語(yǔ)言更易理解必須有語(yǔ)言翻譯器支持，效率低，匯編源程序較冗長(zhǎng)、復(fù)雜，容易犯錯(cuò)。高級(jí)語(yǔ)言更接近自然語(yǔ)言，移植性好要語(yǔ)言翻譯器支持表3三種語(yǔ)言優(yōu)缺陷21/23源代碼：以匯編語(yǔ)言或高級(jí)語(yǔ)言所編寫(xiě)程序被稱為“源代碼”，這些代碼需要我們逐一地輸入到計(jì)算機(jī)中，并把他們以文獻(xiàn)形式保存起來(lái)，這個(gè)過(guò)程稱為程序編輯。保存文獻(xiàn)稱為“源文獻(xiàn)”。大多數(shù)源文獻(xiàn)都是以最簡(jiǎn)單文本形式進(jìn)行存放，和我們常見(jiàn).txt文獻(xiàn)沒(méi)有區(qū)分，只不過(guò)為了表白它是源文獻(xiàn)，一般會(huì)起不一樣擴(kuò)展名。三、程序編輯和翻譯22/23高級(jí)語(yǔ)言翻譯程序有兩種類型：編譯程序和