計算思維-05-程序設(shè)計基礎(chǔ)

第5章

程序設(shè)計基礎(chǔ)5.1程序設(shè)計的概念5.2結(jié)構(gòu)化程序設(shè)計的基本原則

5.3程序設(shè)計的基本控制結(jié)構(gòu)5.4程序設(shè)計的基本方法5.5程序設(shè)計語言5.1程序設(shè)計的概念5.1.1什么是程序

簡單地說，程序可以看作是對一系列動作的執(zhí)行過程的描述。

計算機程序，是指為了得到某種結(jié)果而由計算機等具有信息處理能力的裝置執(zhí)行的代碼化指令序列。5.1程序設(shè)計的概念5.1.1什么是程序

程序的幾個性質(zhì)：目的性。分步性。有限性?？刹僮餍?。有序性。5.1程序設(shè)計的概念5.1.2指令和指令系統(tǒng)

指令由兩部分組成，一部分叫操作碼，它表示計算機該做什么操作；另一部分叫操作數(shù)，它表示計算機的操作對象。

計算機所能執(zhí)行的全部操作指令被稱為指令系統(tǒng)，不同類型的計算機系統(tǒng)有不同的指令系統(tǒng)。5.1程序設(shè)計的概念5.1.3文檔

文檔是軟件開發(fā)、使用和維護過程中必不可少的資料。5.1程序設(shè)計的概念5.1.4程序設(shè)計文檔是軟件開發(fā)、使用和維護過程中必不可少的資料。5.1程序設(shè)計的概念5.1.4程序設(shè)計1.為什么要學(xué)習(xí)程序設(shè)計5.1程序設(shè)計的概念5.1.4程序設(shè)計2.程序設(shè)計的步驟分析問題，確定解決方案建立數(shù)學(xué)模型確定算法（算法設(shè)計）編寫源程序程序調(diào)試整理資料5.2結(jié)構(gòu)化程序設(shè)計的基本原則5.2.1 模塊化程序設(shè)計概念模塊模塊化5.2結(jié)構(gòu)化程序設(shè)計的基本原則5.2.2

程序設(shè)計的風(fēng)格1.程序設(shè)計的風(fēng)格2.

程序設(shè)計語言運用的風(fēng)格程序文本的風(fēng)格輸入/輸出的風(fēng)格5.2結(jié)構(gòu)化程序設(shè)計的基本原則5.2.3 結(jié)構(gòu)化程序設(shè)計的原則1.自頂向下2.逐步求精模塊化限制使用GoTo語句5.2結(jié)構(gòu)化程序設(shè)計的基本原則5.2.4 面向?qū)ο蟮某绦蛟O(shè)計1.面向?qū)ο蠹夹g(shù)的基本概念2.面向?qū)ο蠹夹g(shù)的特點模塊化5.3程序設(shè)計的基本控制結(jié)構(gòu)5.3.1 順序結(jié)構(gòu)5.3程序設(shè)計的基本控制結(jié)構(gòu)5.3.2 選擇（分支）結(jié)構(gòu)1.兩路分支選擇結(jié)構(gòu)5.3程序設(shè)計的基本控制結(jié)構(gòu)5.3.2 選擇（分支）結(jié)構(gòu)2.多路分支選擇結(jié)構(gòu)5.3程序設(shè)計的基本控制結(jié)構(gòu)5.3.3 循環(huán)結(jié)構(gòu)1.“當(dāng)”型循環(huán)5.3程序設(shè)計的基本控制結(jié)構(gòu)5.3.3 循環(huán)結(jié)構(gòu)2.“直到”型循環(huán)5.4程序設(shè)計的基本方法【例5.4】 雞兔同籠問題：雞和兔子被放在同一個籠中，現(xiàn)在已知雞和兔子的總頭數(shù)和總腳數(shù)。編程序，計算籠子中雞和兔子各有多少只?5.4程序設(shè)計的基本方法【例5.4】 雞兔同籠問題【分析】假如我們用Head表示總頭數(shù)，F(xiàn)oot表示總腳數(shù) 用Cock表示雞的個數(shù)，Rabbit表示兔子的個數(shù)則有：Cock+Rabbit=Head ①2Cock+4Rabbit=Foot ②5.4程序設(shè)計的基本方法【例5.4】 雞兔同籠問題【分析】計算機不會直接處理這樣的二元一次方程組，必須經(jīng)過變形：②-①×2得：Rabbit=（Foot-2Head）/2 ③① 以等價的變形為：

Cock=Head–Rabbit ④5.4程序設(shè)計的基本方法【例5.4】 雞兔同籠問題【偽碼】Begin：Input("總頭數(shù)")；Head//輸入原始數(shù)據(jù)

Input("總腳數(shù)")；Foot//輸入原始數(shù)據(jù)

Rabbit←(Foot-2*Head)/2//計算兔子的個數(shù)

Cock←Head–Rabbit//計算雞的個數(shù)

