算法和算法的描述

第二节算法和算法描述教学目标:1、掌握算法的概念和特征；2、掌握算法的描述方法；3、了解算法在解决问题中的地位和作用欧几里得是古代最有名望的学者之一，古希腊数学家，几何学鼻祖。公元前300年左右，他所著《几何原本》十三卷，是世界上最早公理化的数学著作。在《几何原本》中，他充分总结了前人的生产经验和研究成果，从公理和公设出发，运用演绎法，经过逻辑推理和数学运算，创立了著名的欧几里得几何（简称欧式几何）。例利用辗转相除法求两个正整数m和n的最大公约数（1）m除以n，令所得的余数为r。（2）若r=0,则输出结果n，算法结束；否则，继续步骤（3）。（3）令m=n,n=r,并返回步骤（1）继续进行。输入m和n的值。结束分析：构成这个问题的一个完整算法一、算法的概念：算法就是用计算机解决问题的方法和步骤。是能被机械的执行的动作或指令的有穷集合。利用辗转相除法，求112和64的最大公约数。（1）112除以64，余数为48（2）64除以48，余数为16（3）48除以16，余数为0答：112和64的最大公约数为16如何求最小公倍数？m*n=最大公约数*最小公倍数二、算法的特征：（1）输入（2）输出（3）确定性（4）有穷性（5）可行性输入：一个算法有零个或多个输入，以刻画运算对象的初始情况。例如，在欧几里得算法中，有两个输入，即m和n。所谓0个输入是指算法本身定出了初始条件确定性：算法的每一步骤必须有确切的定义。即算法中所有有待执行的动作必须严格而不含混地进行规定，不能有歧义性。例如：在欧几里得算法中，步骤（1）中明确规定“以m除以n”，而不能有类似“以m除以n或n除以m”这类有两种可能做法的规定。输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；例如，在欧几里得算法中只有一个输出，即步骤（2）中的n。有穷性：一个算法必须保证执行有限步之后结束可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成三、算法的描述：方法：自然语言、流程图、伪代码等。1、用自然语言描述算法。例1-2鸡兔同笼问题一个笼子里有鸡和兔，现在只知道共有35个头，94只脚，问鸡和兔个有多少只？设鸡数是x，兔数是y，由已知得以下方程组：x+y=a2x+4y=b解得x=2a-b/2,y=b/2-a分析：设计算法：（1）输入a和b的值；（2）求x=2a-b/2;（3）求y=b/2-a；（4）输出x,y的值；（5）结束。例1-3求100以内能被3整除的所有正整数。分析：设能被3整除的数为I,令I=1，2，3，，100，如果I是能被3整除的数，则输出I，否则，检查下一个I，直到I=100为止。设计算法2、用流程图描述算法用一组图形符号来表示算法。例如：3、用伪代码描述算法它是介于自然语言和流程图之间的一种描述算法的工具。三种算法描述方式的比较算法描述方式优势不足自然语言不用专门训练，通俗易懂语句过长产生歧义难以清晰的表示较多的循环和分支不便于翻译成编程语言流程图清晰简洁各种结构一目了然有利于不同环境的程序设计书写不方便伪代码精练，容易转化为程序设计语言语句不规范，有时会产生误解四、算法在解决问题中的地位和作用：有举足轻重的地位和作用。他是程序设计的核心，是程序设计的灵魂。一个算法的好坏，直接影响着程序的通用性和有效性，影响着问题解决的效率。五、小结：通过本节的学习，我们复习了算法的定义、算法的特征、算法的描述方法以及算法在解决问题中的地位和作用，算法是整个程序设计的基础，编写一个好的程序，离不开一个好的算法。六、作业:（1）课本11页猴子吃桃问题（2）课后练习（2）（3）课后练习（3）