算法的概念+课件（共42张ppt）

1.1.1 算法的概念学习目标 :通过分析具体问题过程与步骤 ,体会算法的思想 ,了解算法的含义 ,能用自然语言描述解决具体问题的算法 .学习重点 (难点 ):通过实例体会算法思想 ,初步理解算法的含义 .问题 1请你写出解二元一次方程组的详细求解过程 . 第一步 : 2+ 得 : 5x=1 第二步 :解 得 :x=1/5第三步 :将 x=1/5代入 得 :y=3/5第四步 :得到方程组的解为 :对于一般的二元一次方程组其中 也可以按照上述步骤求解 .这些步骤就构成了解二元一次方程组的算法 ,我们可以根据这一算法编制计算机程序 ,让计算机来解二元一次方程组 .算法的概念与特征算法 (algorithm)这个词出现于 12世纪 ,指的是用阿拉伯数字进行算术运算的过程 .在数学上 ,“算法 ”通常是指按照一定规则解决某一类问题的明确和有限的步骤 .现在算法通常可以编成计算机程序 ,让计算机执行并解决问题 .说明 :(1)事实上算法并没有精确化的定义 .(2)算法虽然没有一个明确的定义 ,但其特点是鲜明的 ,不仅要注意 算法的程序性、有限性、构造性、精确性的特点，还应该充分理解算法问题的指向性，即算法往往指向解决某一类问题，泛泛地谈算法是没有意义的。算法学的发展 随着科学技术的日新月异 ,算法学也得到了前所未有的发展 ,现在已经发展到了各个领域 .有遗传算法 ,排序算法,加密算法 ,蚁群算法等 ,与生物学 ,计算机科学等有着很广泛的联系 ,尤其是在现在的航空航天中 ,更是有着更广泛的应用 . 很多复杂的运算都是借助计算机和算法来完成的 ,在高端科学技术中有着很重要的地位 .例 1:任意给定一个大于 1的整数 n,试设计一个程序或步骤对 n是否为质数做出判定 .分析 :请回顾这个问题的解题过程 .算法分析 :第一步 :判断 n是否等于 2. 若 n=2,则 n是质数 ;若 n2,则执行第二步 .第二步 :依次检验 2(n-1)这些整数是不是 n的因素 ,即是不是整除 n的数 .若有这样的数 ,则 n不是质数 ;若没有这样的数 ,则 n是质数 .说明 :用语言描述一个算法 ,最便捷的方式就是按解决问题的步骤进行描述 .每一步做一件事情 .若是 ,则 m为所求 ; 例 2:用二分法设计一个求方程 x2-2=0的近似根的算法 .算法分析 : 设所求近似根与精确解的差的绝对值不超过 =0.005.第一步 :令 f(x)=x2-2.因为 f(1)0,所以设 a=1,b=2.第二步 :令 判断 f(m)是否为 0.若否 ,则继续判断 f(a) (m)大于 0还是小于 0.第三步 :若 f(a) (m)0,则令 a=m;否则 ,令 b=m.第四步 :判断 |a-b|7时 )解 :y与 x之间的函数关系为 :(当 0x7时 )(当 x7时 )求该函数值的算法分析 :第一步 :输入每月用水量 x;第二步 :判断 x是否不超过 7.若是 ,则y=1.2x;若否 ,则 y=1.9x-4.9.第三步 :输出应交纳的水费 y.作业 :课本 P6页 T2(只需用自然语言写出算法步骤 ) 1.1.2 程序框图 学习目标 :(1)在具体问题的解决过程中 ,掌握基本的程序框图的画法 ,理解程序框图的三种基本逻辑结构 -顺序结构、条件结构、循环结构。(2)通过模仿、操作、探索，经历通过设计程序框图表达解决问题的算法的过程。学习重点 :通过模仿、操作、探索，经历通过设计程序框图表达求解问题的过程，在具体问题解决过程中，理解程序框图的三种基本逻辑结构 .学习难点 :用程序框图清晰表达含有循环结构的算法 .例 1:任意给定一个大于 1的整数 n,试设计一个程序或步骤对 n是否为质数做出判定 .算法分析 :第一步 :判断 n是否等于 2. 若 n=2,则 n是质数 ;若 n2,则执行第二步 .第二步 :依次检验 2(n-1)这些整数是不是 n的因素 ,即是不是整除 n的数 .若有这样的数 ,则 n不是质数 ;若没有这样的数 ,则 n是质数 .从上节课我们知道 :算法可以用自然语言来描述 .如例 1为了使算法的程序或步骤表达得更为直观 ,我们更经常地用图形方式来表示它 .开始输入 ni=2求 n除以 i的余数 ri的值增加 1仍用 i表示in或 r=0?n不是质数结束是否是 n是质数否r=0?设 n是一个大于 2的整数 .一般用 i=i+1表示 .i=i+1说明 :i表示从 2(n-1)的所有正整数 ,用以判断例 1步骤 2是否终止 ,i是一个计数变量 ,有了这个变量 ,算法才能依次执行 .逐步考察从 2(n-1)的所有正整数中是否有 n的因数存在 .思考 ?通过上述算法的两种不同表达方式的比较,你觉得用程序框图来表达算法有哪些特点 ?用程序框图表示的算法更加简练 ,直观 ,流向清楚. 程序框图 又称 流程图 ,是一种用规定的图形、指向线及文字说明来准确、直观地表示算法的图形 .通常 ,程序框图由程序框和流程线组成 .一个或几个程序框的组合表示算法中的一个步骤;流程线是方向箭头 ,按照算法进行的顺序将程序框连接起来 .基本的程序框和它们各自表示的功能如下 :图形符号 名称 功能终端框 (起止框 )表示一个算法的起始和结束输入、输出框表示一个算法输入和输出的信息处理框 (执行框 )判断某一条件是否成立 ,成立时在出口处标明 “是 ”或 “Y”；不 ”成立时标明 “否 ”或 “N”.判断框赋值、计算流程线 连接程序框连接点 连接程序框图的两部分开始输入 ni=2求 n除以 i的余数 ri=i+1in或 r=0?n不是质数结束是否是 n是质数否r=0?顺序结构用程序框图来表示算法，有三种不同的基本逻辑结构：条件结构循环结构程序框图的三种基本的逻辑结构顺序结构条件结构循环结构(1)顺序结构 -是由若干个依次执行的处理步骤组成的 .这是任何一个算法都离不开的基本结构 . 例 1:已知一个三角形的三边边长分别为 2,3,4,利用海伦 -秦九韶公式设计一个算法 ,求出它的面积 ,画出算法的程序框图 .算法分析 :第一步 :计算 p的值 .第二步 :由海伦 -秦九韶公式求出三角形的面积S.第三步 :输出 S的值 .已知三角形三边长分别为 a,b,c,则三角形的面积为其中 这个公式被称为海伦 秦九韶公式 .程序框图 :开始输出 S结束(2)条件结构 -在一个算法中 ,经常会遇到一些条件的判断 ,算法的流向根据条件是否成立有不同的流向 .条件结构就是处理这种过程的结构 .例 2:任意给定 3个正实数 ,设计一个算法 ,判断分别以这 3个数为三边边长的三角形是否存在 .画出这个算法的程序框图 .算法分析 :第一步 :输入 3个正实数 a,b,c;第二步 :判断 a+bc,a+cb,b+ca是否同时成立 ,若是 ,则能组成三角形 ;若否 ,则组不成三角形 .程序框图 : 开始输入 a,b,ca+bc,a+cb,b+ca是否同时成立 ?是存在这样的三角形不存在这样的三角形否结束例 3:为了加强居民的节水意识 ,某市制订了以下生活用水收费标准 :每户每月用水未超过7m3时 ,每立方米收费 1.0元 ,并加收 0.2元的城市污水处理费 ;超过 7m3的部分 ,每立方米收费1.5元 ,并加收 0.4元的城市污水处理费 ,请你写出某户居民每月应交纳的水费 y(元 )与用水量x(m3)之间的函数关系 ,然后设计一个求该函数值的算法 ,并画出程序框图 .解 :y与 x之间的函数关系为 :(当 0x7时 )(当 x7时 )解 :y与 x之间的函数关系为 :(当 0x7时 )(当 x7时 )算法分析 :第一步 :输入每月用水量x;第二步 :判断 x是否不超过 7.若是 ,则 y=1.2x;若否 ,则 y=1.9x-4.9.第三步 :输出应交纳的水费 y.开始输入 x0x7?是y=1.2x否y=1.9x-4.9输出 y结束程序框图例 4.画程序框图 ,对于输入的