算法及其实现(新疆维吾尔自治区阿克苏地区阿克苏市)

(共25张PPT)
3.4 算法及其实现
阿克苏地区二中 吴园园
案例一：
一个农夫带着一条狼、一头山羊和一篮蔬菜要过河。当他来到渡口时发现过河的小船除了能装下自己之外，只能再带1样东西过河。这使他有点犯愁了，因为如果农夫不在场的情况下，狼会吃羊，羊会吃蔬菜。请同学们帮助农夫解决安全过河问题。
步骤一：农夫先带着羊乘船过河。
步骤二：农夫回来后再将狼乘船过河。
步骤三：将狼渡完河时，把羊再带回来。
步骤四：把羊放下将蔬菜乘船过河
步骤五：最后农夫回来再带着羊乘船过河。
步骤一：农夫先带着羊乘船过河。
步骤二：农夫回来后再将蔬菜乘船过河。
步骤三：将蔬菜渡完河时，把羊再带回来。
步骤四：把羊放下将狼乘船过河
步骤五：最后农夫回来再带着羊乘船过河。
所谓算法，就是解题方法的精确描述。是指在使用计算机解题前，需要将解题方法转换成一系列具体的在计算机上可执行的步骤，这些步骤能够清楚的反映解题方法一步步“怎么做”的过程，这个过程就是通常所说的算法。
案例二： 泡 茶
洗开水壶
灌凉水
洗茶壶
洗茶杯
拿茶叶
泡茶喝
洗开水壶
洗茶壶
洗茶杯
拿茶叶
灌凉水
烧开水
泡茶喝
拿茶叶
洗茶壶
洗茶杯
泡茶喝
烧开水
洗开水壶
洗开水壶
洗开水壶
洗茶壶
洗茶杯
拿茶叶
灌凉水
烧开水
泡茶喝
洗开水壶
灌凉水
拿茶叶
洗茶壶
洗茶杯
泡茶喝
烧开水
烧开水
最剩时间
洗开水壶
洗开水壶
对同一个问题，有时可以有不同的解题方法和步骤。有的方法只需要较少的步骤,而有些方法则可能需要较多的步骤。一般情况下,尽可能采用简单省时的和步骤少的方法去解决问题。因此，为了有效地解决问题，不仅需要保证算法正确，还要考虑算法的质量，这就要求人们设计或选择合适的算法。
1、有穷性（有限性）。任何一种提出的解题方法都是在有限的操作步骤内可以完成的，哪怕是失败的解题方法。
2、确定性（唯一性）。解题方法中的任何一个操作步骤都是清晰无误的，不会使人产生歧义或者误解。
3、可行性（能行性）。解题方法中的任何一个操作步骤在现有计算机软硬件条件下和逻辑思维中都能够实施实现。
4、有0到多个输入。解题算法中可以没有数据输入，也可以同时输入多个需要算法处理的数据。
5、有1到多个输出。一个算法执行结束之后必须有数据处理结果输出，哪怕是输出错误的数据结果，没有输出的算法使毫无意义的。
一、使用自然语言描述算法
二、使用流程图描述算法
三、使用伪代码（计算机语言）描述算法
例1：
要设计一个算法，对任意输入的三个整数x、y和z，找出并输出其中的最大值。这个算法比较简单，只要先比较x和y，得到一个较大的值max，再用max与z比较，将两者中较大的值作为结果输出即可。
第一种：用自然语言描述：
（1）输入变量X、Y和Z的值。
（2）比较X和Y。如果X>Y，则X存入以max命名的存储单元中，否则，Y送max。
（3）比较z和max。如果z>max，则将z送max。
（4）输出结果max。
从上面的这个描述的求解过程中，我们不难发现，使用自然语言描述算法的方法虽然比较容易掌握，但是存在着很大的缺陷。例如，当算法中含有多分支或循环操作时很难表述清楚。另外，使用自然语言描述算法还很容易造成歧义（称之为二义性），譬如有这样一句话——“武松打死老虎”，我们既可以理解为“武松/打死老虎”，又可以理解为“武松/打/死老虎”。自然语言中的语气和停顿不同，就可能使他人对相同的一句话产生不同的理解。又如“你输他赢”这句话，使用不同的语气说，可以产生3种截然不同的意思，同学们不妨试试看。为了解决自然语言描述算法中存在着可能的二义性，我们提出了第2种描述算法的方法——流程图。
第二种：用流程图描述
开 始
输入变量X、Y和Z的值
X>Y
MAX←X
MAX←Y
Z>MAX
Y
MAX←Z
输出变量MAX的值
结　束
Ｎ
Ｙ
Ｎ
流程图的缺点是在使用标准中没有规定流程线的用法，因为流程线能够转移、指出流程控制方向，即算法中操作步骤的执行次序。在早期的程序设计中，曾经由于滥用流程线的转移而导致了可怕的“软件危机”，震动了整个软件业，并展开了关于“转移”用法的大讨论，从而产生了计算机科学的一个新的分支学科——程序设计方法。无论是使用自然语言还是使用流程图描述算法，仅仅是表述了编程者解决问题的一种思路，都无法被计算机直接接受并进行操作。由此我们引进了第三种非常接近于计算机编程语言的算法描述方法——伪代码。
用计算机语言描述（C++语言）：
#include void main() { int a,b,c; printf("输入三个数："); scanf("%d%d%d",&a,&b,&c); if(a>b&&a>c) printf("最大值为：%d",a); else if(b>a&&b>c) printf("最大值为：%d",b); else printf("最大值为：%d",c); }
例2：
求解 sum=1+2+3+4+5……+（n-1）+n为例
请利用自然语言和流程图描述算法
第一种：用自然语言描述：
① 确定一个n的值；
② 假设等号右边的算式项中的初始值i为1；
③ 假设sum的初始值为0；
④ 如果i≤n时，执行⑤，否则转出执行⑧；
⑤ 计算sum加上i的值后，重新赋值给sum；
⑥ 计算i加1，然后将值重新赋值给i；
⑦ 转去执行④；
⑧ 输出sum 的值，算法结束。
sum=1+2+3+4+5……+（n-1）+n
第二种：用流程图描述
开 始
输入n的值
i=1; sum=0
i <=n
Yes
sum=sum+i
i=i+1
No
输出sum的值
结 束
哪位同学上来总结一下我们这节课都学了什么内容 你学到了哪些知识和本领
（1）有两个瓶子A和B，分别盛放醋和酱油，如果要将 它们所盛的内容互换，即A瓶原来盛醋，现改为盛酱油，B瓶则相反。请用自然语言来描述实现这一转换的算法。
（2）输入三个数，判断它们是否能成为一个三角形的三条边的长度，若能则输出“能”，否则输出“不能”。请用流程图描述本题的算法。
P76页 1. 2 题