第一章 算法和算法的表示

1、 1.1使用計(jì)算機(jī)解決問(wèn)題的一般過(guò)程使用計(jì)算機(jī)解決問(wèn)題的一般過(guò)程 科學(xué)技術(shù)的進(jìn)步，社會(huì)生產(chǎn)力的發(fā)展，都是由于相關(guān)的問(wèn)題得到不斷的解決的結(jié)果。在當(dāng)今社會(huì)中，由于信息化概念的提出，許多問(wèn)題的解決都使用到了計(jì)算機(jī)。（一）、人工解題（一）、人工解題（二）、計(jì)算機(jī)解題（二）、計(jì)算機(jī)解題1、理解和分析所面臨的問(wèn)題 2、尋找解題的途徑和方法 3、用筆、紙和算盤(pán)、計(jì)算器等工具進(jìn)行計(jì)算 4、驗(yàn)證計(jì)算結(jié)果 人們解決問(wèn)題一般使用到以下兩種方法： 早期，由于數(shù)據(jù)量小，人們以手工算法居多，隨著科技的發(fā)展和計(jì)算機(jī)性能的提高，越來(lái)越多的人使用計(jì)算機(jī)來(lái)解決各式各樣的問(wèn)題。 計(jì)算機(jī)看起來(lái)似乎無(wú)所不能，實(shí)際上，至今為止，計(jì)算機(jī)只

2、能按照設(shè)計(jì)好的程序，一步一步地進(jìn)行計(jì)算。計(jì)算機(jī)是程序的忠實(shí)執(zhí)行者!使用計(jì)算機(jī)解決問(wèn)題一般要經(jīng)歷三個(gè)階段：1、分析問(wèn)題確定要用計(jì)算機(jī)做什么2、尋找解決問(wèn)題的途徑和方法3、用計(jì)算機(jī)進(jìn)行處理做什么怎么做農(nóng)夫的故事農(nóng)夫的故事一個(gè)農(nóng)夫帶著一個(gè)農(nóng)夫帶著一條狼、一頭山羊和一籃一條狼、一頭山羊和一籃蔬菜蔬菜要過(guò)河，但只有一條船。乘船時(shí)，農(nóng)夫要過(guò)河，但只有一條船。乘船時(shí)，農(nóng)夫只能帶一樣?xùn)|西。當(dāng)農(nóng)夫在場(chǎng)的時(shí)候，這三只能帶一樣?xùn)|西。當(dāng)農(nóng)夫在場(chǎng)的時(shí)候，這三樣?xùn)|西相安無(wú)事。一旦農(nóng)夫不在，樣?xùn)|西相安無(wú)事。一旦農(nóng)夫不在，狼會(huì)吃羊，狼會(huì)吃羊，羊會(huì)吃菜羊會(huì)吃菜。請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法，使農(nóng)夫能安全。請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法，使農(nóng)夫能安全地將這三

3、樣?xùn)|西帶過(guò)河。地將這三樣?xùn)|西帶過(guò)河。過(guò)河步驟：過(guò)河步驟：1、農(nóng)夫帶羊過(guò)河、農(nóng)夫帶羊過(guò)河2、農(nóng)夫回來(lái)、農(nóng)夫回來(lái)3、把狼帶過(guò)河、把狼帶過(guò)河4、把羊帶回來(lái)、把羊帶回來(lái)5、帶蔬菜過(guò)河、帶蔬菜過(guò)河6、農(nóng)夫回來(lái)、農(nóng)夫回來(lái)7、把羊帶過(guò)河、把羊帶過(guò)河解一：解一：解二：解二：1、農(nóng)夫帶羊過(guò)河、農(nóng)夫帶羊過(guò)河2、農(nóng)夫回來(lái)、農(nóng)夫回來(lái)3、帶蔬菜過(guò)河、帶蔬菜過(guò)河4、把羊帶回來(lái)、把羊帶回來(lái)5、把狼帶過(guò)河、把狼帶過(guò)河6、農(nóng)夫回來(lái)、農(nóng)夫回來(lái)7、把羊帶過(guò)河、把羊帶過(guò)河演示課件演示課件1.2 確定解決問(wèn)題的方法下面將通過(guò)實(shí)例來(lái)說(shuō)明計(jì)算機(jī)解決實(shí)際問(wèn)題的步驟。第一章第一章 算法和算法的表示算法和算法的表示L面積Sh=？w=?4h1，h

4、2 =d設(shè)設(shè)當(dāng)當(dāng)d0時(shí)，方程的兩個(gè)根就是時(shí)，方程的兩個(gè)根就是h和和w44當(dāng)當(dāng)d0時(shí)，方程有兩個(gè)相同的根，即矩形為一個(gè)邊長(zhǎng)為時(shí)，方程有兩個(gè)相同的根，即矩形為一個(gè)邊長(zhǎng)為L(zhǎng)/4的正方形的正方形當(dāng)當(dāng)d0時(shí)，方程無(wú)實(shí)數(shù)根，無(wú)解。時(shí)，方程無(wú)實(shí)數(shù)根，無(wú)解。1.3 把解決問(wèn)題的方法步驟化指令指令: :用來(lái)規(guī)定計(jì)算機(jī)操作的命令用來(lái)規(guī)定計(jì)算機(jī)操作的命令程序：為解決某一問(wèn)題而編排的一個(gè)指令序列。通常，一個(gè)程序由如下程序：為解決某一問(wèn)題而編排的一個(gè)指令序列。通常，一個(gè)程序由如下兩部分組成：指令部分和數(shù)據(jù)部分兩部分組成：指令部分和數(shù)據(jù)部分 為使計(jì)算機(jī)能按照上面確定的方法進(jìn)行計(jì)算，光有計(jì)算公式是不夠的，還必須把解決問(wèn)題的

