2	程序的靈魂—算法	1
2.1	算法的概念	1
2.2	簡單算法舉例	1
2.3	算法的特性	4
2.4	怎樣表示一個算法	4
2.4.1	用自然語言表示算法	4
2.4.2	用流程圖表示算法	4
2.4.3	三種基本結(jié)構(gòu)和改進的流程圖	8
2.4.4	用N-S流程圖表示算法	9
2.4.5	用偽代碼表示算法	10
2.4.6	用計算機語言表示算法	11
2.5	結(jié)構(gòu)化程序設(shè)計方法	11
2	程序的靈魂—算法
一個程序應(yīng)包括：
?	對數(shù)據(jù)的描述。在程序中要指定數(shù)據(jù)的類型和數(shù)據(jù)的組織形式，即數(shù)據(jù)結(jié)構(gòu)（data structure）。
?	對操作的描述。即操作步驟，也就是算法（algorithm）。
Nikiklaus Wirth提出的公式：
數(shù)據(jù)結(jié)構(gòu)+算法=程序
教材認(rèn)為：
程序=算法+數(shù)據(jù)結(jié)構(gòu)+程序設(shè)計方法+語言工具和環(huán)境
這4個方面是一個程序涉及人員所應(yīng)具備的知識。
本課程的目的是使同學(xué)知道怎樣編寫一個C程序，進行編寫程序的初步訓(xùn)練，因此，只介紹算法的初步知識。
2.1	算法的概念
做任何事情都有一定的步驟。為解決一個問題而采取的方法和步驟，就稱為算法。
?	計算機算法：計算機能夠執(zhí)行的算法。
?	計算機算法可分為兩大類：
?	數(shù)值運算算法：求解數(shù)值；
?	非數(shù)值運算算法：事務(wù)管理領(lǐng)域。
2.2	簡單算法舉例
【例2.1】求1×2×3×4×5。
最原始方法：
步驟1：先求1×2，得到結(jié)果2。
步驟2：將步驟1得到的乘積2乘以3，得到結(jié)果6。
步驟3：將6再乘以4，得24。
步驟4：將24再乘以5，得120。
這樣的算法雖然正確，但太繁。
改進的算法：
S1: 使t=1
S2: 使i=2
S3: 使t×i, 乘積仍然放在在變量t中，可表示為t×i→t
S4: 使i的值+1，即i+1→i
S5: 如果i≤5, 返回重新執(zhí)行步驟S3以及其后的S4和S5；否則，算法結(jié)束。
如果計算100！只需將S5:若i≤5改成i≤100即可。
如果該求1×3×5×7×9×11，算法也只需做很少的改動：
S1: 1→t
S2: 3→i
S3: t×i→t
S4: i+2→t
S5:若i≤11, 返回S3，否則，結(jié)束。
該算法不僅正確，而且是計算機較好的算法，因為計算機是高速運算的自動機器，實現(xiàn)循環(huán)輕而易舉。
思考：若將 S5寫成：S5:若i＜11, 返回S3;否則，結(jié)束。
【例2.2】有50個學(xué)生，要求將他們之中成績在80分以上者打印出來。
如果，n表示學(xué)生學(xué)號，ni表示第個學(xué)生學(xué)號；g表示學(xué)生成績，gi表示第個學(xué)生成績；
則算法可表示如下：
S1: 1→i
S2: 如果gi≥80，則打印ni和gi，否則不打印
S3: i+1→i
S4:若i≤50, 返回S2，否則，結(jié)束。
【例2.3】判定2000 — 2500年中的每一年是否閏年，將結(jié)果輸出。
潤年的條件：
1)	能被4整除，但不能被100整除的年份；
2)	能被100整除，又能被400整除的年份；
設(shè)y為被檢測的年份，則算法可表示如下：
S1: 2000→y
S2:若y不能被4整除，則輸出y“不是閏年”，然后轉(zhuǎn)到S6
S3:若y能被4整除，不能被100整除，則輸出y“是閏年”，然后轉(zhuǎn)到S6
S4:若y能被100整除，又能被400整除，輸出y“是閏年” 否則輸出y“不是閏年”，然后轉(zhuǎn)到S6
S5:輸出y“不是閏年”。
S6:y+1→y
S7:當(dāng)y≤2500時, 返回S2繼續(xù)執(zhí)行，否則，結(jié)束。
 
