人的差異在于業余時間程序的靈魂-算法程序的靈魂-算法人的差異在于業余時間程序的靈魂-算法第二章程序的靈魂－算法C程序設計第二章程序的靈魂－算法著名計算機科學家沃思提出一個公式：程序=數據結構+算法由于采用結構化方法進行程設,且用某一種計算機語言表示,因此還可表示為：程序=數據結構+算法+程序設計方法+語言工具和環境算法:是靈魂，是解決“做什么”、“怎么做”數據結構：是加工對象程序設計方法：程序應當采用的結構化程序設計方法語言：是工具。2．2簡單算法舉例（續）方法二：步驟1：設P=1（P為乘數）。步驟2：設I=2（I為被乘數）。步驟3：使P*I，乘積仍放在變量P中，可表示為P=P*I。步驟4：使I的值加1，可表示為I=I+1。步驟5：判斷：如果I不大于5，返回重新執行步驟3、4、5； 否則算法結束。最后求得的P的值就是5！的值。2．2簡單算法舉例（續）例2.2有50個學生，要求將他們之中成績在80分以上者打印出來．用n表示學生學號,n1代表第一個學生學號,ni代表第i個學生的學號,g代表學生成績,gi代表第i個學生成績．算法如下：S1:1=>iS2:若gi≥80則打印ni和gi，否則不打印S3:i+1=>iS4:若i≤50返回s2，否則算法結束2．3算法的特性（1）有窮性：一個算法應包含有限的操作步驟，而不能是無限的

（2）確定性：算法中每一步的操作步驟都是確定的，不能模棱兩可

（3）有零個或多個輸入：在執行算法時從外界取的必要的信息(4）有一個或多個輸出：即算法的求解(5）有效性：算法中每一個步驟都應當能有效執行2.4怎樣表示一個算法2.4.1用自然語言表示算法算法可以用自然語言描述的。自然語言就是人們日常使用的語言，可以是漢語、英語或其它語言。用自然語言表示通俗易懂，但文字冗長，容易出現歧義。自然語言表示的含義往往不太嚴格，要根據上下文才能準確判斷其含義。此外，用自然語言描述分支和循環的算法，不是很直觀。因此，除了簡單問題，一般不采用自然語言描述算法。

2.4.2用流程圖表示算法用流程圖表示：流程圖是一種傳統的算法表示法，它利用特定的幾何圖形框來代表各種不同性質的操作，用流程線來指示算法的執行方向。由于它簡單直觀，所以應用廣泛。2.4.2用流程圖表示算法美國標準化協會ANSI規定了一些常用的流程圖符號，已為世界各國程序工作者普遍采用注釋框輸入輸出框處理框判斷框流程線連接點起止框一、舉例例1：求5!，其算法流程圖如右所示。例2：將50名學生中成績在80分以上的學生的學號及成績打印出來。2.4.3三種基本結構

和改進的流程圖1.傳統流程圖的弊端傳統流程圖采用流程線指出各框的執行順序，對流程線的使用沒有嚴格限制。因此，使用者可以不受限制地使流程轉來轉去，使流程圖變得毫無規律。

三種基本結構：人們對傳統流程圖進行改進，規定幾種基本的結構，然后由這些基本結構按一定規律組成算法結構，整個算法結構是由上而下地將各個基本結構順序排列起來1)順序結構：是最簡單的一種基本結構，如右圖所示。2)選擇結構：根據給定的條件p選擇執行A或者B。成立不成立成立不成立3)循環結構(1)當型(while)循環結構(2)直到型(Until)循環成立成立不成立不成立3.三種基本結構的共同特點1)只有一個入口2)只有一個出口3)結構內的每一個部分都有機會被執行4)結構內不存在“死循環”已經證明，任何復雜的問題都可以通過由以上三種基本結構順序組成的算法結構來解決。2.4.4用N-S流程圖表示算法將全部算法寫在一個矩形框內，在矩形內還可包含其它從屬于它的框N和S是兩位美國學者的英文名的第一個字母N-S流程圖用以下符號表示：PABAB成立不成立A當p1成立A直到p1成立1.順序結構2.選擇結構3.循環結構N-S圖的使用特點:1、比文字描述更加直觀、形象，易于理解；2、比傳統的流程圖緊湊易畫3、廢除流程線，整個算法結構是由各個基本結構按順序組成。N-S流程圖的上下順序就是執行時的順序。N-S圖表示的算法都是結構化的算法。2.4.4用N-S流程圖表示算法(續)2.4.4用N-S流程圖表示算法(續)例2.11將例2.1的求5!算法用N-S圖表示