5、方法步驟化，即要用某種方式告訴計(jì)算機(jī)，第1步做什么，第2步做什么。 對(duì)例1而言，在計(jì)算前，計(jì)算機(jī)必須要知道給定的鐵絲長(zhǎng)度L和所要求的面積S。即把計(jì)算機(jī)所需的原始數(shù)據(jù)L和S輸入到計(jì)算機(jī)中，然后按照編好的程序一步步進(jìn)行計(jì)算。D=0?開(kāi)始輸入L，SD=(-L/2)2-4SW=(L/2)-H輸出H、W退出W=(L/2+D)/2或H=(L/2-D)/2輸出無(wú)解 為解決不同的問(wèn)題，人們必須設(shè)計(jì)不同的程序。設(shè)計(jì)一個(gè)程序時(shí)，需要考慮以下的問(wèn)題：1、數(shù)據(jù)的存儲(chǔ)2、計(jì)算的過(guò)程典型的指令類型有：輸入指令：通過(guò)輸入設(shè)備向程序輸入數(shù)據(jù)，并存儲(chǔ)到指定的變量中。輸出指令：把計(jì)算獲得的結(jié)果，通過(guò)輸出設(shè)備輸出。算術(shù)運(yùn)算指令：進(jìn)

6、行加、減、乘、除等算術(shù)運(yùn)算。邏輯判斷指令：對(duì)指定的兩個(gè)數(shù)進(jìn)行比較，產(chǎn)生一個(gè)邏輯值（真或假）?？刂妻D(zhuǎn)移指令：用來(lái)改變程序中指令的執(zhí)行順序。1.4 算法的概念和表示方法 算法就是解題方法的精確描述。1、算法的概念：2、算法的特征有窮性：一個(gè)算法的執(zhí)行步驟是有限的確定性：算法中的每個(gè)步驟必須有確切的含義可行性：算法的每個(gè)步驟是可行的，是實(shí)際能做的有0個(gè)或多個(gè)輸入有1個(gè)或多個(gè)輸出3、算法的表示形式自然語(yǔ)言流程圖計(jì)算機(jī)語(yǔ)言 1)1)輸入整數(shù)的值；輸入整數(shù)的值；2)2)將的值置為；將的值置為；3)3)將的值置為將的值置為 ；4)4)判斷判斷? ?，條件成立執(zhí)行下一步，否則跳轉(zhuǎn)至第步；，條件成立執(zhí)行下一步，

7、否則跳轉(zhuǎn)至第步；5)5)判斷能否整除，若能整除即找到因子，跳轉(zhuǎn)第步；判斷能否整除，若能整除即找到因子，跳轉(zhuǎn)第步；6)6)的值增加，跳轉(zhuǎn)至第的值增加，跳轉(zhuǎn)至第4 4步；步；7)7)判斷判斷 ? ?，條件成立輸出結(jié)果，條件成立輸出結(jié)果“是素?cái)?shù)是素?cái)?shù)”，否則輸出結(jié)，否則輸出結(jié)果是果是“合數(shù)合數(shù)”。N Private Sub Command1_Click()Private Sub Command1_Click() Dim a As Long, b As Long, n As Long Dim a As Long, b As Long, n As Long n = Val(Text1.Text) n =

8、 Val(Text1.Text) 輸入整數(shù)輸入整數(shù)N N b = Int(Sqr(n b = Int(Sqr(n) + 1) + 1 計(jì)算值計(jì)算值 For a = 2 To bFor a = 2 To b If n Mod a = 0 Then Exit For If n Mod a = 0 Then Exit For 判斷判斷a a是否為的因子是否為的因子 Next aNext a If a = b Then If a = b Then 輸出結(jié)果輸出結(jié)果 Text2.Text = Text2.Text = 是素?cái)?shù)是素?cái)?shù) Else Else Text2.Text = Text2.Text = 是合數(shù)是合數(shù),= + Str(a) + x + Str(n,= + Str(a) + x + Str(n a) a) End If End IfEnd SubEnd Sub 流程圖常用符號(hào)（流程圖常用符號(hào)（5框框1線）線）練習(xí)練習(xí)1：P17 問(wèn)題與練習(xí)問(wèn)題與練習(xí) 第第1題題1.有兩個(gè)容器A和B，A容器中裝滿了飲料,B容器中裝滿了調(diào)料,要將A和B容器內(nèi)容交換，如何完成？仿照上面方式，寫(xiě)