PrintCock//輸出計算結(jié)果PrintRabbit//輸出計算結(jié)果End5.4程序設(shè)計的基本方法【例5.7】 相傳古代印度國王舍罕要褒獎他聰明能干的宰相（國際象棋發(fā)明者）達依爾。國王問達依爾需要什么，達依爾說：國王只要在國際象棋棋盤上的第一格放一粒麥子，第二格放兩粒麥子，第三格放四粒麥子，以后都按此比例每一格都是前一格的兩倍，一直放到第64格為止，我將感激不盡！國王一聽馬上便答應(yīng)下來。結(jié)果，他讓扛過來的麥子，不一會兒就用完了。國王很納悶，這到底是怎么回事呢？我們下面編寫程序，讓計算機來算一算這筆帳，假定1.42×108粒小麥/m3，計算一下這么多小麥有多大的體積。5.4程序設(shè)計的基本方法【例5.7】 【分析】根據(jù)題目的描述，我們知道：第一格放1粒麥子，1=20第二格是第一格的兩倍，2×1=2=21第三格是第二格的兩倍，2×2=4=22第四格是第三格的兩倍，2×4=8=23……第64格是第63格的兩倍，2×262=2635.4程序設(shè)計的基本方法【例5.7】 【偽碼】Begin：For(i=0To63) //0~63計數(shù){S←S+2^i //對每一格中的麥子數(shù)向S求和

}PrintS //輸出麥子的總數(shù)PrintS/1.42E8 //輸出所占的體積End5.4程序設(shè)計的基本方法【例5.7】 計算機在進行冪指數(shù)的運算時，相對于連乘運算要慢很多。因此在計算時我們常常用連乘替代冪指數(shù)！5.4程序設(shè)計的基本方法【例5.7】 【偽碼】Begin：K←1 //設(shè)置第1格中的麥子數(shù)S←S+K //對第1格中的麥子數(shù)向S求和For(i=1To63) //1~63計數(shù)（第1格已經(jīng)累加過了）{K←2*K //用累乘的方法計算當(dāng)前格中的麥子數(shù)S←S+K //對當(dāng)前格中的麥子數(shù)向S求和}PrintS //輸出麥子的總數(shù)PrintS/1.42E8 //輸出所占的體積End5.4程序設(shè)計的基本方法【例5.10】 一個猴子摘了一堆桃子。第一天吃了一半，又多吃一個。第二天還是吃了一半，又多吃一個。它每天如此，到第5天時只剩一個桃子了。編寫程序，計算猴子第一天共摘了多少個桃子？5.4程序設(shè)計的基本方法【例5.10】 【分析】假如我們用Ti表示第i天的桃子數(shù)根據(jù)題目描述，第5天剩1個桃子，T5=1第4天剩下的桃子數(shù)，T4=2×(T5+1)

……第1天剩下的桃子數(shù)，T1=2×(T2+1)因此我們得到：Tn=2×(Tn+1+1)(n=4，3，2，1)假設(shè)程序中我們用T表示每天的桃子數(shù)。用循環(huán)控制執(zhí)行四次：T=2*(T+1)即可得到要求的結(jié)果。5.4程序設(shè)計的基本方法【例5.10】 【偽碼】Begin：T←1 //T的初值為1(第5天時只剩一個桃子了)For(i=4To1，-1){T←2*(T+1) //迭代計算}PrintT //輸出計算結(jié)果End5.4程序設(shè)計的基本方法【例5.11】 有數(shù)據(jù)：3，7，2，9，5，1，6。編寫程序，將其按升序排列。5.4程序設(shè)計的基本方法【例5.11】 【分析】直接排序法直接排序法的具體方法是，先用第1個數(shù)據(jù)與剩下第2到第N這N-1個數(shù)據(jù)分別比較：用第1個數(shù)據(jù)與第2個數(shù)據(jù)比較，如果它們之間的關(guān)系不符合升序要求，就交換它們的值。接下來，第1個數(shù)據(jù)與第3個數(shù)據(jù)比較，……，直到第一個數(shù)據(jù)與第N數(shù)據(jù)比較完為止。這時，第一個數(shù)據(jù)就是該序列中最小的一個數(shù)據(jù)。然后再用第2個數(shù)據(jù)與剩下第3到第N這N-2個數(shù)據(jù)分別比較。一直下去，直到用第N-1個數(shù)據(jù)與第N個數(shù)據(jù)比較完為止。5.4程序設(shè)計的基本方法【例5.11】 【偽碼】在此，我們只給出排序的偽碼(假設(shè)N個數(shù)據(jù)已經(jīng)存放在D數(shù)組中)：……For(i=1ToN–1) //外循環(huán){

For(j=i+1ToN) //內(nèi)循環(huán){

If(D(i)>D(j)) //i數(shù)據(jù)與j數(shù)據(jù)比較

