(
课件网) 3.2 算法及算法描述 第三章 算法基础 课题引入 找两个数的 最大公约数比赛 知道他为什么计算这么快吗？ .给定两个正整数m=112，n=64，求最大公约数。 某同学方法如下： 比一比 Step1.112除以64，余数为___ Step2.____除以____，余数为___ Step3.____除以____，余数为___ 答：112和64的最大公约数为___ 48 64 48 16 48 16 0 16 巧用计算机解决问题提高效率 第三章 算法基础 3.2算法及其描述 第三章 算法基础 3.2算法及其描述 从计算机解决问题的过程出发——— 具体问题 分析问题 设计算法 编写程序 调试程序 得到答案 3.2.1 什么是算法 观看素材空间提供的学习视频素材，结合教材“3.2.1算法”，算法的定义 “、”算法的特征“。 概述算法的概念和特征 项目实施 Step1.r=m mod n Step2.若r=0，则输出结果n，算法结束； 否则，继续step3 Step3.令m=n，n=r，返回step1 几何学的鼻祖，古希腊数学家欧几里得创立了著名的欧几里得几何，简称欧氏几何。其中阐述了关于求两个整数的最大公约数的过程，叫辗转相除法，就是古人留下来的一种算法。 算法是指在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗地说，算法就是用计算机求解某一问题的方法，是能被机械地执行的动作或指令的有穷集合。 算法是程序设计的灵魂： 算法+数据结构（Data Structure）=程序。 算法独立于任何具体的程序设计语言，一个算法可以用多种语言来实现。 你知道世界上最早的算法？ 巴比伦人发明的六十进制，我们现在关于时分秒和角度的记法就是从他们那里学来的。 3.2.1 什么是算法 1.输入：一个算法有0个或多个输入，以刻画运算对象的初始情况。2.确定性：算法的每一步骤必须有确切的定义；3.有穷性：一个算法必须执行有限步骤之后结束。4.输出：算法至少有1个输出，即最终结果。没有输出的算法是毫无意义的。5.可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。3.2.1算法的特征 开学之际，同学们纷纷忙于购置各种学习文具，假设现在同学手中有50元的现金，用于购买下列物品，以何种方式搭配购买能够让资金最大化利用呢？ 笔记本 单价：6元/本 签字笔 单价：5元/支 橡皮 单价：4元/块 讨 论 买文具问题转化为求解方程：6x+5y+4z=50的正整数解个数t。 探究活动 第三章 算法基础 分 析 3.2算法及其描述 分析问题：x的取值范围1~8本，y的取值范围1~10支，z的取值范围1~12块，那么x，y，z的取值组合有几种？ 利用穷举法的思想，对每一种x、y、z的取值组合进行计算，如果正好等于50就输出x、y、z的值，t自增1并输出。 然后判断下一个取值组合，直到判断完所有的组合。 买文具问题转化为求解方程：6x+5y+4z=50的正整数解。 探究活动 第三章 算法基础 分 析 3.2算法及其描述 解决方法如下： t=0; x=1; y=1; z=1; 如果6x+5y+4z=50，则解的个数加1，输出这个解； z=z+1； 如果z<=12则转到⑤，否则继续⑧； y=y+1； 如果y<=10则转到④，否则继续⑩； x=x+1； 如果x<=8则转到③，否则继续12； 结束。 买文具问题转化为求解方程：6x+5y+4z=50的正整数解的python程序如下： 探究活动 实现 现 t=0 for x in range(1,9): for y in range(1,11): for z in range(1,13): if x*6+y*5+z*4==50: print(x,y,z) t=t+1 print("解的个数",t) 编写程序 第三章 算法基础 3.1体验计算机解决问题的过程 调试运行 体 验 请根据老师的演示，尝试打开电脑上的“解三元一次方程.py”代码文件，并运行程序，观察程序运行结果，得出结论。 买笔记本问题转化为求解方程：6x+5y+4z=50的正整数解 探究活动 第三章 算法基础 实 现 方案 x y z 合计 1 1 4 6 11 2 1 8 1 10 3 2 2 7 11 4 2 6 ... ...
