本課主題： 算法及算法設計要求

教學目的： 掌握算法的定義及特性，算法設計的要求

教學重點： 算法的特性，算法設計要求

教學難點： 算法設計的要求

授課內容：

一、算法的定義及特性

1、定義：

ispass(int num[4][4])

{ int i,j;
for(i=0;i<4;i++)

for(j=0;j<4;j++)

if(num[i][j]!=i*4+j+1)/*一條指令，多個操作*/

return 0;

return 1;
}/*上面是一個類似華容道游戲中判斷游戲是否結束的算法*/

算法是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作；此外，一個算法還具有下列五個重要特性：

2、算法的五個特性：

有窮性	一個算法必須總是（對任何合法的輸入值）在執行有窮步之后結束，且每一步都可在有窮時間內完成；
確定性	算法中每一條指令必須有確切的含義，讀者理解時不會產生二義性。有任何條件下，算法只有唯一的一條執行路徑，即對于相同的輸入只能得出相同的輸出。
可行性	一個算法是能行的，即算法中描述的操作都是可以通過已經實現的基本運算執行有限次來實現的。
輸入	一個算法有零個或多個的輸入，這些輸入取自于某個特定的對象的集合。
輸出	一個算法有一個或多個的輸出。這些輸出是同輸入有著某些特定關系的量。

例：

有窮性	haha() {/*only a joke,do nothing.*/ } main() {printf("請稍等...您將知道世界的未日..."); while(1) haha(); }
確定性	float average(int *a,int num) {int i;long sum=0; for(i=0;i<num;i++) sum+=*(a++); return sum/num; } main() {int score[10]={1,2,3,4,5,6,7,8,9,0}; printf("%f",average(score,10); }
可行性
輸入
輸出	getsum(int num) { int i,sum=0; for(i=1;i<=num;i++) sum+=i; } /*無輸出的算法沒有任何意義，

二、算法設計的要求

1、正確性

算法正確性的四個層次
程序不含語法錯誤。	max(int a,int b,int c) { if (a>b) {if(a>c) return c; else return a; } }
程序對于幾組輸入數據能夠得出滿足規格說明要求的結果。	max(int a,int b,int c) { if (a>b) {if(a>c) return a; else return c; } } /* 8,6,7 */ /* 9,3,2 */
程序對于精心選擇的典型、苛刻而帶有刁難性的幾組輸入數據能夠得出滿足規格說明要求的結果。	max(int a,int b,int c) { if (a>b) {if(a>c) return a; else return c; } else {if(b>c) return b; else return c; } }
程序對于一切合法的輸入數據都能產生滿足規格說明要求的結果。

2、可讀性

3、健壯性

4、效率與低存儲量需求

效率指的是算法執行時間。對于解決同一問題的多個算法，執行時間短的算法效率高。

存儲量需求指算法執行過程中所需要的最大存儲空間。

兩者都與問題的規模有關。

	算法一	算法二
在三個整數中求最大者	max(int a,int b,int c) {if (a>b) {if(a>c) return a; else return c; } else {if(b>c) return b; else return c; }/*無需額外存儲空間，只需兩次比較*/	max(int a[3]) {int c,int i; c=a[0]; for(i=1;i<3;i++) if (a[i]>c) c=a[i]; return c; } /*需要兩個額外的存儲空間，兩次比較，至少一次賦值*/ /*共需5個整型數空間*/
求100個整數中最大者	同上的算法難寫，難讀	max(int a[100]) {int c,int i; c=a[0]; for(i=1;i<100;i++) if (a[i]>c) c=a[i]; return c; } /*共需102個整型數空間*/

三、總結

1、算法的特性

2、算法設計要求：正確性、可讀性、健壯性、效率與低存儲量需求。