程序的靈魂—算法


一個程序應包括：

對數據的描述。在程序中要指定數據的類型和數據的組織形式，即數據結構（data?structure）。

對操作的描述。即操作步驟，也就是算法（algorithm）。

Nikiklaus?Wirth提出的公式：

數據結構+算法=程序

教材認為：

程序=算法+數據結構+程序設計方法+語言工具和環境

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

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

2.1?算法的概念

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

計算機算法：計算機能夠執行的算法。

計算機算法可分為兩大類：

數值運算算法：求解數值；

非數值運算算法：事務管理領域。

有喜歡C語言或者想要學習C語言的小伙伴可以加一下我自己的C語言交流群815393895

2.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×it

S4:?使i的值+1，即i+1i

S5:?如果i≤5,?返回重新執行步驟S3以及其后的S4和S5；否則，算法結束。

如果計算100！只需將S5:若i≤5改成i≤100即可。

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

S1:?1t

S2:?3i

S3:?t×it

S4:?i+2t

S5:若i≤11,?返回S3，否則，結束。

該算法不僅正確，而且是計算機較好的算法，因為計算機是高速運算的自動機器，實現循環輕而易舉。

思考：若將?S5寫成：S5:若i＜11,?返回S3;否則，結束。

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

如果，n表示學生學號，ni表示第個學生學號；g表示學生成績，gi表示第個學生成績；

則算法可表示如下：

S1:?1i

S2:?如果gi≥80，則打印ni和gi，否則不打印

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:?n被i除，得余數r

S4:如果r=0，表示n能被i整除，則打印n“不是素數”，算法結束；否則執行S5

S5:?i+1i

S6:如果i≤n-1，返回S3；否則打印n“是素數”；然后算法結束。

改進：

S6:如果i≤?，返回S3；否則打印n“是素數”;然后算法結束。

2.3?算法的特性

有窮性：一個算法應包含有限的操作步驟而不能是無限的。

確定性：算法中每一個步驟應當是確定的，而不能應當是含糊的、模棱兩可的。

有零個或多個輸入。

有一個或多個輸出。

有效性：算法中每一個步驟應當能有效地執行，并得到確定的結果。

對于程序設計人員，必須會設計算法，并根據算法寫出程序。

2.4?怎樣表示一個算法

2.4.1?用自然語言表示算法

除了很簡單的問題，一般不用自然語言表示算法。

2.4.5?用偽代碼表示算法

偽代碼使用介于自然語言和計算機語言之間的文字和符號來描述算法。

2.4.6?用計算機語言表示算法

??我們的任務是用計算機解題，就是用計算機實現算法；

??用計算機語言表示算法必須嚴格遵循所用語言的語法規則。

【例2.20】求1×2×3×4×5用C語言表示。

main()

printf(“%d”,t);

}

【例2.21】求級數的值。

main()

{

int?sigh=1;

floatdeno=2.0,sum=1.0,term;

while(deno

{?sigh=?-sigh;

term=?sigh/?deno;

sum=sum+term;

deno=deno+1;

}

printf(“%f”,sum);

}

2.5?結構化程序設計方法

自頂向下；

逐步細化；

模塊化設計；

結構化編碼。

算法是程序的靈魂，也是C語言的靈魂。C語言是面向過程的編程語言，算法對C語言的作用尤為重要。這是C語言的基礎，小編希望大家在入門的時候，一定要打好基礎，往后的學習才事半功倍。