2.1算法的概念及描述（教學(xué)設(shè)計）年級高一年級授課時間課題2.1算法的概念及描述教學(xué)目標1.了解算法的概念與基本特征；2.了解算法描述方法及特點并能夠運用恰當(dāng)?shù)拿枋龇椒ū硎竞唵嗡惴ǎ?.能夠根據(jù)實際需要設(shè)計算法解決問題，提升利用信息技術(shù)學(xué)科素養(yǎng)；教學(xué)重難點重點：1.深刻理解算法的概念，能夠辨別概要方法與細化算法。2.理解算法的基本特征，能夠區(qū)分不符合算法特征的案例并加以修正。難點：能夠結(jié)合算法的概念及特征，為具體問題設(shè)計和描述算法。教學(xué)準備多媒體課件、多媒體教室教學(xué)過程教師活動學(xué)生活動新課導(dǎo)入一、課堂導(dǎo)入1.通過給同同學(xué)們展示農(nóng)夫過河游戲規(guī)則：一個農(nóng)夫帶著—只狼、一只羊和—棵白菜，身處河的南岸。他要把這些東西全部運到北岸。他面前只有一條小船，船只能容下他和—件物品，另外只有農(nóng)夫才能撐船。如果農(nóng)夫在場，則狼不能吃羊，羊不能吃白菜，否則狼會吃羊，羊會吃白菜，所以農(nóng)夫不能留下羊和白菜自己離開，也不能留下狼和羊自己離開，而狼不吃白菜。然后提出問題：請求出農(nóng)夫?qū)⑺械臇|西運過河的方案。待同學(xué)們思考后，播放農(nóng)夫過河的這一個視頻，然后將頻中所示的方法我們以文字的方式羅列出來，并提出這就是算法，從而引出本堂課的主題。新知講授一、算法的概念同學(xué)們還記得上期剛開學(xué)報道的場景吧？學(xué)校在校園入口處擺放“高一新生報到流程”示意圖。這個“高一新生報到流程”示意圖就是一個算法，該算法可以幫助高一新生解決“入學(xué)報到”問題。1.算法的定義請同學(xué)們看一看書上的內(nèi)容和結(jié)合生活經(jīng)驗，想一想什么是算法？（1）古老的算法百錢買百雞：“雞翁一，值錢五；雞母一，值錢三；雞雛三，值錢一；百錢買雞百，問翁、母、雛各幾何？”這是我國古代數(shù)學(xué)家張丘建在《算經(jīng)》中提出的經(jīng)典問題。同時，他還在書中給出了解決該問題的算法“雞翁每增四，雞母每減七，雞雛每益三，即得”。古代的算法主要指的是“算術(shù)”，即數(shù)值的算術(shù)運算。隨著科學(xué)技術(shù)的發(fā)展，“算法”的外延和內(nèi)涵逐漸發(fā)生著變化。（2）廣義的算法廣義地講，“算法”指的是解決問題或完成任務(wù)的一系列步驟。廣義的算法中，需要解決的問題不僅僅指傳統(tǒng)意義上的計算任務(wù)（算術(shù)），也可以是社會生活中各種事務(wù)的處理。比如，假期的自由行旅游方案、一道菜的烹飪過程、洗衣機的操作步驟等。這些算法的執(zhí)行者往往是人，人們按照算法的要求逐步執(zhí)行，最終解決問題。以關(guān)鍵字段和箭頭指向的方式逐一展示廣義算法的概念、運用、案例等，讓同學(xué)們在循序漸進中掌握知識。（3）計算機算法在計算機科學(xué)領(lǐng)域內(nèi)，“算法”指的是用計算機解決問題的步驟，是為了解決問題而需要讓計算機有序執(zhí)行的、無歧義的、有限步驟的集合。這些需要解決的問題不僅包含了數(shù)值計算，還包含了非數(shù)值計算的數(shù)據(jù)處理。例如，在包含上萬人信息的數(shù)據(jù)中查找某人的數(shù)據(jù)、導(dǎo)航程序中兩個地點之間最短路線的規(guī)劃等。解決這些問題的算法執(zhí)行者是計算機，為了讓計算機理解算法中的步驟，需要用計算機能理解的語言來描述算法并將其輸入到計算機中，這個過程就稱為計算機程序設(shè)計。展示用計算機解決實際問題的過程：提出問題→分析問題→設(shè)計方案→編程調(diào)試→解決問題，有兩個重要的環(huán)節(jié)：①設(shè)計算法；②編制和運行程序來實現(xiàn)算法將理論進行講解后再將過程以關(guān)鍵字展示出來，隨后再將重要環(huán)節(jié)重點提出來，讓同學(xué)們掌握重難點。（4）窮舉算法窮舉算法也稱枚舉算法，指的是在求解過程中，先按照一定的順序一一列舉所有可能的解，然后用條件判斷列舉出的可能解是否為正確解。窮舉法一般適合解決解集為離散的且范圍明確的問題。生活中還有哪些問題也可以用算法描述？是不是所有問題都可以用算法描述？洗衣服的過程、報道流程、掛號流程、解題步驟……通過提問的方式檢驗同學(xué)們對知識點的掌握，同學(xué)們相互探究，激發(fā)同學(xué)們對知識探究的欲望。2.算法的特征①有窮性。一個算法的處理步驟必須是有限的。②可行性。一個算法中的每一步操作與要求都應(yīng)該是算法執(zhí)行者（人或者機器）可以實施的，同時在現(xiàn)實環(huán)境中能做到并且能在有限的時間內(nèi)完成。③確定性。算法中對于每個步驟的執(zhí)行描述必須是明確的。④0個或多個輸入。算法被執(zhí)行者實施時，一般需要從外部獲取可變的數(shù)據(jù)。⑤1個或多個輸出。算法必須包含至少一個輸出，以告訴外界問題求解的結(jié)果。將算法特征逐一列出，明確算法的特征，直觀的講述本堂課的知識點。3.算法的要素（1）數(shù)據(jù)用算法解決問題時，必須明確參與運算的初始數(shù)據(jù)、運算時產(chǎn)生的中間數(shù)據(jù)以及代表問題解決的結(jié)果數(shù)據(jù)。列舉案例：在洗衣機執(zhí)行洗衣算法前，必須進行洗滌時間、漂洗次數(shù)、脫水時間、每次洗滌所加水量的設(shè)置，并將這些設(shè)置產(chǎn)生的數(shù)據(jù)輸入到算法中，洗衣機才能按照需求工作。將知識點直觀的羅列出，再進行案例講解，同學(xué)們結(jié)合案例加深對知識點的掌握。（2）運算在對數(shù)據(jù)進行運算時，必須明確每一步的運算是什么、對哪些數(shù)據(jù)進行運算等。例如，在洗衣機的控制算法中必須包含“洗滌時間的計時”“漂洗次數(shù)的統(tǒng)計”以及“判斷加水是否到達50升”等運算。將剛才的例子繼續(xù)引入到本知識點中，進行知識的遷移和強化。（3）控制轉(zhuǎn)移在算法執(zhí)行過程中，有時需要根據(jù)數(shù)據(jù)或運算結(jié)果的特點進行不同的處理，這時就需要運用控制轉(zhuǎn)移來執(zhí)行不同的操作。例如，在洗衣機控制算法的進水過程中，若水量達到50升，則關(guān)閉進水閥，否則不關(guān)閉進水閥，這個環(huán)節(jié)就采用了一種稱為分支結(jié)構(gòu)（也稱選擇結(jié)構(gòu)）的控制轉(zhuǎn)移。再如，漂洗過程中，當(dāng)漂洗次數(shù)未達到2次時，需要繼續(xù)加水到50升，然后重復(fù)原來的漂洗處理，這種需要實現(xiàn)重復(fù)執(zhí)行某些操作的控制轉(zhuǎn)移稱為循環(huán)結(jié)構(gòu)。將兩個案例以對比的方式羅列出來，讓同學(xué)們在對比中掌握本節(jié)的知識點。二、算法的描述一個作曲家想讓一個鋼琴家演奏他創(chuàng)作的新作品，首先他要寫出琴譜，然后鋼琴家才能根據(jù)琴譜進行演奏。同樣地，設(shè)計出一個解決問題的算法，也需要用能被算法執(zhí)行者理解的形式加以呈現(xiàn)，才能被算法執(zhí)行者理解并執(zhí)行。算法的這種呈現(xiàn)就稱為算法的描述。掌握各種算法的描述方法，在解決問題過程中選擇恰當(dāng)?shù)姆绞胶侠淼孛枋鏊惴ǎ墙鉀Q問題的一個重要環(huán)節(jié)。以一個鋼琴演奏的例子引出本小結(jié)的知識點。1.用自然語言描述算法自然語言是人們在日常生活中交流使用的語言，如漢語、英語、德語、日語等。用自然語言描述算法通俗易懂，且不需要進行專門的學(xué)習(xí)和訓(xùn)練。當(dāng)然，人們在長期用自然語言描述算法的過程中也逐漸形成了一些約定俗成的規(guī)則，了解這些規(guī)則有助于快速應(yīng)用自然語言描述算法。某超市為了對蘋果進行促銷，規(guī)定蘋果原價5元，購買3千克以上的，超過3千克的部分可以在原價的基礎(chǔ)上打6折。請同學(xué)們用語言描述付款的算法。使用自然語言描述算法：第一步：輸入蘋果的重量x第二步：判斷蘋果的重量是否大于3千克第三步：如果蘋果的重量不大于3千克，應(yīng)付款y=x*5第四步：如果蘋果的重量大于3千克，應(yīng)付款y=3*5+(x3)*5*0.6第五步：輸出應(yīng)付款的金額通過知識點的逐步引入講解自然語言描述算法，再引入生活中的例子循序漸進的講解算法在生活中的使用，讓同學(xué)們更好的掌握知識點。2.用流程圖描述算法用自然語言描述算法雖然通俗易懂，但也存在難以避免的問題。例如，在描述某些操作時容易出現(xiàn)歧義（面對同樣的文字描述，不同的人產(chǎn)生不同的理解）；在描述根據(jù)條件進行不同處理的算法時比較煩瑣。此時，采用流程圖來描述會顯得比較直觀和易于理解。流程圖用一些圖形符號表示規(guī)定的操作，并用帶箭頭的流程線連接這些圖形符號，表示操作進行方向。流程圖描述算法結(jié)構(gòu)清晰、寓意明確。通過展示自然語言在某些案例使用中的缺點，再引出用流程圖能更好的解決這一問題，隨即以關(guān)鍵詞引出的方式展示流程圖的概念和優(yōu)點，再以表格方式展示流程圖基本圖形及其功能，讓同學(xué)們能直觀的了解其知識點。3.用偽代碼描述算法流程圖雖然直觀易懂，但當(dāng)分支增多時會出現(xiàn)流程線相互交叉而影響算法理解的情況。而且，自然語言和流程圖描述的算法要轉(zhuǎn)化為計算機能理解的計算機程序時，中間還需要較多的語義解釋和格式轉(zhuǎn)換工作。由此，人們想出了用偽代碼來描述算法。偽代碼指的是一種比較直觀簡潔的、符號接近計算機程序代碼的算法描述方式，其風(fēng)格很像計算機程序設(shè)計語言，但又不是真正的可以被計算機理解的代碼。偽代碼的表示方法沒有統(tǒng)一、嚴格的規(guī)定，只要定義合理、表達正確即可。偽代碼由于語法比較接近計算機程序設(shè)計語言，所以描述的算法更加緊湊簡練，也便于進一步轉(zhuǎn)化為相應(yīng)的計算機程序。（1）條件判斷語句格式1：If條件then（語句序列1）Else（語句序列2）語義：若條件成立，則執(zhí)行語句序列1（由一個或多個語句組成），否則執(zhí)行語句序列2。如果在該條件基礎(chǔ)上還需要做進一步的條件判斷，那么可以進行條件判斷語句的嵌套，在If語句中繼續(xù)放入另一個If語句。當(dāng)條件成立需要執(zhí)行特定的語句序列1，而條件不成立不需要執(zhí)行特定的處理時，則采用下列格式：格式2：If條件then（語句序列1）（2）循環(huán)語句格式：while條件（循環(huán)體）語義：循環(huán)體由一個或多個語句組成。循環(huán)語句執(zhí)行時，先判斷條件是否成立，若條件成立則執(zhí)行循環(huán)體，循環(huán)體執(zhí)行完后再次判斷條件是否成立，如此重復(fù)，直到某次條件不成立，則結(jié)束循環(huán)語句，接著去執(zhí)行循環(huán)語句后面的語句。以對比的方式展示兩個語句，并羅列出其語義，讓同學(xué)們在對比中感受兩個語句的不同。4.用計算機程序設(shè)計語言描述算法無論是自然語言描述的算法，還是流程圖或者偽代碼描述的算法，計算機都無法理解并執(zhí)行。為了讓計算機幫助人們真正解決問題，需要將算法用某種計算機程序設(shè)計語言來描述，這個過程稱為程序編寫（或稱代碼編寫）。5.討論探究停車場車位探測中的算法：某停車場每個車位的上方都裝有傳感器（車位探測器）、前方裝有車位指示燈（空車位顯示綠色，否則顯示紅色），如下圖所示。車位上方的傳感器探測下方的車位是否為空，然后根據(jù)探測結(jié)果控制車位指示燈的顏色并向區(qū)域控制器發(fā)送該車位的狀態(tài)信息（“空車位”或“非空車位”）。請同學(xué)們之間相互討論，用自然語言、流程圖、NS圖、偽代碼、程序語言描述。（1）自然語言：分析：傳感器每隔一段時間對車位進行探測，在某個時刻，若傳感器測得結(jié)果為空車位，則將指示燈設(shè)置為綠色，同時向區(qū)域控制器輸出“空車位”的信息；否則，將指示燈設(shè)置為紅色，同時向區(qū)域控制器輸出“非空車位”的信息。將傳感器回傳的數(shù)據(jù)作為輸入數(shù)據(jù)并進行數(shù)字化設(shè)定，若測得空車位，則用輸入數(shù)值1表示，否則用輸入數(shù)值0表示。因為該數(shù)據(jù)會發(fā)生改變，所以用變量flag保存該輸入數(shù)據(jù)。根據(jù)上述分析，某個時刻對車位進行數(shù)據(jù)處理的任務(wù)可以界定為以下問題：輸入flag的值，根據(jù)flag的值設(shè)置車位上方指示燈的顏色，并輸出車位狀態(tài)（“空車位”或“非空車位”）。解決本問題的算法可以用自然語言描述如下。①輸入變量flag的值。②若flag的值為1，則設(shè)置指示燈為綠色，輸出“空車位”；否則，設(shè)置指示燈為紅色，輸出“非空車位”。（2）用流程圖表示車位探測中的算法（3）NS圖“NS圖”是由美國學(xué)者納西（Nassi）和斯奈德曼（Shneiderman）提出的一種在流程圖中完全去掉流程線，全部算法寫在一個矩形框內(nèi)的算法描述方式。相比于原來的流程圖描述，結(jié)構(gòu)性顯得更好，也更有助于高效地編寫程序。用NS圖表示車位探測中的算法（4）車位探測中的算法用偽代碼表示flag←車位探測結(jié)果；#將測得的車位當(dāng)前狀態(tài)值輸入給變量flagIfflag=1then(指示燈綠色輸出“空車位”)Else(指示燈紅色輸出“非空車位”)（5）車位探測中的算法用C++程序設(shè)計語言描述voidMainWindow::on_pushButton_clicked(){intflag=ui>lineEdit>text().toInt();if(flag==1){ui>label_4>setStyleSheet("color:green;");ui>label_4>setText("綠色");ui>label_5>setText("空車位");}else{ui>label_4>setStyleSheet("color:red;");ui>label_4>setText("紅色");ui>label_5>setText("非空車位");}（6）車位探測中的算法用Python程序設(shè)計語言描述表示flag=int(input("輸入車位狀態(tài)值："))ifflag==1:print("綠色")print("空車位")else:print("紅色")print("非空車位")6.拓展鏈接計算機程序設(shè)計語言計算機程序設(shè)計語言經(jīng)歷了“機器語言→匯編語言→高級語言”的發(fā)展歷程。機器語言中的指令由“0”“1”二進制碼組成，機器執(zhí)行效率高但可讀性、維護性差。為了提升編程的效率，科學(xué)家用特定的符號（助記符）來表示各個機器指令，發(fā)明了匯編語言。科學(xué)家后來又發(fā)明了高級語言，用接近人類日常用語的符號來表示各類指令。常見的高級語言有Basic、C、C++、Java、Python、Ruby等。三、小結(jié)四、課堂小練通過設(shè)問的方式，激發(fā)學(xué)生探究問題的積極性，培養(yǎng)學(xué)生表達觀點，分享觀點的意識與能力。學(xué)生自主閱讀課本，總結(jié)歸納，更能激發(fā)學(xué)生自主學(xué)習(xí)的熱情。以關(guān)鍵字段和箭頭指向的方式逐一展示廣義算法的概念、運用、案例等，讓同學(xué)們在循序漸進中掌握知識。將理論進行講解后再將過程以關(guān)鍵字展示出來，隨后再將重要環(huán)節(jié)重點提出來，讓同學(xué)們掌握重難點。通過提問的方式檢驗同學(xué)們對知識點的掌握，同學(xué)們相互探究，激發(fā)同學(xué)們對知識探究的欲望。將算法特征逐一列出，明確算法的特征，直觀的講述本堂課的知識點。將知識點直觀的羅列出，再進行案例講解，同學(xué)們結(jié)合案例加深對知識點的掌握。將剛才的例子繼續(xù)引入到本知識點中，進行知識的遷移和強化。將兩個案例以對比的方式羅列出來，讓同學(xué)們在對比中掌握本節(jié)的知識點。以一個鋼琴演奏的例子引出本小結(jié)的知識點。通過知識點的逐步引入講解自然語言描述算法，再引入生活中的例子循序漸進的講解算法在生活中的使用，讓同學(xué)們更好的掌握知識點。通過展示自然語言在某些案例使用中的缺點，再引出用流程圖能更好的解決這一問題，隨即以關(guān)鍵詞引出的方式展示流程圖的概念和優(yōu)點，再以表格方式展示流程圖基本圖形及其功能，讓同學(xué)們能直觀的了解其知識點。通過列舉同學(xué)們生活中的例子，讓同學(xué)們感受到大數(shù)據(jù)讓生活更便利?，F(xiàn)將知識點羅列出來，然后再舉出兩個例子來論證，知識點和案例的結(jié)合，這樣更能讓同學(xué)們掌握其知識點。以對比的方式展示兩個語句，并羅列出其語義，讓同學(xué)們在對比中感受兩個語句的不同。用一個生活中的案例讓同學(xué)們討論探究，并且要使用剛才講授的知識點，用不同的語言將其描述出來，。S圖的講解通過其知識點的展示后，讓同學(xué)們在流程圖的基礎(chǔ)上將其改為NS圖，并對比兩種流程圖的區(qū)別，這樣能讓同學(xué)們更好的掌握其知識點。通過C語言和Python程序的展示，其語法有所不同，讓同學(xué)們在對比中感受兩種語法，這樣有助于知識點的掌握。將計算機程序設(shè)計語言知識點一一羅列出，讓同學(xué)們直觀的感受。課堂練習(xí)（有題有答案有解析）1.算法流程圖中矩形框的功能是（）A.表示算法的開始或結(jié)束B.表示算法中變量的計算與賦值C.表示算法中的條件判斷D.表示算法中變量的輸入或輸出答案：B解析：本題考查算法流程圖。算法流程圖中矩形框的功能是表示變量的計算與賦值。2.下列關(guān)于算法的敘述,正確的是（）A.描述算法只能使用自然語言B.算法如果沒有數(shù)據(jù)輸入就沒有數(shù)據(jù)輸出C.在執(zhí)行算法時,必須輸入至少一個數(shù)據(jù)D.算法必須能在執(zhí)行有限個步驟之后終止答案：D解析：本題考查算法的特征及其描述。描述算法的常用方法有自然語言描述算法、流程圖描述算法、偽代碼描述算法;一個算法至少有一個數(shù)據(jù)輸出;一個算法可以有零個數(shù)據(jù)輸入;算法必須能在執(zhí)行有限個步驟之后終止。3.下列關(guān)于算法的敘述,正確的是（）A.算法必須有數(shù)據(jù)輸入 B.算法只能用流程圖描述C.算法必須有數(shù)據(jù)輸出 D.可以用算法描述“輸出所有素數(shù)”答案：C解析：本題考查算法的特征及其描述。算法能用自然語言、流程圖、偽代碼描述;一個算法必須有零個或多個數(shù)據(jù)輸入;一個算法必須有一個或多個數(shù)據(jù)輸出;不可以用算法描述“輸出所有素數(shù)”,因為不滿足算法的有窮性。4.以下對算法的理解不正確的是（）A.一個算法應(yīng)包含有限的操作步驟，而不能是無限的B.算法中的每一步驟都應(yīng)當(dāng)是確定的，而不應(yīng)當(dāng)是含糊的、模棱兩可的C.算法可以沒有輸入，但必須有輸出D.算法可以沒有輸出，但必須有輸入答案：D解析：本題考查的是對算法特征的理解，其中算法可以有0個或多個輸入，必須有1個或多個輸出。故正確答案為D。5.下面對算法描述