算法描述與設(shè)計

第一章如何用計算機(jī)解決問題1.1計算機(jī)解決問題的過程1.2算法描述與設(shè)計1.3初試身手，體驗編程游戲規(guī)則：用沒有刻度的3毫升量杯和5毫升量杯，如何量出一毫升的水？①人是如何解決問題的？首先觀察分析問題收集必要的信息根據(jù)已有的知識、經(jīng)驗進(jìn)行判斷、推理嘗試按一定的方法和步驟

解決問題1.1計算機(jī)解決問題的過程1.1計算機(jī)解決問題的過程我國漢代有位大將軍叫韓信，他在點兵時讓士兵分別從1~3、1~5、1~7報數(shù)，然后報告各次報數(shù)的余數(shù)，這樣，他就能推算出總共有多少士兵。

“今有物不知其數(shù)，三三數(shù)之余二，五五數(shù)之余三，七七數(shù)之余二，問物幾何？”“韓信點兵問題”韓信是我國西漢初著名的軍事家。韓信點兵，多多益善，不僅如此，還能經(jīng)常以少勝多，以弱勝強(qiáng)。在與楚軍決戰(zhàn)時韓信指揮諸侯聯(lián)軍，在垓下十面埋伏，擊敗楚軍，楚霸王項羽因此自殺。②計算機(jī)解決問題的過程算法1：列舉法；算法2：最小公倍數(shù)法；算法3：列方程式法；開始N被3、5、7整除余數(shù)為2、3、2N=N+1結(jié)束NYN=1輸出N值②計算機(jī)解決問題的過程1.1計算機(jī)解決問題的過程用列舉法，利用存儲量大、運(yùn)算速度快、精確度高，可以按人們設(shè)定的程序重復(fù)執(zhí)行等特點。②計算機(jī)解決問題的過程1.1計算機(jī)解決問題的過程自然語言是不能被計算機(jī)執(zhí)行的。自然語言計算機(jī)程序程序設(shè)計——思想程序設(shè)計語言——編寫工具機(jī)器語言匯編語言高級語言計算機(jī)010101110001011100101110……②計算機(jī)解決問題的過程1.1計算機(jī)解決問題的過程1.2算法描述與設(shè)計①什么是算法算法就是解決問題的方法和步驟。算法就程序設(shè)計的“靈魂”。算法+數(shù)據(jù)結(jié)構(gòu)=程序；算法獨立于任何具體的程序設(shè)計語言；#include<stdio.h>main(){intn=1;while(n<1100){if(n%3==2&&n%5==3&&n%7==2){printf("%d\n",n);break;}elsen++;}}C語言JAVA語言DimnasintegerN=1Doif(nmod3=2)and(nmod5=3)and(nmod7=2)thenPrintnExitdoEndifN=n+1LoopVB語言1.2算法描述與設(shè)計②算法的特征有窮性；確定性；輸入；輸出；可行性；

算法要有一個清晰的起始步，表示處理問題的起點，且每一個步驟只能有一個確定的后繼步驟(1算法的確定性)，從而組成一個步驟的有限序列(2算法的有窮性)；要有一個終止步(序列的終止)表示問題得到解決或不能得到解決；每條規(guī)則必須是確定的、可行的(3算法的可行性)、不能存在二義性。算法總是對數(shù)據(jù)進(jìn)行加工處理，因此，算法的執(zhí)行過程中通常要有數(shù)據(jù)4輸入(0個或多個)和數(shù)據(jù)5輸出（至少一個）的步驟。如：請輸入您的密碼：判斷：密碼是否為aaa；若是，退出，否則繼續(xù)輸入；練習(xí)①s=1②將s的值增加1③重復(fù)步驟②解答：該算法的步驟②將被重復(fù)執(zhí)行無窮次，不符合①有窮性第1題① L=10② 輸出L/自然數(shù)解答：自然數(shù)沒有具體指明是哪個數(shù)，不符合算法的②確定性第2題① R=2② S=3.14*R*R③ 輸出面積S說明：該算法中在執(zhí)行時已包含計算所需的初始數(shù)據(jù)，不必另外提供數(shù)據(jù)，因此沒有輸入，即有0個輸入。第3題① 輸入圓的半徑R② S=3.14*R*R③ 輸出面積S說明：該算法中計算面積所需的初始數(shù)據(jù)半徑R待定，需要在算法執(zhí)行時從鍵盤多個輸入。第4題① 輸入圓的半徑R② S=3.14*R*R③ C=2*3.14*R④ 輸出面積S，周長C說明：通過前兩個例子可以知道，算法可能有1個或多個輸出。第5題① x=-2② 計算x的平方根解答：x是負(fù)數(shù)，沒有平方根，該算法不可行，不符合算法的可行性。第6題1.2算法描述與設(shè)計②描述算法1、將N的初始值賦為12、如果N<100并且N被3、5、7整除后余數(shù)為2、3、2，則輸出N的值，轉(zhuǎn)入第4步；3、將N的值加1,轉(zhuǎn)到第2步；4、結(jié)束程序自然語言自然語言優(yōu)點通俗易懂缺點缺乏直觀性簡潔性，容易產(chǎn)生歧義如：“這個人連老張也不認(rèn)識”。意思1：這個人不認(rèn)識老張；

