资源简介

(共22张PPT)
1.算法及其描述
任务一：
一个农夫带着一头羊、一只狼和一颗大白菜过河，但只有一条小船，并且每次只能让农夫带一样东西过河。
农夫在场的情况下一切相安无事，一旦农夫不在，狼会吃羊，羊会吃白菜。
注意：
要写明确共几个步骤，并标明序号。
农夫如何解决过河问题？
1、算法
概念：
算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。
即用计算机求解某一问题的方法，是能被机械地执行的动作或指令的有穷集合。
广义：是解决问题的方法和步骤，而且步骤是有限的。
计算机科学中：用计算机解决问题的步骤。
任务二：
在数学中，我们是用什么方法来求两个正整数的最大公约数的。
例：m=112,n=64，求它们的最大公约数。
欧几里得算法设给定的两个正整数为m
和n,
求它们的最大公约数的步骤如下：
1、以m除n，令所得的余数为r。
2、若r=0，则输出n,算法结束；否则，继续步骤3。
3、令m=n，n=r，并返回步骤1继续进行。
计算：现在请同学们再计算m=112和n=64的最大公约数。
辗转相除法
2、算法的特征
有穷性：执行步骤和每步执行时间都是有限的
算法特征
确定性：每个步骤的执行
描述必须是明确的
输出：至少产生一个输出（必须有）（不做无用功）
可行性：每个步骤都是可以做到并能在有限的时间内完成。
1
2
3
输入：初始数值可以从外界输入，也可以包含在算法中
4
5
打印输出所有的偶数
100/正整数
计算a@b的值
算法的描述
问题
1：在【任务一】中，我们是用什么来描述算法的？
问题
2：还有什么其他的方式吗？
3、算法的描述
自然语言：
是人们日常所用的语言，如汉语、英语、德语等。
优点
通俗易懂
容易理解
缺点
冗长
存在歧义
3、算法的描述
有两个瓶子A和B
,
A瓶装有雪碧,B瓶装有可乐,问如何把雪碧和可乐互换。即A瓶原来装雪碧,现改为装可乐,B瓶原来装可乐,现改为装雪碧。
流程图：
使用流程图描述算法，让人感到算法的流程描述清晰简洁，容易表达选择结构；它不依赖于任何具体的计算机和计算机程序设计语言，从而有利于不同环境的程序设计。
图
形
名
称
功
能
开始/结束框
表示算法的开始或结束
输入/输出框
表示算法中变量的输入或输出
处理框
表示算法中变量的计算与赋值
判断框
表示算法中的条件判断
流程线
表示算法中的流向
3、算法的描述
表1
流程图的基本图形及其功能
3、算法的描述
伪代码：
是用介于自然语言和计算机语言之间的文字和符号来描述算法的工具。它不使用图形符号，因此，书写方便，格式紧凑，易于理解，便于向计算机程序语言过渡。
3、算法的描述
A=雪碧,B=可乐,C=空
C=A
A=B
B=C
任务三：
鸡兔同笼问题：
一个笼子里有兔和鸡，现在只知道里面一共有35个头，94只脚，兔和鸡各有多少只？
试设计一个求解的算法，并用自然语言描述出来。
注意：
要写明确共几个步骤，并标明序号。
设：兔子的数量为X，鸡的数量为Y
求解二元一次方程组:
X+Y=35
4X+2Y=94
求X和Y的值
数学题：
1.让兔子和鸡都抬起两只脚。
跑男中包贝尔算法：
抬起脚的数量：2
35=70
2.地上站着的脚全部是兔子的
？
地上站着的脚的数量：94-70=24
3.每只兔子还剩几只脚站在地上？
兔子的数量：24/2=12
4.是不是可以求出鸡的数量？
鸡的数量：35-12=23
任务三：总结出这类问题的通用解决办法。
鸡兔同笼问题：
一个笼子里有兔和鸡，现在只知道里面一共有m个头，n只脚，求兔子的数量X和鸡的数量Y？
1.让兔子和鸡都抬起两只脚。
跑男中包贝尔算法：
抬起脚的数量：2
m
2.地上站着的脚全部是兔子的
？
地上站着的脚的数量：
n-2
m
3.每只兔子还剩几只脚站在地上？
兔子的数量：X=(n-2
m)/2
4.是不是可以求出鸡的数量？
鸡的数量：Y=m-X
图1
用流程图表示鸡兔同笼算法
开
始
输入头的数量m和脚的数量n
兔子的数量：X=(n-2m)/2
输出兔子的数量X和
鸡的数量Y
结束
鸡的数量：Y=m-X
开
始
输入头的数量m和脚的数量n
设兔子数X=1
鸡数Y=m-X
4X+2Y=n
输出兔子的数量X和
鸡的数量Y
结束
是
否
X=X+1
Y=m-X
流程图
鸡兔同笼算法1：
输入m和n的值
X=(n-2m)/2
Y=m-X
输出X和Y的值
伪代码
鸡兔同笼算法2：
输入m和n的值
X等于1
Y等于m-X
do
while
n不等于4X+2Y
X=X+1
Y=m-X
Loop
输出X和Y的值
表2
三种算法描述方式的优劣
算法描述方式
优点
缺点
自然语言
不需要专门训练，通俗易懂
歧义性、语句长、循环和分支较多时难以清晰表示、不便翻译成计算机程序设计语言
流程图
描述清晰简洁，容易表达选择结构，利于不同环境的程序设计
无法被计算机直接接受进行操作
伪代码
书写方便，格式紧凑，易于理解，便于向计算机程序设计语言过渡
种类繁多，语句不容易规范
本节课总结：

展开更多......

收起↑