一個程式應包括:
l對資料的描述。在程式中要指定資料的類型和資料的組織形式,即資料結構(data structure)。
l對操作的描述。即操作步驟,也就是演算法(algorithm)。
Nikiklaus Wirth提出的公式:
資料結構+演算法=程式
更進一步的還認為:
程式=演算法+資料結構+程式設計方法+語言工具和環境
這4個方面是一個程式涉及人員所應具備的知識。
本課程的目的是使同學知道怎樣編寫一個C程式,進行編寫程式的初步訓練,因此,只介紹演算法的初步知識。
做任何事情都有一定的步驟。為解決一個問題而採取的方法和步驟,就稱為演算法。
l電腦演算法:電腦能夠執行的演算法。
l電腦演算法可分為兩大類:
n數值運算演算法:求解數值;
n非數值運算演算法:事務管理領域。
【例 2.1】求1×2×3×4×5。
最原始方法:
步驟 1:先求1×2,得到結果2。
步驟 2:將步驟1得到的乘積2乘以3,得到結果6。
步驟 3:將6再乘以4,得24。
步驟 4:將24再乘以5,得120。
這樣的演算法雖然正確,但太繁複。
改進的演算法:
S1: 使 t=1
S2: 使 i=2
S3: 使 t × i, 乘積仍然放在在變數 t 中,可表示為 t × i → t (即 t=t*i)
S4: 使 i 的值 +1,即 i +1→ i(即 i=i+1)
S5: 如果 i < 5, 返回重新執行步驟S3以及其後的S4和S5;否則,演算法結束。
如果計算100!只需將 S5: 若i < 5改成 i < 100即可。
如果該求1×3×5×7×9×11,演算法也只需做很少的改動:
S1: 1→t(即 t=1)
S2: 3→i(即 t=t*3)
S3: t×i→t(即 t=t*i)
S4: i+2→t(即i=i+2)
S5:若i<=11, 返回S3,否則,結束。
該演算法不僅正確,而且是電腦較好的演算法,因為電腦是高速運算的自動機器,實現迴圈輕而易舉。
思考:若將 S5寫成:S5: 若i<11, 返回S3;否則,結束。
【例 2.2】有50個學生,要求將他們之中成績在80分以上者列印出來。
如果,n表示學生學號,ni表示第個學生學號;g表示學生成績,gi表示第個學生成績;
則演算法可表示如下:
S1: 1→i
S2: 如果gi≥80,則列印 ni和 gi,否則不列印
S3: i+1→i
S4:若i<=50, 返回S2,否則,結束。
【例2.3】判定2000 — 2500年中的每一年是否閏年,將結果輸出。
潤年的條件:
1)能被4整除,但不能被100整除的年份;
2)能被100整除,又能被400整除的年份;
設 y為被檢測的年份,則演算法可表示如下: S1: 2000→y S2:若y不能被4整除,則輸出y“不是閏年”,然後轉到S6 S3:若y能被4整除,不能被100整除,則輸出y“是閏年”,然後轉到S6 S4:若y能被100整除,又能被400整除,輸出y“是閏年” 否則輸出y“不是閏年”,然後轉到S6 S5:輸出y“不是閏年”。 S6:y+1→y S7:當y<=2500時, 返回S2繼續執行,否則,結束。 |
【例2.4】求。
演算法可表示如下: S1: sigh=1 S2: sum=1 S3: deno=2 S4: sigh=(-1)×sigh S5: term= sigh×(1/deno ) S6: term=sum+term S7: deno= deno +1 S8:若deno<=100,返回S4;否則,結束。 |
【例2.5】對一個大於或等於3的正整數,判斷它是不是一個質數。
演算法可表示如下: S1: 輸入n的值 S2: i=2 S3: n被i除,得餘數r S4:如果r=0,表示n能被i整除,則列印n“不是質數”,演算法結束;否則執行S5 S5: i+1→i S6:如果i<=n-1,返回S3;否則列印n“是質數”;然後演算法結束。 |
改進:
S6:如果 i <=,返回S3;否則列印 n“是質數”; 然後演算法結束。
l有窮性:一個演算法應包含有限的操作步驟而不能是無限的。
l確定性:演算法中每一個步驟應當是確定的,而不能應當是含糊的、模棱兩可的。
l有零個或多個輸入。
l 有一個或多個輸出。
l有效性:演算法中每一個步驟應當能有效地執行,並得到確定的結果。
對於程式設計人員,必須會設計演算法,並根據演算法寫出程式。
除了很簡單的問題,一般不用自然語言表示演算法。
流程圖表示演算法,直觀形象,易於理解。詳細內容,請參閱下節《流程圖說明》。