2.4.4用N-S流程圖表示算法(續)例2.12將例2.2的算法用N-S圖表示。將50名學生中成績高于80分的學號和成績打印出來。例2.13將判定閏年的算法用圖表示。2.4.4用N-S流程圖表示算法(續)例2.14將例2.4的算法用N-S圖表示。2.4.4用N-S流程圖表示算法(續)例2.15將例2.5判別素數的算法用N-S流程圖表示

2.4.4用N-S流程圖表示算法(續)2.4.5用偽碼表示算法偽代碼—介于自然語言與計算機語言間的文字和符號來描述算法。每一行(或幾行)表示一個操作.它不用圖形符號,因此書寫方便、格式緊湊,比較好懂優點：書寫方便，格式緊湊，易懂，便于向計算機語言過渡。2.4.5用偽碼表示算法(續)例如，“打印x的絕對值”的算法可以用偽代碼表示如下：

IFxispositiveTHEN

printx

ELSE

print–x

也可以用漢字偽代碼，如：

若x為正

打印x

否則

打印–x

也可以中英文混用，如：

IFx為正

printx

ELSE

print–x

例2.16求5!。用偽代碼表示的算法如下：也可以寫成以下形式：BEGIN(算法開始)

1=>t

2=>i

whilei<=5

{t×i=>t

i+1=>i}

printt

END(算法結束)

開始

置t的初值為1

置i的初值為2

當i<=5，執行下面操作：

使t=t×i

使i=i+1

(循環體到此結束)

打印t的值

結束2.4.5用偽碼表示算法(續)例2.17

打印出50個學生中成績高于80分者的學號和成績。

用偽代碼表示算法如下：

BEGIN(算法開始)

1=>i

whilei<=50

{inputniandgi

i+1=>i}

1=>i

whilei<=50

{ifgi≥80printniandgi

i+1=>i}

END(算法結束)

2.4.5用偽碼表示算法(續)例2.18打印2000—2500年中的每一年是否閏年。

用偽代碼表示算法如下：

BEGIN(算法開始)

2000=>y

whiley<=2500

{ify被4整除

ify不被100整除

printy;“是閏年”

else

ify被400整除

printy；“閏年”

else

printy；“非閏年”

endif

endif

else

printy;“非閏年”

endif

y+1=>y

}

END(算法結束)

2.4.5用偽碼表示算法(續)例2.19求1-1/2+1/3-1/4+…+1/99-1/100。

用偽代碼表示的算法如下：

BEGIN(算法開始)

1=>sum

2=>deno

1=>sign

whiledeno<=100

{(-1)×sign=>sign

sign×1/deno=>term

sum+term=>sum

deno+1=>deno

}

printsum

END(算法結束)

2.4.5用偽碼表示算法(續)2.4.6用計算機語言表示算法用計算機解題，就是用計算機實現算法；用計算機語言表示算法必須嚴格遵循所用語言的語法規則。

例2.20將例2.16表示的算法（求5!）用C語言表示main(){inti,t;t=1;i=2;while(i<=5){t=t*i;i=i+1;}printf(“%d”,t);}

例2.21將例2.19表示的算法（求級數的值）用C語言表示main()

{

intsign=1;

floatdeno=2.0，sum=1.0，term;

while(deno<=100)

{sign=-sign;

term=sign/deno;

sum=sum+term;

deno=deno+1;

}

printf("%f"，sum);

}

2.5結構化程序設計方法

自頂向下；逐步細化；模塊化設計；結構化編碼。

盡量避免使用goto語句

設計總框架；考慮各個函數的入口、出口（參數）；完成各個函數。main(){input();processing();output();}voidinput(){};voidoutput(){};voidprocessing(){};