高一課程C語言>程式的靈魂—演算法


程式的靈魂—演算法

一個程式應包括:

Nikiklaus Wirth提出的公式:

資料結構+演算法=程式

更進一步的還認為:

程式=演算法+資料結構+程式設計方法+語言工具和環境

4個方面是一個程式涉及人員所應具備的知識。

本課程的目的是使同學知道怎樣編寫一個C程式,進行編寫程式的初步訓練,因此,只介紹演算法的初步知識。


1、演算法的概念

做任何事情都有一定的步驟。為解決一個問題而採取的方法和步驟,就稱為演算法。

l電腦演算法:電腦能夠執行的演算法。

l電腦演算法可分為兩大類:

n數值運算演算法:求解數值;

n非數值運算演算法:事務管理領域。


2、簡單演算法舉例

【例 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以及其後的S4S5;否則,演算法結束。

如果計算100!只需將 S5: i < 5改成 i < 100即可。

如果該求1×3×5×7×9×11,演算法也只需做很少的改動:

S1: 1t(即 t=1)

S2: 3i(即 t=t*3)

S3: t×it(即 t=t*i)

S4: i+2t(即i=i+2)

S5:i<=11, 返回S3,否則,結束。

該演算法不僅正確,而且是電腦較好的演算法,因為電腦是高速運算的自動機器,實現迴圈輕而易舉。

思考:若將 S5寫成:S5: i11, 返回S3;否則,結束。

【例 2.2】有50個學生,要求將他們之中成績在80分以上者列印出來。

如果,n表示學生學號,ni表示第個學生學號;g表示學生成績,gi表示第個學生成績;

則演算法可表示如下:

S1: 1i

S2: 如果gi80,則列印 nigi,否則不列印

S3: i+1i

S4:i<=50, 返回S2,否則,結束。

【例2.3】判定2000 2500年中的每一年是否閏年,將結果輸出。

潤年的條件:

1)能被4整除,但不能被100整除的年份;

2)能被100整除,又能被400整除的年份;

y為被檢測的年份,則演算法可表示如下:

S1: 2000y

S2:y不能被4整除,則輸出y“不是閏年”,然後轉到S6

S3:y能被4整除,不能被100整除,則輸出y“是閏年”,然後轉到S6

S4:y能被100整除,又能被400整除,輸出y“是閏年” 否則輸出y“不是閏年”,然後轉到S6

S5:輸出y“不是閏年”。

S6:y+1y

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: ni除,得餘數r

S4:如果r=0,表示n能被i整除,則列印n“不是質數”,演算法結束;否則執行S5

S5: i+1i

S6:如果i<=n-1,返回S3;否則列印n“是質數”;然後演算法結束。

改進:

S6:如果 i <=,返回S3;否則列印 n“是質數”然後演算法結束。


3、演算法的特性

對於程式設計人員,必須會設計演算法,並根據演算法寫出程式。


4、怎樣表示一個演算法