第二章算法與問題解決PPT課件

1、第二章算法與問題解決1、算法的概念2、算法的描述3、計算機解決問題的過程溫州中學溫州中學游戲：狼、菜、羊過河 有一個牧羊人帶著一頭羊,一只狼和一顆大白菜準備過河,他找到一只很小的船,每次只能帶一樣東西過去,可是如果讓狼與羊單獨在一起,狼會吃羊,讓羊與白菜單獨在一起,羊會吃白菜，請你說說牧羊人應如何過河？Answer:過河的方案過河的方案: : 第一步：人和羊過河，人返回，留下羊；第一步：人和羊過河，人返回，留下羊； 第二步：人和狼過河，人和羊返回，留下狼；第二步：人和狼過河，人和羊返回，留下狼； 第三步：人和菜過河，人返回，留下菜；第三步：人和菜過河，人返回，留下菜； 第四步：人和羊過河第四步

2、：人和羊過河 廣義的講，是。 計算機科學領(lǐng)域內(nèi)，“算法”指的是用計算機解決問題的步驟，是為了解決問題而需要讓計算機的集合。解決的問題包含數(shù)值計算和非數(shù)值計算的數(shù)據(jù)處理。什么是算法？什么是算法？1.有窮性(一個算法的處理步驟必須是有限的)2.確定性 (算法中對于每個步驟的執(zhí)行描述必須是明確的)4.有0個或多個輸入 (初始數(shù)據(jù)可從外界輸入，也可包含在算法中)算法的特征3.可行性 (算法中的每個步驟都是可執(zhí)行的，同時能在現(xiàn)實環(huán)境和有限時間內(nèi)完成)輸出：所有整數(shù)求解：10/正整數(shù)求解：最大的素數(shù)5.有1個或多個輸出 (算法必須有結(jié)果，即包含至少一個輸出)“程序出錯” 也是一種輸出算法的特征算法的特征算

3、法的描述方法算法的描述方法人們?nèi)粘Ｉ钪惺褂玫恼Z言，漢語，英語等都是自然語言，這些自然語言描述算法符合我們的表達習慣，且容易理解，但不直觀，并且容易產(chǎn)生歧義。也叫程序框圖，是算法的一種圖形化表示方法，與自然語言描述算法相比，用流程圖描述算法形象、直觀、更容易理解。是指一種比較直觀簡潔的、符號接近計算機程序的算法描述方式，風格很像計算機程序設計語言，但又不是真正的可以被計算機理解的代碼。 計算機是人腦的延伸，要研究計算機解決問題的過程，首先要從人解決問題的角度談起。算法的三種描述方法某商場為了對蘋果進行促銷，規(guī)定蘋果原價1.5元，購買2千克以上的，超過2千克的部分可以在原價的基礎(chǔ)上打8折。請同學

4、們用語言描述付款的算法。算法的描述方法自然語言使用自然語言描述算法。 （1）輸入蘋果的重量x （2）判斷蘋果的重量是否大于2千克 （3）如果蘋果的重量不大于2千克，應付款y=x*1.5 （4）如果蘋果的重量大于2千克，應付款y=2*1.5+(x-2)*1.5*0.8 （5）輸出應付款的金額使用自然語言描述算法的優(yōu)缺點 優(yōu)點：通俗易懂，且不需要進行專門的學習和訓練。 缺點：描述某些操作時容易產(chǎn)生歧義，描述根據(jù)條件進行不同的算法時比較繁瑣。算法的描述方法自然語言流程圖符號表示算法的開始與結(jié)束 表示輸入、輸出數(shù)據(jù) 用于表示要處理的內(nèi)容表示條件判斷及產(chǎn)生分支的情況 用于連接因頁面寫不下而斷開的流程線

5、有向線段，用于控制流程方向 開始開始初始等級初始等級=1輸入職業(yè)選擇輸入職業(yè)選擇遇到100級怪物是否發(fā)起攻擊躲過一劫 繼續(xù)游戲YN1 挑戰(zhàn)失敗 重新游戲遇到1級怪物是否發(fā)起攻擊錯失升級機會 懊惱跳腳成功升級 等級2YN1輸出角色等級輸出角色等級結(jié)束結(jié)束算法的描述方法流程圖使用流程圖描述算法的優(yōu)缺點 優(yōu)點：結(jié)構(gòu)清晰，寓意明確。 缺點：分支較多時出現(xiàn)流程線相互交叉的情況，需要較多的語義解釋和格式轉(zhuǎn)換工作。算法的優(yōu)劣解決同一個問題可能有不同的算法對同一問題，可以有不同的解題方法和步驟對同一問題，可以有不同的解題方法和步驟華羅庚在數(shù)華羅庚在數(shù)學普及讀物學普及讀物統(tǒng)籌方法平話及補充統(tǒng)籌方法平話及補充中，

6、以中，以“泡茶泡茶”為例，為例，闡明了設計和闡明了設計和選擇合適的、優(yōu)化的算法選擇合適的、優(yōu)化的算法的重要性。的重要性。 想要泡茶喝，此時的情況是：有茶葉和涼水，還沒燒開，水壺和茶壺和茶杯還沒洗都要洗，怎么辦？泡茶步驟方法甲方法甲方法乙方法乙方法丙方法丙 不僅要考慮解決方法的正確性，還要注意效率。區(qū)別？區(qū)別？哪個更高效？哪個更高效？算法的三種基本結(jié)構(gòu)算法的三種基本結(jié)構(gòu)算法基本是由順序結(jié)構(gòu)、分支結(jié)構(gòu)、循環(huán)結(jié)構(gòu)這三種基本結(jié)構(gòu)組合而成。大程序采用“自上而下，逐步細化”的方法，把大任務拆分成若干個小任務組成，每一個小任務再分解為若干個子任務，逐級分解，直至三種基本結(jié)構(gòu)。把冰箱門打開把冰箱門打開把大象放

