22算法的概念及描述课件高一上学期高中信息技术必修1第2章人教中图版

2.2算法的概念及描述年级：高一

学科：信息技术（人教/中图）思考:1.列举出由A站出发到达B站的所有换乘次数最少的乘车路线。2.如果小明同学希望尽快到达B站，试为他推荐一条最佳乘车路线，并说明理由。A-E-G-B或A-K-J-B或A-K-G-B体验探索思考:1.列举出由A站出发到达B站的所有换乘次数最少的乘车路线。2.如果小明同学希望尽快到达B站，试为他推荐一条最佳乘车路线，并说明理由。A-E-G-B或A-K-J-B或A-K-G-B体验探索A-K-J-B或A-K-G-B

从广义上讲，算法是为解决一类特定问题而采取的确定的、有限的步骤。它描述出某类问题求解的方法和过程，在整个问题解决过程中起着重要的作用。算法的概念

“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。”——《九章算术》更相减损术两种情形步骤“不可半者”（如153和119）直接辗转相减，直至减数和差相等：①153-119=34②119-34=85③85-34=51④51-34=17⑤34-17=17所以，153和119的最大公约数为17“可半者”（如24和16）第一步，现将24和16用2反复约简，直至不都是偶数，约数最后为8（用2反复约简了3次）第二步，分别将两个约简的数辗转相减，直至减数和差相等：①3-2=1②2-1=1第三步，求差和约数的积：1×8=8所以，24和16的最大公约数为8更相减损术电梯运行铁路订票算法的应用共享单车外卖服务算法的应用

一个算法一般要求有0个或多个输入,以描述运算对象的初始情况。

一个算法可以有一个或多个输出,以反映对输入数据加工后的结果。

算法的有穷性指算法必须能在执行有限个步骤之后终止,也就是算法步骤不能是无限的。有穷性03有输出02有输入01算法的特征算法中的每一步操作都是可以执行的,或者都可以分解成计算机可执行的基本操作。算法的每个步骤都具有确定的含义,没有歧义。模糊不清、模棱两可或带有二义性的描述都会影响算法的确定性。可行性04确定性05算法的特征描述算法就是将解决问题的步骤，用一种可理解的形式表示出来。常用的描述算法的方法有自然语言、流程图和伪代码等。算法的描述红灯倒计时15s的描述用自然语言描述算法易于理解，它既可以描述生活中的算法，也可以描述在计算机中执行的算法。但是,自然语言的描述方法存在容易产生二义性的缺点，有可能干扰后续的编程实现。步骤1：将计数器t设为15；步骤2：如果t大于或等于1，执行步骤3，否则倒计时结束；步骤3：输出t,并保持显示1s，然后清除显示；步骤4：将t的值减1，跳转至步骤2。自然语言流程图符号名称功能

开始/结束框表示算法的开始或结束

输入/输出框表示输入或输出数据

处理框框中指出要处理的内容，此框有1个入口和1个出口流程图流程图符号名称功能

判断框用于表示条件判断及产生分歧的情况，判断框有4个顶点，通常上面的顶点表示入口，视需要用另外3个顶点来表示出口

流程线用于控制流程方向

连接点用于连接因页面写不下而断开的流程线流程图顺序结构选择结构循环结构123流程图的三种结构

每一个步骤按先后次序被执行，即执行处理A，然后执行处理B。

顺序结构AB

又称分支结构。根据条件的成立与否，选择执行不同的分支处理。当条件成立时(True)，执行处理A；当条件不成立时(False)，执行处理B。

AB条件TrueFalse选择结构

当条件成立时，反复执行处理A，一旦条件不成立就立即结束循环。

B条件TrueFalse循环结构倒计时15s流程图t←15t≥1TrueFalse输出t开始结束清除显示保持显示1st←t-1流程图是一种常用的表示算法的图形化工具。用流程图描述的算法直观易读，问题解决的步骤清晰简洁，算法结构表达明确，很适合初学算法的人员使用。

绘制流程图的方法很多，可以手工绘制流程图，也可以用软件制作，如使用文本编辑软件中的“流程图”对象绘制，或使用专门的流程图绘制软件，还可以到在线绘制流程图网站进行制作。流程图用伪代码描述算法就是采用一种类似于程序设计语言的代码来表示算法。伪代码没有固定的、严格的语法规则，只要定义合理，没有矛盾即可。

用伪代码描述算法回避了程序设计语言严格的书写格式，保持了语言叙述准确、无二义性的优点，结构性强，比较容易书写和理解。倒计时15s伪代码t←15whilet≥1outputtsleep1scleart←t-1endwhile自然语言流程图伪代码优点容易理解形象直观容易理解简洁易懂修改容易缺点书写较烦、容易产生不确定性、歧义等。所占篇幅较大，过于灵活，不受约束修改困难等。不直观、错误不容易排查三种描述方法的对比找出质量较轻的零件

已知有10个一模一样的零件，其中9个零件的质量相同，只有1个质量略轻，不符合规格要求。现在有一台天平，请设计算法找出该零件。

1.如果采用一一比较的方法，逐一称重对比，最多需要比较多少次才能找出这个质量较轻的零件？试着描述该算法，想一想还有哪些方法可以解决该问题？2.如果有n个零件（n>10），要找出其中质量较轻的一个，以上方法是否仍然可用？试分析n=10000时，这些算法在问题解决效率上的不同。实践活动123456789101.两两比较，最多5次！实践活动2.分成两组，每组5个，较轻的一组拿出4个，分别放在天平两端，较轻的一组最后比较一次