【海淀高中信息技术】2.2算法的概念及描述

2.2算法的概念及描述学习目标：描述算法的特征，理解算法在问题解决中的作用。选用恰当的描述方法和控制结构表示简单算法，增强用算法解决问题的意识。123什么是算法？算法的描述方法45标准流程符号程序设计三种基本结构流程图设计项目流程图引入：规划乘车路线小明同学所在城市的地铁线路局部图，他计划从A站出发去B站附近的图书馆学习。假设地铁各线路每两站间行车用时相等，记为t1；换乘地铁的用时也相等，记为t2。1.列举出由A站出发到达B站的所有换乘次数最少的乘车路线。2.如果小明同学希望尽快到达B站，试为他推荐一条最佳乘车路线，并说明理由。算法是为解决一个特定问题而采取的确定的、有限的步骤。算法就是解决某一类问题的方法和步骤。什么是算法？1我国古代《九章算术》中记载的“更相减损术”，求两个正整数最大公约数。其方法“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。”算法的特征1方法步骤不可半者（如153和119）直接辗转相减，直至减数和差相等：1）153-119=342）119-34=853）85-34=514）51-34=175）34-17=17所以，153与119的最大公约数为17可半者（24和16）第一步，先将24和16用2反复约简，直至不都是偶数，约数最后为8（用2约简了三次）；第二步，分别将两个约简后的数辗转相减，直至减数和差相等：1）3-2=12）2-1=1第三步，求差和约数的乘积：1×8=8所以，24与16的最大公约数为8有输入有输出有穷性可行性确定性算法是为解决一个特定问题而采取的确定的、有限的步骤。算法就是解决某一类问题的方法和步骤。什么是算法？1算法的特征：有输入、有输出、有穷性、可行性、确定性自然语言描述、伪代码描述、流程图描述3算法的描述方法伪代码：输入a，bifab，则printa否则printb问题：输入两个数，打印输出其中最大的数。自然语言：输入a和b两个数，如果a大于b，则打印输出a，否则打印输出b流程图：程序代码：a=float(input())b=float(input())ifab:print(a)else:print(b)输入a,b的值判断ab?否是打印输出a开始结束打印输出b2算法的描述方法伪代码：输入a，b，cifab，则max←a否则max←bifcmax，则max←cprintmax问题：输入三个数，打印输出其中最大的数。自然语言：输入a、b、c三个数，如果a大于b，则把a给最大值max记录，否则把b给最大值max记录，如果c大于max，则把c给最大值max记录，输出max的值流程图：程序代码：a=float(input())b=float(input())c=float(input())ifab:max=aelse:max=bifcmax:max=cprint(max)输入a,b,c的值max←b输出max判断ab?否是max←a开始结束判断cmax?是max←c否32文字较多，容易产生二义性标准流程符号输入a,b的值max←b输出max判断ab?否是max←a开始结束起、止框输入、输出框判断框处理框流程线3程序设计三种基本结构流程图（1）顺序结构：每一个步骤按先后次序被执行，即执行处理A，然后执行处理B。是最简单的算法结构。（2）选择结构：也叫分支结构，根据条件的成立与否，选择执行不同的分支处理。当条件成立时（用Ture表示），执行处理A；当条件不成立时（用False表示），执行处理B。（3）循环结构：当条件成立时，反复执行处理A，一旦条件不成立就立即结束循环。4ABABTrueFalseTrueFalseA思考活动：描述“红灯变绿灯”问题的算法（学生练习制作流程图，再与书中答案比较）5自然语言描述：步骤1：将计数器t设为15秒步骤2：如果t大于或等于1，执行步骤3，否则倒计时结束；步骤3：输出t，并保持显示1秒，然后清除显示；步骤4：将t的值减1，跳转至步骤2。伪代码描述：t15whilet≥1outputtsleep1scleartt-1Endwhile完善本章第一节思考活动“红灯变绿灯”功能，在交通信号灯下方增加一个15秒的“倒计时器”，提示过往的行人和车辆。tt-1t≥1?否是输出tt15开始结束保持显示1秒清除显示流程图：设计项目流程图（自学书中内容）5