【例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；否則，結(jié)束。
【例2.5】對一個大于或等于3的正整數(shù)，判斷它是不是一個素數(shù)。
算法可表示如下：
S1: 輸入n的值
S2: i=2
S3: n被i除，得余數(shù)r
S4:如果r=0，表示n能被i整除，則打印n“不是素數(shù)”，算法結(jié)束；否則執(zhí)行S5
S5: i+1→i 
S6:如果i≤n-1，返回S3；否則打印n“是素數(shù)”；然后算法結(jié)束。
改進：
S6:如果i≤ ，返回S3；否則打印n“是素數(shù)”;然后算法結(jié)束。
2.3	算法的特性
?	有窮性：一個算法應(yīng)包含有限的操作步驟而不能是無限的。  
?	確定性：算法中每一個步驟應(yīng)當(dāng)是確定的，而不能應(yīng)當(dāng)是含糊的、模棱兩可的。
?	有零個或多個輸入。
?	有一個或多個輸出。
?	有效性：算法中每一個步驟應(yīng)當(dāng)能有效地執(zhí)行，并得到確定的結(jié)果。
對于程序設(shè)計人員，必須會設(shè)計算法，并根據(jù)算法寫出程序。
2.4	怎樣表示一個算法
2.4.1	用自然語言表示算法
除了很簡單的問題，一般不用自然語言表示算法。
2.4.2	用流程圖表示算法
流程圖表示算法，直觀形象，易于理解。
 
【例2.6】將例2.1求5!的算用流程圖表示。
 
【例2.7】將例2.2的算用流程圖表示。
 
【例2.8】將例2.3判定閏年的算用流程圖表示。
 
【例2.9】將例2.4求 的算用流程圖表示。
一個流程圖包括：
1.	表示相應(yīng)操作的框；
2.	帶箭頭的流程線；
3.	框內(nèi)外必要的文字說明。
2.4.3	三種基本結(jié)構(gòu)和改進的流程圖
1.	順序結(jié)構(gòu)：
 
2.	選擇結(jié)構(gòu)：
 
 
3.	循環(huán)結(jié)構(gòu)
 
 

三種基本結(jié)構(gòu)的共同特點：
?	只有一個入口；
?	只有一個出口；
?	結(jié)構(gòu)內(nèi)的每一部分都有機會被執(zhí)行到；
?	結(jié)構(gòu)內(nèi)不存在“死循環(huán)”。
2.4.4	用N-S流程圖表示算法
1973年美國學(xué)者提出了一種新型流程圖：N-S流程圖。
順序結(jié)構(gòu)：
 
選擇結(jié)構(gòu)：
 
循環(huán)結(jié)構(gòu)：
 
 
2.4.5	用偽代碼表示算法
偽代碼使用介于自然語言和計算機語言之間的文字和符號來描述算法。
2.4.6	用計算機語言表示算法
?	我們的任務(wù)是用計算機解題，就是用計算機實現(xiàn)算法；
?	用計算機語言表示算法必須嚴(yán)格遵循所用語言的語法規(guī)則。
【例2.20】求1×2×3×4×5用C語言表示。
main()
{int i,t;
 t=1;
 i=2;
 while(i<=5)
{t=t*i;
i=i+1;
}
 printf(“%d”,t);
} 
 
【例2.21】求級數(shù)的值。
main()
{
int sigh=1;
float deno=2.0,sum=1.0,term;
while(deno<=100)
{ sigh= -sigh; 
term= sigh/ deno;
sum=sum+term;
deno=deno+1;
}
 printf(“%f”,sum);
}
 
2.5	結(jié)構(gòu)化程序設(shè)計方法
?	自頂向下；
?	逐步細(xì)化；
?	模塊化設(shè)計；
?	結(jié)構(gòu)化編碼。