资源简介 (共27张PPT)3.2 算法及算法描述第三章 算法基础课题引入找两个数的最大公约数比赛知道他为什么计算这么快吗?.给定两个正整数m=112,n=64,求最大公约数。某同学方法如下:比一比Step1.112除以64,余数为___Step2.____除以____,余数为___Step3.____除以____,余数为___答:112和64的最大公约数为___486448164816016巧用计算机解决问题提高效率第三章 算法基础3.2算法及其描述第三章 算法基础3.2算法及其描述从计算机解决问题的过程出发——具体问题分析问题设计算法编写程序调试程序得到答案3.2.1什么是算法观看素材空间提供的学习视频素材,结合教材“3.2.1算法”,算法的定义 “、”算法的特征“。概述算法的概念和特征项目实施Step1.r=m mod nStep2.若r=0,则输出结果n,算法结束;否则,继续step3Step3.令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=0for 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+1print("解的个数",t)编写程序第三章 算法基础3.1体验计算机解决问题的过程调试运行体验请根据老师的演示,尝试打开电脑上的“解三元一次方程.py”代码文件,并运行程序,观察程序运行结果,得出结论。买笔记本问题转化为求解方程:6x+5y+4z=50的正整数解探究活动第三章 算法基础实现方案 x y z 合计1 1 4 6 112 1 8 1 103 2 2 7 114 2 6 2 105 3 4 3 106 4 2 4 107 6 2 1 93.2算法及其描述1.用自然语言描述算法用自然语言描述算法,就是用人们日常所用的语言,如:汉语、英语等来描述算法。第三章 算法基础3.2.2算法的描述t=0;x=1;y=1;z=1;如果满足式子6x+5y+4z=50,则购买的方案数加1(即t=t+1),并输出这种购买方案(即输出t、x、y、z的值)。z=z+1;如果z<=12则转⑤,否则继续⑧;y=y+1;如果y<=10则转④,否则继续⑩;x=x+1;如果x<=8则转③,否则继续 ;结束。3.2算法及其描述2.用流程图描述算法用ANSI制定的一系列流程图符号来描述算法的一种表示方法。使用流程图描述算法,让人感到算法的形象直观简洁。流程图的基本图形及其功能如下表所示。(例:教材图3-8)第三章 算法基础图 形 名 称 功 能开始/结束 开始或结束输入/输出 输入或输出处理 计算与赋值判断 条件判断流程线 表示算法中的流向连接点 表示算法中的转接表3-4流程图的基本图形及其功能表所示。3.2.2算法的描述3.2算法及其描述探究活动这三种基本控制结构的主要作用是:(1)顺序结构表示程序中的各操作是按照它们出现的先后顺序执行的。(2)选择结构表示程序的处理步骤出现了分支,它需要根据某一特定的条件选择其中的一个分支执行。选择结构有单选择、双选择和多选择三种形式。(3)循环结构表示程序反复执行某个或某些操作,直到某条件为假时才可终止循环,结构中有返回跳转。讨论观看光盘视频掌握算法的三种基本控制结构第三章 算法基础3.2算法及其描述3.用流程图描述购买文具问题的算法第三章 算法基础3.2.2算法的描述3.2算法及其描述3.用伪代码描述算法用伪代码描述算法就是用介于自然语言和计算机语言之间的文字和符号来描述算法。第三章 算法基础t=0for 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:{t=t+1;输出解的个数t和三个整数x,y,z}3.2.2算法的描述3.2算法及其描述分组讨论:辗转相除法的三种算法描述。设给定的两个正整数为m和n,求它们的最大公约数的步骤为:以m除以n,令所得余数为r。若r=0,则输出结果n,算法结束;否则继续③。令m=n,n=r,并返回①继续。项目实施第三章 算法基础3.2算法及其描述探究活动实践辗转相除法的算法描述展评第三章 算法基础自然语言表示法 流程图表示法 伪代码表示法示例 ①输入两个正整数m,n(m>n); ②计算m除以n所得的余数r; ③m=n,n=r; ④若r=0,则m,n的最大公约数等于m;否则转到步骤②; ⑤输出最大公约数m; ⑥结束。 m=input("m=")n=input("n=")if m < n:t=m, m = n, n=tr = m% nwhile r != 0:r = m% nm = nn = rprint m3.2算法及其描述探究活动讨论算法三种描述方法的优劣对比第三章 算法基础算法描述的方法 优势 不足自然语言表示法 用人们日常所用的语言,比较容易掌握。 当算法中含有多分支或循环操作较多时很难清晰地表示出来,由于自然语言的歧义性,容易导致算法执行的不确定性。流程图表示法 用程序框图来描述,流程描述清晰简洁。 所占篇幅较大,由于允许使用流程线,过于灵活,不受约束。伪代码表示法 用介于自然语言和计算机语言之间的文字和符号来描述,书写方便,格式紧凑,易于理解,便于向计算机程序设计语言过渡。 由于编程语言的种类繁多,伪代码的语句不容易规范,有时会产生误解。3.2算法及其描述算法是程序设计的核心,是程序设计的灵魂。算法的好坏,直接影响着程序的通用性和有效性,影响着问题解决的效率,算法不唯一,同一个算法可以用多种程序设计语言来实现。恰当的算法描述更有利于编写程序。要点:算法描述要完整,步骤要清晰,符合算法的特征,有效解决项目的关键问题。第三章 算法基础3.2算法及其描述课堂小结1、用计算机解决某个问题,问题分析清楚后,给出解决这个问题的( ),这个过程称为设计算法。A、编程语言B、程序代码 C、方法和步骤 D、加密措施2、用流程图表示条件“A>B”是否成立,要用到以下哪个图形?( )A 平行四边形 B 菱形 C 圆角矩形 D直角矩形 3、 用自然语言描述一下解决以下问题的算法:借助一个空杯将一杯橙汁和一杯可乐互换所盛放的杯子。课堂练习过程步骤第三章 算法基础3.1体验计算机解决问题的过程[参考答案](1)橙汁倒入空杯;(2)可乐倒入刚空出的杯子;(3)橙汁倒入刚倒出可乐的杯子第三章 算法基础设计一个算法,输入半径r,输出圆的面积S和周长L。设计一个算法,求鸡兔同笼问题:上有头a个,下有脚b只,问鸡兔各几何?设计一个算法,求两个数中的最大数。设计一个算法,求实数a的绝对值。课后作业3.2算法及其描述 展开更多...... 收起↑ 资源预览