1.2算法和算法的描述

1.2算法和算法的描述第一章揭开计算机解决问题的神秘面纱信息技术（选修1）——算法与程序设计头脑风暴：例：设给定的两个正整数m=112和n=64，求它们的最大公约数。步骤：实践1求两个正整数的最大公约数算法的概念算法就是用计算机求解某一问题的方法，是能被机械地执行的动作和指令的有穷集合。简单说就是解决问题的方法和步骤，而且步骤是有限的。一、算法的概念有1个或多个输出能行性有穷性确定性有0个或多个输入二、算法的特征老师用纸条抽签抽出一位同学参与“猜数”游戏，再由该同学抽取下一位同学参加游戏。思考：若一个班有60人，老师是不是要准备60张号码纸？是否可以改进这个抽签形式，又不用浪费纸张？展示编制好的计算机程序，用计算机模拟抽签效果。提出：现实生活中，有没有应用产生随机数的算法案例？老师是如何设计算法的？三、随机数的游戏三、算法的描述流程图自然语言伪代码N-S图描述算法的方法PAD图问题：例：鸡兔同笼问题。有若干只鸡兔同在一个笼子里，从上面数，有35个头；从下面数，有94只脚。问笼中各有几只鸡和兔？试设计一个求解的算法。分析问题：设所求的鸡数是X，兔数是Y，已知笼子里的头数是a,脚数是b，根据题意得方程组X+Y=a2X+4Y=b解方程组得X=2a-b/2，Y=b/2-a1、用自然语言描述算法用自然语言表达算法，就是把算法的各个步骤，依次用人们熟悉的自然语言表示出来。三、算法的描述1）、输入a和b的值2）、求X=2a-b/23）、求Y=b/2-a4）、输出X，Y的值；5）、结束。开始输入a和b的值求x=2a-b/2求y=b/2-a输出x和y的值结束2、用流程图来描述算法三、算法的描述也称为程序框图，它是算法的一种图形化表示方法。程序框名称功能开始/结束算法的开始和结束输入/输出输入和输出信息处理计算与赋值判断条件判断流程线算法中的流向连接圈表示算法流向出口或入口连接点常用的“流程图”所用的基本符号3、用伪代码描述算法伪代码是介于自然语言和计算机程序语言之间的一种算法描述。三、算法的描述Inputa,bx=2*a-b/2y=b/2-aPrintx,y算法描述方式比较算法描述方式优势不足自然语言容易理解书写较烦、不确定性、描述太长、对复杂的问题难以表达准确、不能被计算机识别和执行流程图形象、直观、清晰简洁、容易理解不能被电脑识别伪代码简洁、易懂、修改容易不规范、不直观、错误不容易排查练一练：实践2求两个正整数的最大公约数和最小公倍数。用自然语言、流程图和源代码描述算法：四、算法在解决问题中的地位和作用同学甲的算法：同学乙的算法：PrivateSubCommand1_Click()m=9147485a=9147485n=5147480b=5147480r=mModnDoWhiler0m=nn=rr=mModnLoopPrint“最大公约数=”;nPrint“最小公倍数=”;a*b/nEndSubPrivateSubCommand1_Click()m=9147485a=9147485n=5147480b=5147480i=mDoWhilemModi0ornModi0i=i-1LoopPrint“最大公约数=”;IPrint“最小公倍数=”;a*b/iEndSubP13效率比较算法是程序设计的核心，是程序设计的灵魂。算法的好坏，直接影响程序的通用性和有效性，影响着问题解决的效率。几点建议求解同一计算问题可能有许多不同的算法，究竟如何来评价这些算法的好坏以便从中选出较好的算法呢？选用的算法首先应该是正确的。此外，主要考虑如下三点：①执行算法所耗费的时间；②执行算法所耗费的存储空间，其中主要考虑辅助存储空间；③算法应易于理解，易于编码，易于调试等等。小结2、算法的特征：有输入确定性有穷性有输出可行性3、算法的描述用自然语言描述算法用流程图描述算法用伪代码描述算法1、算法——解决问题的方法和步骤一个问题，可能有多种算法，应该通过分析、比较、挑选一种最优的算法。一个好算法必须用到科学的方法，应该好好学习各学科处理问题的科学方法。算法和算法的描述一、单项选择题1.以下不是算法特征的是（）。A.有穷性B.确定性和可行性C.输入和输出D.高效2.在流程图的基本图形中，菱形表示（）。A.开始/结束B.输入/输出C.处理D.判断3.以下说法正确的是（）。A.算法就是程序B.数据结构就是程序C.算法+数据结构=程序D.算法就是解决问题的方法DDC