算法的描述课件.pptx

我们上节课通过我们上节课通过“农夫过河农夫过河”的例子讨论了计算机解决问题的步骤，的例子讨论了计算机解决问题的步骤，你们还记得计算机是如何解决问题的吗？你们还记得计算机是如何解决问题的吗？u具体问题具体问题u分析问题分析问题 任何一个问题必须弄清楚其内容、性质及规模，才能找到解任何一个问题必须弄清楚其内容、性质及规模，才能找到解决问题的方法。决问题的方法。u设计算法设计算法u编写程序编写程序u调试程序调试程序u得出答案得出答案计算机解决问题的步骤计算机解决问题的步骤 选修一 1.2.2 算法的描述LoadingLoading粤教粤教2003课标版课标版算法是什么？规则解决问题思路办法算法的描述算法的概念算法的地位和作用算法的特征算法的描述算法总结 在有限步骤内求解某一问题所使用的一组定义明确的在有限步骤内求解某一问题所使用的一组定义明确的规则。规则。关键词：关键词：有限步骤有限步骤 求解某一问题求解某一问题 定义明确定义明确 算法的概念算法的描述算法的概念算法的地位和作用算法的特征算法的描述算法总结u有穷性有穷性 一个算法在执行有穷步之后必须结束。一个算法在执行有穷步之后必须结束。反例：反例：S1:sum=0S1:sum=0 S2:i=1 S2:i=1 S3:sum=sum+i S3:sum=sum+i S4:i=i+1 S4:i=i+1 S5:S5:若若sum=0sum=0，返回，返回S3S3；否则，算法结束。；否则，算法结束。算法的特征算法的特征u确定性确定性 算法的每一个步骤必须要确切的定义，不能有歧义。算法的每一个步骤必须要确切的定义，不能有歧义。例例1 1：这个发言稿是新来的市长的秘书写的。：这个发言稿是新来的市长的秘书写的。例例2 2：他已经走了半个多小时了。：他已经走了半个多小时了。算法的特征算法的特征u 能行性能行性 根据算法的每一个操作步骤最后要得出正确的结果。根据算法的每一个操作步骤最后要得出正确的结果。例：例：？求一元二次方程组的解。求一元二次方程组的解。求根公式法求出判别式的值。求根公式法求出判别式的值。=b-4ac =b-4ac，0 0时方程无解，时方程无解，00时时 有解。有解。u 输入。一个算法有输入。一个算法有0 0个或多个输入。个或多个输入。u 输出。算法有一个或多个输出。输出。算法有一个或多个输出。算法的特征算法的特征算法的描述算法的概念算法的地位和作用算法的特征算法的描述算法总结例例1 1问题：鸡兔同笼问题。一个笼子里有鸡和兔，现在只知道里面一共有35个头，94只脚，鸡和兔各有多少只？设计一个求解的算法，写出程序代码？x +y=35 2x+4y=94设所求鸡数是x,兔数是y，已知笼子里的头数是a，脚数是b，依题意，得到如下的方程组：x+y=a 2x+4y=b解方程组得：x=2a-b/2,y=b/2-a分析分析问题问题输入输入a a和和b b的值；的值；求求x=2a b/2x=2a b/2求求y=b/2-ay=b/2-a输出输出x,yx,y的值；的值；结束。结束。1 1.自然语言描述算法自然语言描述算法自然语言描述算法自然语言描述算法 流程图的基本图形及其功能流程图的基本图形及其功能2.2.用流程图描述算法用流程图描述算法图形形名称名称功能功能开始开始/结束束表示算法的开始或表示算法的开始或结束束输入入/输出出表示算法中的表示算法中的变量量输入或入或输出出处理理表示算法表示算法变量的量的计算与算与赋值判断判断表示算法条件判断表示算法条件判断流程流程线表示算法中的流向表示算法中的流向连接点接点表示算法的表示算法的转接接顺序结构顺序结构2.2.用流程图描述算法用流程图描述算法选择结构选择结构2.2.用流程图描述算法用流程图描述算法循环结构循环结构2.2.用流程图描述算法用流程图描述算法绘制流程图技巧绘制流程图技巧2.2.用流程图描述算法用流程图描述算法例：求例：求100100以内能被以内能被3 3整除整除 的所有正整数。的所有正整数。2.2.用流程图描述算法用流程图描述算法 开始开始 i=1i能被能被3整除整除 i=i+1i=100 结束结束是是否否否否输出输出i的值的值是是练习练习1.1.判断任意数判断任意数X X的奇偶性。的奇偶性。要求要求 （1 1）用自然语言描述出来。）用自然语言描述出来。（2 2）用流程图描述出来。）用流程图描述出来。2.2.用流程图描述算法用流程图描述算法2.2.用流程图描述算法用流程图描述算法 伪代码是用介于自然语言和计算机语言之间的文字和符号伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法的工具。来描述算法的工具。以鸡兔同笼问题为例以鸡兔同笼问题为例 自然语言自然语言 伪代码伪代码1 1、输入、输入a a和和b b的值；的值；1 1、input a,binput a,b2 2、求、求x=2a b/2 2x=2a b/2 2、x=2*a b/2x=2*a b/23 3、求、求y=b/2 a 3y=b/2 a 3、y=b/2-ay=b/2-a4 4、输出、输出x,yx,y的值；的值；4 4、print x,yprint x,y5 5、结束。、结束。5 5、endend 3.3.用伪代码描述算法用伪代码描述算法3.3.用伪代码描述算法用伪代码描述算法算法的描述算法的概念算法的地位和作用算法的特征算法的描述算法总结u算法设计有着举足轻重的地位和作用，算法是程序设计的算法设计有着举足轻重的地位和作用，算法是程序设计的核心，是程序设计的灵魂。核心，是程序设计的灵魂。u算法的好坏，直接影响着程序的通用性和有效性，影响着算法的好坏，直接影响着程序的通用性和有效性，影响着问题解决的效率。问题解决的效率。u程序的编制依赖于算法的设计，程序的效率主要取决于算程序的编制依赖于算法的设计，程序的效率主要取决于算法的效率。法的效率。算法的地位和作用算法的地位和作用1.1.下列关于算法的说法中，正确的是（下列关于算法的说法中，正确的是（）。）。A.A.算法就是某个问题的解题过程。算法就是某个问题的解题过程。B.B.算法执行后可以不产生确定的结果。算法执行后可以不产生确定的结果。C.C.解决某类问题的算法不是唯一的。解决某类问题的算法不是唯一的。D.D.算法可以无限的操作下去不停止。算法可以无限的操作下去不停止。答案：答案：C C练习题练习题2.2.下列关于算法的说法正确的是（下列关于算法的说法正确的是（）。）。A.A.某算法可以无止境的运行下去。某算法可以无止境的运行下去。B.B.一个问题的算法步骤可以是可逆的。一个问题的算法步骤可以是可逆的。C.C.完成一件事的算法有且只有一种。完成一件事的算法有且只有一种。D.D.设计算法要本着简单、方便、可操作的原则。设计算法要本着简单、方便、可操作的原则。答案：答案：D D3.3.下列运算中不属于我们所讨论算法范畴的是（下列运算中不属于我们所讨论算法范畴的是（）。）。A.A.已知圆的半径求圆的面积。已知圆的半径求圆的面积。B.B.从一副扑克牌随意抽取从一副扑克牌随意抽取3 3张扑克抽到张扑克抽到2121点的可能性。点的可能性。C.C.已知坐标平面内的两点求直线方程。已知坐标平面内的两点求直线方程。D.D.加减乘除运算法则。加减乘除运算法则。答案：答案：B B4.4.写出求写出求1+2+3+1001+2+3+100的一个算法。的一个算法。可以运用公式可以运用公式1+2+3+n=n(n+1)/21+2+3+n=n(n+1)/2直接计算。直接计算。第一步第一步 _(1)_;_(1)_;第二步第二步 _(2)_;_(2)_;第三步第三步 输出运算结果；输出运算结果；答案：(1)取n=100;(2)计算n(n+1)/2 在在几何原本几何原本中，欧几里得阐述了关于求两个整数的最中，欧几里得阐述了关于求两个整数的最大公约数的过程，这就是著名的欧几里得算法大公约数的过程，这就是著名的欧几里得算法辗转相辗转相除法，其具体过程如下：除法，其具体过程如下：设给定的两个正整数为设给定的两个正整数为mm和和n n，求它们最大公约数的步骤，求它们最大公约数的步骤为：为：（1 1）以）以mm除以除以n n，令所得的余数为，令所得的余数为r r。（2 2）若）若r=0r=0，则输出结果，则输出结果n n，算法结束；否则，继续步骤，算法结束；否则，继续步骤（3 3）。）。（3 3）令）令m=nm=n，n=rn=r，并返回步骤（，并返回步骤（1 1）继续进行。）继续进行。练习练习求最大公约数求最大公约数算法算法解决问题的方法和步骤。解决问题的方法和步骤。特征：输入、确定性、有穷性、能行性、输出。特征：输入、确定性、有穷性、能行性、输出。算法的描述：算法的描述：用自然语言描述算法用自然语言描述算法 用流程图描述算法用流程图描述算法 用伪代码描述算法用伪代码描述算法好的算法需要我们分析、比较、挑选。好的算法需要我们分析、比较、挑选。总结总结谢 谢谢谢谢谢