第二章

算法與問題解決1、算法的概念及描述2、算法的控制結(jié)構(gòu)3、用算法解決問題的過程12.1算法的概念及描述

2132算法的定義算法的特征算法的要素4算法的描述主要內(nèi)容3問題：狼、菜、羊過河有一個(gè)牧羊人帶著一頭羊,一只狼和一顆大白菜準(zhǔn)備過河,他找到一只很小的船,每次只能帶一樣?xùn)|西過去,可是如果讓狼與羊單獨(dú)在一起,狼會(huì)吃羊,讓羊與白菜單獨(dú)在一起,羊會(huì)吃白菜，請(qǐng)你說說牧羊人應(yīng)如何過河？4過河步驟:過河的步驟:第一步：人將羊運(yùn)過去第二步：人返回第三步：人將菜運(yùn)過去第四步：人將羊運(yùn)回來第五步：人將狼運(yùn)過去第六步：人返回第七步：將羊運(yùn)過去5那到底什么是算法？

6算法的定義古代的算法古代的算法主要指的是”算術(shù)”，即數(shù)值的算術(shù)運(yùn)算。隨著科學(xué)技術(shù)的發(fā)展，算法的外延和內(nèi)涵逐漸發(fā)生著變化。廣義算法算法指的是解決問題或完成任務(wù)的一系列步驟。既包括傳統(tǒng)意義上計(jì)算任務(wù)，也可以是生活中各種事物的處理。計(jì)算機(jī)算法計(jì)算機(jī)領(lǐng)域內(nèi)，算法指的是用計(jì)算機(jī)解決問題的步驟。是為了解決問題而讓計(jì)算機(jī)執(zhí)行的有序執(zhí)行的、無(wú)歧義的，有限步驟的集合。7算法的特征有1個(gè)或多個(gè)輸出有0個(gè)或多個(gè)輸入確定性可行性有窮性8用計(jì)算機(jī)解決問題，本質(zhì)上是“數(shù)據(jù)運(yùn)算”的方式來實(shí)現(xiàn)的。

9算法的要素10數(shù)據(jù)運(yùn)算控制轉(zhuǎn)移能否描述算法的要素在洗衣機(jī)洗衣服時(shí)的體現(xiàn)數(shù)據(jù)：在洗衣機(jī)執(zhí)行洗衣算法前，必須進(jìn)行洗滌時(shí)間、漂洗次數(shù)、脫水時(shí)間、每次洗滌所加水量的設(shè)置，并將設(shè)置產(chǎn)生的數(shù)據(jù)輸入到算法中，洗衣機(jī)才能按照需求工作。運(yùn)算：洗衣機(jī)的控制算法中包含“洗滌時(shí)間的計(jì)時(shí)”、“漂洗次數(shù)的統(tǒng)計(jì)”、“判斷加水是否到達(dá)50升”等運(yùn)算?？刂妻D(zhuǎn)移：在洗衣機(jī)的控制算法進(jìn)水過程中，比如水量達(dá)到50升則關(guān)閉水閥，否則不關(guān)閉水閥，再如漂洗次數(shù)未達(dá)到2次時(shí)，需要繼續(xù)加水到50升。11控制結(jié)構(gòu)12分支結(jié)構(gòu)先進(jìn)行條件判斷，再根據(jù)判斷結(jié)果分別執(zhí)行不同處理的控制結(jié)構(gòu)。①首先進(jìn)行條件判斷,根據(jù)條件滿足與否來決定執(zhí)行哪個(gè)分支。②在一個(gè)分支結(jié)構(gòu)中，必定有一個(gè)分支被執(zhí)行，其他的分支則被忽略。順序結(jié)構(gòu)算法中各個(gè)步驟按照先后順序依次執(zhí)行的結(jié)構(gòu)。①每個(gè)步驟按照算法中出現(xiàn)的順序依次執(zhí)行。②每個(gè)步驟一定會(huì)被執(zhí)行一次，而且只執(zhí)行一次。循環(huán)結(jié)構(gòu)算法執(zhí)行過程中，在條件控制下，某些操作步驟需要重復(fù)執(zhí)行(循環(huán))的控制結(jié)構(gòu)。案例:某停車場(chǎng)每個(gè)車位的上方都裝有傳感器(車位探測(cè)器)前方裝有車位指示燈(空車位顯示綠色，否則顯示紅色)。車位上方的傳感器探測(cè)下方的車位是否為空，然后根據(jù)探測(cè)結(jié)果控制車位指示燈的顏色并向區(qū)域控制器發(fā)送該車位的狀態(tài)信息(“空車位”或“非空車位”)。請(qǐng)用算法描述上面的案例。算法的描述13（1）自然語(yǔ)言描述算法:將傳感器回傳的數(shù)據(jù)作為輸人數(shù)據(jù)并進(jìn)行數(shù)字化設(shè)定，若測(cè)得空車位，則用輸入數(shù)值1表示，否則用輸人數(shù)值0表示。用變量flag保存該輸人數(shù)據(jù)。輸入flag的值，根據(jù)flag的值設(shè)置車位上方指示燈的顏色，并輸出車位狀態(tài)(“空車位”或“非空車位”)。（1）自然語(yǔ)言描述算法:解決本問題的算法可以用自然語(yǔ)言描述如下：（1）輸人變量flag的值。（2）若flag的值為1,則設(shè)置指示燈為綠色，輸出“空車位”;否則，設(shè)置指示燈為紅色，輸出“非空車位”。算法的描述——自然語(yǔ)言14自然語(yǔ)言描述算法的優(yōu)缺點(diǎn)15咬死獵人的狗咬死獵人的“狗”咬死“獵人的狗“咬“死獵人的狗“咬死“獵人的”狗優(yōu)點(diǎn)容易理解缺點(diǎn)書寫煩瑣，不確定性，對(duì)復(fù)雜的問題難以表達(dá)準(zhǔn)確，不能被計(jì)算機(jī)識(shí)別和執(zhí)行。算法的描述——流程圖16算法的描述——流程圖圖形名稱功能開始/結(jié)束符表示算法的開始或結(jié)束輸入/輸出表示數(shù)據(jù)的輸入或輸出處理框表示數(shù)據(jù)的運(yùn)算處理判斷框表示算法中的條件判斷流程線表示算法中的流向連接點(diǎn)表示算法中的轉(zhuǎn)接17常用的流程圖基本圖形及其功能算法的描述方法——流程圖開始輸入蘋果的重量xX>2?Y=X*1.5Y=2*1.5+(X-2)*1.5*0.8輸出應(yīng)付款y結(jié)束YN案例1：(1)輸入蘋果的重量x(2)判斷蘋果的重量是否大于2千克(3)如果蘋果的重量不大于2千克，應(yīng)付款y=x*1.5(4)如果蘋果的重量大于2千克，應(yīng)付款y=2*1.5+(x-2)*1.5*0.8(5)輸出應(yīng)付款的金額18算法的描述——流程圖案例2：用流程圖表示交換a和b的值，并輸出。開始aa+bba-baa-b結(jié)束流程圖中a和b為變量，“”表示賦值。如果a的值為15，b的值為10，代入到流程圖中，看看結(jié)果是什么？輸入變量a,b的值輸出變量a,b的值19使用流程圖描述算法的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：直觀、形象、結(jié)構(gòu)清晰缺點(diǎn)：情況復(fù)雜時(shí)，流程線過多，影響理解。不能被計(jì)算機(jī)識(shí)別和執(zhí)行。算法的描述——N-S圖“N-S圖”是由美國(guó)學(xué)者納西（Nassi）和斯奈德曼（Shneiderman）提出的一種在流程圖中完全去掉流程線，全部算法寫在一個(gè)矩形框內(nèi)的算法描述方式。相比于原來的流程圖描述，結(jié)構(gòu)性顯得更好，也更有助于高效地編寫程序。前面車位探測(cè)中的算法，可用N-S圖表示成如下形式。輸入flag的值指示燈綠色指示燈紅色輸出“空車位”輸出“非空車位”Flag=1?是否拓展鏈接：20算法的描述——偽代碼（3）偽代碼描述算法:flag←車位探測(cè)結(jié)果;#將測(cè)得的車位當(dāng)前狀態(tài)值輸入給變量flagIfflag=1then(指示燈綠色輸出“空車位”)Else(指示燈紅色