7、進去把大象放進去算法的三種基本的控制結(jié)構(gòu)算法的三種基本的控制結(jié)構(gòu) 一個步驟完成后，順序執(zhí)行緊跟著的下個處理步驟。 如電視節(jié)目，按先后順序直線下來。把大象放進冰箱分哪幾步？把冰箱門關(guān)上把冰箱門關(guān)上算法的三種基本的控制結(jié)構(gòu)算法的三種基本的控制結(jié)構(gòu) 根據(jù)情況的不同，在預定的兩個模式中，選擇一個合理的步驟執(zhí)行 如根據(jù)停電情況，選擇信息課上課場地問題。停電了？停電了？到教室上課到教室上課到機房上課到機房上課Y YN N算法的三種基本的控制結(jié)構(gòu)算法的三種基本的控制結(jié)構(gòu) 對某個情況e進行判斷，當結(jié)果為真時，執(zhí)行處理步驟step，然后再次判斷這個情況e，當結(jié)果為真是，再次執(zhí)行步驟step，并繼續(xù)判斷情況e?？?/p>

8、是重復上述過程，直到判斷的結(jié)果為假。 如電影捉妖記中井柏然吃面。你還餓嗎？你還餓嗎？吃一碗面吃一碗面Y YN N201.抽象與建模抽象與建模a.提煉核心要素并加以確定或假設b.用數(shù)學符號描述解決問題的計算模型2.設計算法設計算法a.輸入數(shù)據(jù)b.處理數(shù)據(jù) c.輸出處理結(jié)果3.描述算法描述算法自然語言、流程圖、偽代碼、計算機程序設計語言用算法解決問題用算法解決問題某地出租車米表進行計費，規(guī)則如下：3公里（包括3公里）以內(nèi)收起步價10元；超過3公里但低于10公里（包括10公里）時，超過部分每公里2元；超過10公里時，超過部分每公里3元。21某地出租車米表進行計費，規(guī)則如下：3公里（包括3公里）以內(nèi)收

9、起步價10元；超過3公里但低于10公里（包括10公里）時，超過部分每公里2元；超過10公里時，超過部分每公里3元。用算法解決問題用算法解決問題明確要素：明確要素：明確數(shù)學函數(shù)：明確數(shù)學函數(shù)：具體算法設計具體算法設計: :里程數(shù)里程數(shù)x 費用費用f),10(10, 3(3 , 0(31027102)3(1010）（xxf1.輸入里程數(shù)輸入里程數(shù)x2.若若0 x=3,f=10; 若若3x=10,f=10+7*2+3(x-10)3.輸出費用輸出費用fA.算法的基本特征是：有窮性，確定性，可行性，有零個或多個輸入，至少產(chǎn)生一個輸出B.算法獨立于具體的程序設計語言，一個算法可以用多種程序設計語言來實現(xiàn)C

10、.算法就是程序，設計算法的過程就是程序設計的過程D.常見的四種算法描述方法是自然語言法、流程圖法、偽代碼法和計算機程序設計語言C課堂練習A.抽象與建模 B.問題界定 C.設計算法 D.描述算法 B課堂練習A. 自然語言、流程圖 B.偽代碼、流程圖 C.自然語言、偽代碼 D.流程圖、自然語言 A課堂練習4. 有流程圖如下圖所示，其功能是將鍵盤輸入的數(shù)進行相加，當輸入的數(shù)為0時輸出它們的和，則圖中虛線部分的內(nèi)容是（ ） A. B. C. D. D課堂練習5有部分流程圖結(jié)構(gòu)如下，其算法結(jié)構(gòu)屬于（ ） A.順序結(jié)構(gòu) B.重復結(jié)構(gòu) C.分支結(jié)構(gòu) D.循環(huán)結(jié)構(gòu) D課堂練習內(nèi)容總覽python的文件操作的文

11、件操作文件模式描述r以只讀方式打開文件（默認）w以只寫方法打開文件。若文件不存在，則新建文件；如果文件已存在，則清空文件原有內(nèi)容a以只寫方法打開文件。若文件不存在，則新建文件；如果文件已存在，在文件原有內(nèi)容末尾追加內(nèi)容+以讀寫方式打開文件打開文件打開文件fileVariable = open(filename, mode)open函數(shù)為文件函數(shù)為文件filename返回文件對象返回文件對象fileVariable，文件模式，文件模式mode指定如何打開文件指定如何打開文件關(guān)閉文件關(guān)閉文件fileVariable.close()輸入輸入方法描述read( )從文件中讀取所有內(nèi)容readline(

12、 )從文件中讀取一整行內(nèi)容，包括n字符。readlines( )以行為單位從文件中讀取所有內(nèi)容（直至文件末尾），自動將文件內(nèi)容解析成一個行的列表，返回行的列表。方法描述write(str)向文件中寫入指定字符串，不會自動在字符串末尾添加n字符，str表示要寫入文件的字符串writelines(sequence)向文件中寫入一序列的字符串，例如字符串列表，不會自動在字符串末尾添加n字符python的文件操作的文件操作輸出輸出 file1 = open( “hi.txt, “w ) #打開一個指定的文件 s = “I want to learn programming well！” file1.write( s ) #向文件中寫入字符串s，注意沒有回車動手實踐動手實踐操作操作1：打開一個文件，并向該文件