意思2：老張不認(rèn)識這個人；韓信點兵問題1.2算法描述與設(shè)計②描述算法流程圖流程圖是通過箭頭相互連接的幾何圖形來表達(dá)的方法。=程序框圖ANSI規(guī)定的一些常用流程圖符號。起止框輸入輸出框判斷框處理框連接點流程線開始N被3、5、7整除余數(shù)為2、3、2N=N+1結(jié)束NYN=1輸出N值1.2算法描述與設(shè)計②描述算法流程圖韓信點兵問題流程圖優(yōu)點形象、直觀、更容易理解缺點1.2算法描述與設(shè)計②描述算法偽代碼是介于自然語言和計算機(jī)程序之間的一種算法描述。偽代碼優(yōu)點書寫自由，專業(yè)缺點N=1DOifN除以3余2且N除以5余3且N除以7余2then輸出N退出程序endifN=n+1loop1、將N的初始值賦為12、如果N<100并且N被3、5、7整除后余數(shù)為2、3、2，則輸出N的值，轉(zhuǎn)入第4步；3、將N的值加1,轉(zhuǎn)到第2步；4、結(jié)束程序DimnasintegerN=1Doif(nmod3=2)and(nmod5=3)and(nmod7=2)thenPrintnExitdoEndifN=n+1LoopN=1DOifN除以3余2且N除以5余3且N除以7余2then輸出N退出程序endifN=n+1loop自然語言流程圖偽代碼程序語言1.2算法描述與設(shè)計②描述算法三種描述算法的比較自然語言優(yōu)點通俗易懂缺點冗長，繁鎖，缺乏直觀性簡潔性，容易產(chǎn)生歧義流程圖優(yōu)點形象、直觀、更容易理解缺點需要一定數(shù)學(xué)知識偽代碼優(yōu)點簡潔、易懂，修改起來比較容易，易轉(zhuǎn)為程序語言代碼缺點沒有流程圖直觀，出現(xiàn)錯誤不便排查第一章如何用計算機(jī)解決問題1、什么是算法？2、算法的特征：53、算法的描述方法？3小結(jié)練習(xí)：說出下面流程圖的各框名稱開始框輸入框處理框判斷框處理框處理框處理框輸出框結(jié)束框如果兩個數(shù)有最大公約數(shù)A，那么這兩個數(shù)，以及這兩個數(shù)的差，還有大數(shù)除以小數(shù)的余數(shù)，必然都是A的倍數(shù)。

所以當(dāng)最后兩個數(shù)剛好能整除時，較小的數(shù)就是最大公約數(shù)。第一章如何用計算機(jī)解決問題1、

算法是解決問題的（

）A．程序代碼

B．方法與步驟

C．計算公式

D．最終結(jié)果2、利用可視化程序設(shè)計語言進(jìn)行信息的編程加工的一般順序是（

）

A、編寫代碼、設(shè)計算法、設(shè)計界面、調(diào)試運(yùn)行

B、設(shè)計算法、設(shè)計界面、編寫代碼、調(diào)試運(yùn)行

C、設(shè)計算法、編寫代碼、設(shè)計界面、調(diào)試運(yùn)行

D、設(shè)計算法、編寫代碼、調(diào)試運(yùn)行、設(shè)計界面3、下面關(guān)于算法的說法錯誤的是（

）A．算法必須有輸出

B．算法就是程序

C．算法不一定有輸入

D．算法必須在有限步執(zhí)行后能結(jié)束4、以下不屬于算法基本特征的是（

）A．可執(zhí)行性

B．確定性

C．有窮性

D．無限性5、流程圖中表示判斷框的是（

）。A．矩形框B．菱形框

C．圓形框D．橢圓形框第一章如何用計算機(jī)解決問題6、下列哪一個不是用于程序設(shè)計的（）A.BASIC

B.C語言C.WORD

D.Pasical7、程序設(shè)計語言的發(fā)展階段不包括（）A.機(jī)器語言B.自然語言C.匯編語言D.高級語言8、下面說法正確的是（）A.算法+數(shù)據(jù)結(jié)構(gòu)=程序B.算法就是程序

C.數(shù)據(jù)結(jié)構(gòu)就是程序

D.算法包括數(shù)據(jù)結(jié)構(gòu)9、下列不屬于描述算法方式的是（）A、自然語言

B、偽代碼

C、流程圖

D、機(jī)器語言10、流程圖是描述（）的常用方法A、程序B、算法

C、數(shù)據(jù)結(jié)構(gòu)

D、計算規(guī)則11、下列關(guān)于算法描述語言，錯誤的是（）A、用流程圖描述算法形象、直觀B、自然語言描述的算法很容易轉(zhuǎn)化為程序設(shè)計語言C、用偽代碼編寫的算法簡潔易懂、容易修改D、自然語言描述的算法通俗易懂，但缺乏直觀性和簡潔性填空題1、算法就是解決問題的___________和_________。2、算法描述可以有多種表達(dá)方法，一般用_______、_______和______