{ //條件為TrueD(i)與D(j)數(shù)據(jù)交換

}}}5.4程序設(shè)計的基本方法【例5.11】 【偽碼】在此，我們只給出排序的偽碼(假設(shè)N個數(shù)據(jù)已經(jīng)存放在D數(shù)組中)：For(i=1ToN){PrintD(i) //輸出已經(jīng)排好的序列}……5.4程序設(shè)計的基本方法【例5.12】 編寫程序，查找某個關(guān)鍵值是否在指定數(shù)組中。5.4程序設(shè)計的基本方法【例5.12】 編寫程序，查找某個關(guān)鍵值是否在指定數(shù)組中?！痉治觥拷夥?：對分檢索對分檢索只能用于有序序列。對分檢索的算法思想是：每次都取數(shù)據(jù)區(qū)間的中間值，并且通過這個中間值與關(guān)鍵值比較，來判斷是否找到。如果沒有找到，再比較這個中間值與關(guān)鍵值的大小，從而決定關(guān)鍵值可能存在的新區(qū)間。由于這個新區(qū)間是由原區(qū)間“對分”得到的，因此這種方法被叫做“對分檢索”。5.4程序設(shè)計的基本方法【例5.12】 編寫程序，查找某個關(guān)鍵值是否在指定數(shù)組中。【偽碼】我們只給出檢索的偽碼(假設(shè)N個有序數(shù)據(jù)已經(jīng)存放在D數(shù)組中)：……Input("一個數(shù)")；Key //輸入要檢索的關(guān)鍵值Sign←False //給出檢索標(biāo)記變量（邏輯類型）的初值LeftData←1 //給出檢索區(qū)間的左邊界值初值RightData←N //給出檢索區(qū)間的右邊界值初值5.4程序設(shè)計的基本方法【例5.12】 編寫程序，查找某個關(guān)鍵值是否在指定數(shù)組中?！緜未a】我們只給出檢索的偽碼(假設(shè)N個有序數(shù)據(jù)已經(jīng)存放在D數(shù)組中)：DoWhile(RightData>=LeftDataAndNotSign)//判斷檢索是否結(jié)束{MidData←(LeftData+RightData)/2 //計算中間項下標(biāo)

If(D(MidData)=Key) //比較關(guān)鍵值{ //存在一個值與關(guān)鍵值相匹配

Sign←True //修改檢索標(biāo)記變量的值ExitDo //退出循環(huán)5.4程序設(shè)計的基本方法【例5.12】 編寫程序，查找某個關(guān)鍵值是否在指定數(shù)組中。【偽碼】我們只給出檢索的偽碼(假設(shè)N個有序數(shù)據(jù)已經(jīng)存放在D數(shù)組中)：Else //當(dāng)前值與關(guān)鍵值不匹配

If(D(MidData)>Key) //判斷關(guān)鍵值可能的區(qū)間

{

RightData←MidData–1 //右邊界值左移

Else

LeftData←MidData+1 //左邊界值右移

}

}}5.4程序設(shè)計的基本方法【例5.12】 編寫程序，查找某個關(guān)鍵值是否在指定數(shù)組中?！緜未a】我們只給出檢索的偽碼(假設(shè)N個有序數(shù)據(jù)已經(jīng)存放在D數(shù)組中)：If(Sign) //判斷檢索標(biāo)記變量的值{ //條件為TruePrint"關(guān)鍵值在第"&i&"個位置上。"Else //條件為FalsePrint"關(guān)鍵值不在序列中。"}……5.4程序設(shè)計的基本方法【例5.14】 傳說印度教的主神梵天創(chuàng)造世界時，在印度北部佛教勝地貝拿勒斯圣廟里，安放了一塊黃銅板，板上插著3根針，在其中一根針上自上而下的放著由小到大的64個金盤。這就是所謂的梵塔（Hanoi）。梵天要僧侶們堅持不渝地按下面規(guī)則把64個盤子移到另一根針上：

1.一次只能移一個盤子；

2.盤子只許在3根針上存放；

3.永遠都是小盤子在下面大盤子在上面。梵天稱，當(dāng)把他創(chuàng)造世界時所安放的64個盤子全部移到另一根針上之時，就是世界的毀滅之日。5.4程序設(shè)計的基本方法【例5.14】 【分析】假設(shè)三根針分別為：1，2，3(分別用A，B，C表示)。我們現(xiàn)在要將N個盤子從1號針移到3號針上，在移動的過程中可以借助2號針。我們將這個過程定義為：Hanoi(N,A,C,B)。5.4程序設(shè)計的基本方法【例5.14】 【分析】我們簡化這個操作。將N個盤子分成兩部分：最下面的一個和上面的N-1個。這兩部分的移動可以很方便的實現(xiàn)：將N-1個盤子從1號針移到2號針上，將最下面的一個盤子從1號針移到3號針上，再將N-1個盤子從2號針移到3號針上。即：Hanoi(N-1,A,B,C)

A→CHanoi(N-1,B,C,A)5.4程序設(shè)計的基本方法【例5.14】 【分析】我們對上面移動過程中的N-1個盤子也做同樣的操作：將他們分成兩部分：最下面的一個和上面的N-2個，移動這兩部分。重復(fù)這個操作，直到所有的盤子全部移動完畢為止。這種方法叫遞歸。5.4程序設(shè)計的基本方法【例5.14】 【分析】也就是說，我們