輸出“非空車位”)1.條件判斷語(yǔ)句格式1:If條件then(語(yǔ)句序列1)Else(語(yǔ)句序列2)格式2：If條件then(語(yǔ)句序列1)2.循環(huán)語(yǔ)句格式:while條件(循環(huán)體)舉例：a的值為5Whilea>1a=a–1輸出a的值21本書語(yǔ)法約定：算法的描述方法——代碼（4）計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言描述算法:C++程序設(shè)計(jì)語(yǔ)言：voidMainWindow::on_pushButton_clicked(){intflag=ui->lineEdit->text().toInt();if(fag==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("非空車位");}}Python程序設(shè)計(jì)語(yǔ)言：flag=int(input("輸入車位狀態(tài)值:"))ifflag==1:print("綠色")print("空車位")else:print("紅色")print("非空車位")22算法的描述方法——程序PrivateSubCommand1_Click()DimxAsSingle,yAsSinglex=Val(Text1.Text)Ifx<=2Theny=x*1.5Elsey=2*1.5+(x-2)*1.5*0.8EndIfText2.Text=yEndSub開始輸入蘋果的重量xX>2?Y=x*1.5Y=2*1.5+(x-2)*1.5*0.8輸出應(yīng)付款y結(jié)束YN23算法的描述常見的算法描述自然語(yǔ)言流程圖偽代碼計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言24算法的擇優(yōu)解決同一個(gè)問題可能有不同的算法

著名數(shù)學(xué)家華羅庚“燒水泡茶”的兩個(gè)算法。算法一第一步：燒水；第二步：水燒開后，洗刷茶具；第三步：沏茶。

算法二第一步：燒水；第二步：燒水過程中，洗刷茶具；第三步：水燒開后沏茶。第二個(gè)算法的科學(xué)性在于應(yīng)用了“統(tǒng)籌方法”區(qū)別？哪個(gè)更高效？一個(gè)好算法必須用到科學(xué)的方法25小結(jié)——算法的概念及描述1.算法的定義：解決問題的方法和步驟2.算法的特