算法和算法的描述.ppt

算法和算法的描述
第1页，本讲稿共15页
导入新课
我们上节课通过“韩信点兵”的例子探讨了计算机解决问题的步骤，你们还记得计算机解决问题的步骤吗？
计算机解决问题的步骤
分析问题
设计算法
编写程序
调试程序算法和算法的描述
第1页，本讲稿共15页
导入新课
我们上节课通过“韩信点兵”的例子探讨了计算机解决问题的步骤，你们还记得计算机解决问题的步骤吗？
计算机解决问题的步骤
分析问题
设计算法
编写程序
调试程序
得出答案
具体问题
第2页，本讲稿共15页
思考
有一个牧羊人带着一头羊，一只狼和一棵大白菜准备过河，
他找到一只很小的船，每次只能带一样东西过去，如果狼
和羊单独在一起，狼会吃羊，让羊和白菜单独在一起，羊
会吃白菜，牧羊人应如何过河？
新课导入
要求：现在请同学们设计个方案，把3样
东西安然无恙的度过河
第3页，本讲稿共15页
步骤1：
步骤2：
步骤3：
步骤4：
人和羊过河，人返回，留下羊
人和狼过河，人和羊返回，留下狼
人和菜过河，人返回，留下菜
人和羊过河
新课导入
第4页，本讲稿共15页
一、算法
1、算法的概念
算法是在有限步骤内求解某一问题所使用的一组定义
明确的规则。通俗地说，算法就是求解某一问题的方法，
是能被机械地执行的动作或指令的集合。
第5页，本讲稿共15页
一、算法
2、算法的特征
（1）输入。一个算法有零个或多个输入。
零个输入的例子：
Private sub command1_click()
a=3:b=4
Print a*b
End sub
（2）确定性。算法的每一个步骤必须要确切地定义。
例1：这个人好说话。
例2：健美操中一个动作：“手举过头顶”。
第6页，本讲稿共15页
一、算法
2、算法的特征
（3）有穷性。一个算法在执行有穷步之后必须结束。
反例：
S1: sum=0
S2: I=1
S3: sum=sum+I
S4: I=I+1
S5: 若sum>=0 ，返回s3;否则，算法结束。
（4）输出。算法有一个或多个输出。
（5）能行性。
第7页，本讲稿共15页
二、算法的描述
表示算法的语言有哪几种？
表示算法的语言有自然语言、流程图、伪代码。
1、用自然语言描述算法
例:求200-500能被5整除的所有正整数。
（1）分析问题。
设能被5整除的数为I,令I=200,201,202，……，500，
如果I是能被5整除的数，则输出I；否则，检查下一个I，直
到I=500为止。
（2）设计算法
①令I=200;
②如果I能被5整除，则输出I;
③I=I+1;
④如果I<=500，则返回第②；
⑤结束。
第8页，本讲稿共15页
二、算法的描述
1、用自然语言描述算法
用自然语言
描述算法
优点：描述的算法通俗易懂。
缺点：
自然语言具有歧义性，容易导致算法执行的不确定性。
自然语言描述的算法太长。
当算法中循环和分支较多时，很难清晰地表示出来。
自然语言表示的算法不便翻译成计算机程序设计语言。
第9页，本讲稿共15页
二、算法的描述
2、用流程图描述算法
图形
名称
功能
起始/结束
表示算法的开始或结束
输入/输出
表示算法中变量的输入或输出
处理
表示算法中变量的计算或赋值
判定
表示算法中的判断
流程线
表示算法中的流向
连接点
表示算法流向出口或入口连接点
第10页，本讲稿共15页
二、算法的描述
2、用流程图描述算法
例:求200-500能被5整除的所有正整数。
开始
I=200
I能被5整除
输出I的值
I=I+1
I<=500
结束
是
否
否
是
第11页，本讲稿共15页
二、算法的描述
2、用流程图描述算法
用流程图描述算法
优点：描述清晰简洁，不依赖计算机和计算机程序设计语言。
缺点：画起来费事，难以阅读，难以修改。
第12页，本讲稿共15页
二、算法的描述
3、用伪代码描述算法
Input m, n
r= m mod n
Do while r<>0
m=n
n=r
r=m mod n
Loop
Print n
例：用辗转相除法求两个数的最大公约数的伪代码。
伪代码是用介于自然语言和计算机语言之间的
文字和符号来描述算法的工具。
第13页，本讲稿共15页
二、算法的描述
3、用伪代码描述算法
用伪代码描述算法