本課主題： 算法及算法設(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)/*一條指令，多個(gè)操作*/
return 0;
return 1;
}/*上面是一個(gè)類(lèi)似華容道游戲中判斷游戲是否結(jié)束的算法*/
算法是對(duì)特定問(wèn)題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作；此外，一個(gè)算法還具有下列五個(gè)重要特性：
2、算法的五個(gè)特性：
有窮性 一個(gè)算法必須總是（對(duì)任何合法的輸入值）在執(zhí)行有窮步之后結(jié)束，且每一步都可在有窮時(shí)間內(nèi)完成；
確定性 算法中每一條指令必須有確切的含義，讀者理解時(shí)不會(huì)產(chǎn)生二義性。有任何條件下，算法只有的一條執(zhí)行路徑，即對(duì)于相同的輸入只能得出相同的輸出。
可行性 一個(gè)算法是能行的，即算法中描述的操作都是可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來(lái)實(shí)現(xiàn)的。
輸入 一個(gè)算法有零個(gè)或多個(gè)的輸入，這些輸入取自于某個(gè)特定的對(duì)象的集合。
輸出 一個(gè)算法有一個(gè)或多個(gè)的輸出。這些輸出是同輸入有著某些特定關(guān)系的量。
例：
有窮性 haha()
{/*only a joke,do nothing.*/
}
main()
{printf("請(qǐng)稍等...您將知道世界的未日...");
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;
} /*無(wú)輸出的算法沒(méi)有任何意義，
二、算法設(shè)計(jì)的要求
1、正確性
算法正確性的四個(gè)層次
程序不含語(yǔ)法錯(cuò)誤。 max(int a,int b,int c)
{
if (a>b)
{if(a>c) return c;
else return a;
}
}
程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足規(guī)格說(shuō)明要求的結(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ī)格說(shuō)明要求的結(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ī)格說(shuō)明要求的結(jié)果。
2、可讀性
3、健壯性
4、效率與低存儲(chǔ)量需求
效率指的是算法執(zhí)行時(shí)間。對(duì)于解決同一問(wèn)題的多個(gè)算法，執(zhí)行時(shí)間短的算法效率高。
存儲(chǔ)量需求指算法執(zhí)行過(guò)程中所需要的大存儲(chǔ)空間。
兩者都與問(wèn)題的規(guī)模有關(guān)。
算法一 算法二
在三個(gè)整數(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;
}/*無(wú)需額外存儲(chǔ)空間，只需兩次比較*/ 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;
}
/*需要兩個(gè)額外的存儲(chǔ)空間，兩次比較，至少賦值*/
/*共需5個(gè)整型數(shù)空間*/
求100個(gè)整數(shù)中大者 同上的算法難寫(xiě)，難讀 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個(gè)整型數(shù)空間*/
三、總結(jié)
1、算法的特性
2、算法設(shè)計(jì)要求：正確性、可讀性、健壯性、效率與低存儲(chǔ)量需求。
教學(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)/*一條指令，多個(gè)操作*/
return 0;
return 1;
}/*上面是一個(gè)類(lèi)似華容道游戲中判斷游戲是否結(jié)束的算法*/
算法是對(duì)特定問(wèn)題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作；此外，一個(gè)算法還具有下列五個(gè)重要特性：
2、算法的五個(gè)特性：
有窮性 一個(gè)算法必須總是（對(duì)任何合法的輸入值）在執(zhí)行有窮步之后結(jié)束，且每一步都可在有窮時(shí)間內(nèi)完成；
確定性 算法中每一條指令必須有確切的含義，讀者理解時(shí)不會(huì)產(chǎn)生二義性。有任何條件下，算法只有的一條執(zhí)行路徑，即對(duì)于相同的輸入只能得出相同的輸出。
可行性 一個(gè)算法是能行的，即算法中描述的操作都是可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來(lái)實(shí)現(xiàn)的。
輸入 一個(gè)算法有零個(gè)或多個(gè)的輸入，這些輸入取自于某個(gè)特定的對(duì)象的集合。
輸出 一個(gè)算法有一個(gè)或多個(gè)的輸出。這些輸出是同輸入有著某些特定關(guān)系的量。
例：
有窮性 haha()
{/*only a joke,do nothing.*/
}
main()
{printf("請(qǐng)稍等...您將知道世界的未日...");
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;
} /*無(wú)輸出的算法沒(méi)有任何意義，
二、算法設(shè)計(jì)的要求
1、正確性
算法正確性的四個(gè)層次
程序不含語(yǔ)法錯(cuò)誤。 max(int a,int b,int c)
{
if (a>b)
{if(a>c) return c;
else return a;
}
}
程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足規(guī)格說(shuō)明要求的結(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ī)格說(shuō)明要求的結(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ī)格說(shuō)明要求的結(jié)果。
2、可讀性
3、健壯性
4、效率與低存儲(chǔ)量需求
效率指的是算法執(zhí)行時(shí)間。對(duì)于解決同一問(wèn)題的多個(gè)算法，執(zhí)行時(shí)間短的算法效率高。
存儲(chǔ)量需求指算法執(zhí)行過(guò)程中所需要的大存儲(chǔ)空間。
兩者都與問(wèn)題的規(guī)模有關(guān)。
算法一 算法二
在三個(gè)整數(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;
}/*無(wú)需額外存儲(chǔ)空間，只需兩次比較*/ 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;
}
/*需要兩個(gè)額外的存儲(chǔ)空間，兩次比較，至少賦值*/
/*共需5個(gè)整型數(shù)空間*/
求100個(gè)整數(shù)中大者 同上的算法難寫(xiě)，難讀 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個(gè)整型數(shù)空間*/
三、總結(jié)
1、算法的特性
2、算法設(shè)計(jì)要求：正確性、可讀性、健壯性、效率與低存儲(chǔ)量需求。