本課主題： 算法及算法設(shè)計(jì)要求
教學(xué)目的： 掌握算法的定義及特性，算法設(shè)計(jì)的要求
教學(xué)重點(diǎn)： 算法的特性，算法設(shè)計(jì)要求
教學(xué)難點(diǎn)： 算法設(shè)計(jì)的要求
授課內(nèi)容：
一、算法的定義及特性
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;
}/*上面是一個類似華容道游戲中判斷游戲是否結(jié)束的算法*/
算法是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作；此外，一個算法還具有下列五個重要特性：
2、算法的五個特性：
有窮性 一個算法必須總是（對任何合法的輸入值）在執(zhí)行有窮步之后結(jié)束，且每一步都可在有窮時間內(nèi)完成；
確定性 算法中每一條指令必須有確切的含義，讀者理解時不會產(chǎn)生二義性。有任何條件下，算法只有的一條執(zhí)行路徑，即對于相同的輸入只能得出相同的輸出。
可行性 一個算法是能行的，即算法中描述的操作都是可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)的。
輸入 一個算法有零個或多個的輸入，這些輸入取自于某個特定的對象的集合。
輸出 一個算法有一個或多個的輸出。這些輸出是同輸入有著某些特定關(guān)系的量。
例：
有窮性 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 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;
} /*無輸出的算法沒有任何意義，
二、算法設(shè)計(jì)的要求
1、正確性
算法正確性的四個層次
程序不含語法錯誤。 max(int a,int b,int c)
{
if (a>b)
{if(a>c) return c;
else return a;
}
}
程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足規(guī)格說明要求的結(jié)果。 max(int a,int b,int c)
{
if (a>b)
{if(a>c) return a;
else return c;
}
} /* 8,6,7 */ /* 9,3,2 */
程序?qū)τ诰倪x擇的典型、苛刻而帶有刁難性的幾組輸入數(shù)據(jù)能夠得出滿足規(guī)格說明要求的結(jié)果。 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;
}
}
程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能產(chǎn)生滿足規(guī)格說明要求的結(jié)果。
2、可讀性
3、健壯性
4、效率與低存儲量需求
效率指的是算法執(zhí)行時間。對于解決同一問題的多個算法，執(zhí)行時間短的算法效率高。
存儲量需求指算法執(zhí)行過程中所需要的大存儲空間。
兩者都與問題的規(guī)模有關(guān)。
算法一 算法二
在三個整數(shù)中求大者 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個整型數(shù)空間*/
求100個整數(shù)中大者 同上的算法難寫，難讀 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個整型數(shù)空間*/
三、總結(jié)
1、算法的特性
2、算法設(shè)計(jì)要求：正確性、可讀性、健壯性、效率與低存儲量需求。
教學(xué)目的： 掌握算法的定義及特性，算法設(shè)計(jì)的要求
教學(xué)重點(diǎn)： 算法的特性，算法設(shè)計(jì)要求
教學(xué)難點(diǎn)： 算法設(shè)計(jì)的要求
授課內(nèi)容：
一、算法的定義及特性
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;
}/*上面是一個類似華容道游戲中判斷游戲是否結(jié)束的算法*/
算法是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作；此外，一個算法還具有下列五個重要特性：
2、算法的五個特性：
有窮性 一個算法必須總是（對任何合法的輸入值）在執(zhí)行有窮步之后結(jié)束，且每一步都可在有窮時間內(nèi)完成；
確定性 算法中每一條指令必須有確切的含義，讀者理解時不會產(chǎn)生二義性。有任何條件下，算法只有的一條執(zhí)行路徑，即對于相同的輸入只能得出相同的輸出。
可行性 一個算法是能行的，即算法中描述的操作都是可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)的。
輸入 一個算法有零個或多個的輸入，這些輸入取自于某個特定的對象的集合。
輸出 一個算法有一個或多個的輸出。這些輸出是同輸入有著某些特定關(guān)系的量。
例：
有窮性 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
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;
} /*無輸出的算法沒有任何意義，
二、算法設(shè)計(jì)的要求
1、正確性
算法正確性的四個層次
程序不含語法錯誤。 max(int a,int b,int c)
{
if (a>b)
{if(a>c) return c;
else return a;
}
}
程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足規(guī)格說明要求的結(jié)果。 max(int a,int b,int c)
{
if (a>b)
{if(a>c) return a;
else return c;
}
} /* 8,6,7 */ /* 9,3,2 */
程序?qū)τ诰倪x擇的典型、苛刻而帶有刁難性的幾組輸入數(shù)據(jù)能夠得出滿足規(guī)格說明要求的結(jié)果。 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;
}
}
程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能產(chǎn)生滿足規(guī)格說明要求的結(jié)果。
2、可讀性
3、健壯性
4、效率與低存儲量需求
效率指的是算法執(zhí)行時間。對于解決同一問題的多個算法，執(zhí)行時間短的算法效率高。
存儲量需求指算法執(zhí)行過程中所需要的大存儲空間。
兩者都與問題的規(guī)模有關(guān)。
算法一 算法二
在三個整數(shù)中求大者 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個整型數(shù)空間*/
求100個整數(shù)中大者 同上的算法難寫，難讀 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個整型數(shù)空間*/
三、總結(jié)
1、算法的特性
2、算法設(shè)計(jì)要求：正確性、可讀性、健壯性、效率與低存儲量需求。