高中数学1.1.1算法的概念课件新课标人教B必修3.ppt

1 1 1算法的概念 算法作为一个名词 在中学教科书中并没有出现过 我们在基础教育阶段还没有接触算法概念 但是我们却从小学就开始接触算法 熟悉许多问题的算法 如 做四则运算要先乘除后加减 从里往外脱括弧 竖式笔算等都是算法 至于乘法口诀 珠算口诀更是算法的具体体现 我们知道解一元二次方程的算法 求解一元一次不等式 一元二次函数图象的画法 解线性方程组的算法 求两个数的最大公因数的算法等 因此 算法其实是重要的数学对象 一 算法的概念 算法 algorithm 一词源于算术 algorism 即算术方法 是指一个由已知推求未知的运算过程 后来 人们把它推广到一般 把进行某一工作的方法和步骤称为算法 广义地说 算法就是做某一件事的步骤或程序 菜谱是做菜肴的算法 洗衣机的使用说明书是操作洗衣机的算法 歌谱是一首歌曲的算法 在数学中 主要研究计算机能实现的算法 即按照某种机械程序步骤一定可以得到结果的解决问题的程序 比如解方程的算法 函数求值的算法 作图的算法 等等 例1 一群小兔一群鸡 两群合到一群里 要数腿共48 要数脑袋整17 多少小兔多少鸡 解 算术方法 如果没有小兔 那么小鸡应为17只 总的腿数应为2 17 34条 但现在有48条腿 造成腿的数目不够是由于小兔的数目为0 每有一只小兔便会增加两条腿 故应有 48 17 2 2 7只小兔 相应的 小鸡有10只 代数方法 设有x只小鸡 y只小兔 则 将第一个方程的两边同乘以 2加到第二个方程中去 得到 解第二个方程得y 7 把y代入到第一个方程得x 10 思考1教材中例1是著名的 鸡兔同笼 问题 其中第一种解法是算术方法 教材中对它的评价是 简单直观 却包含着深刻的算法思想 那么它是如何体现算法的思想呢 s1假设没有小兔 则小鸡应为n只 s2计算总腿数为2n只 s3计算实际总腿数与假设总腿数的差值为m 2n s4计算小兔只数为 s5小鸡的只数为n 思考2教材中例1的第二种解法是列方程组的方法 它是否也是一种算法呢 探究 是的 其算法步骤为 s1设未知数 s2根据题意列方程组 s3解方程组 s4还原实际问题 得到实际问题的答案 在实际中 很多问题可以归结为求解二元一次方程组 下面我们用消元法来解一般的二元一次方程组 s1假定a11 0 a11 a21得 s2如果a11a22 a12a21 0 则执行下步 否则执行s6 s3 两边同除以a11a22 a12a21 0得 s4 代入 得 s5输出结果x1 x2 s6若a11b2 a21b1 0 则执行下一步 否则执行s8 s7输出 方程组无解 s8输出 方程组有无穷多个解 以上解二元一次方程组的方法 叫做高斯消去法 二 算法的特点 不论在哪一种算法中 它们都是经有限次步骤完成的 因而它们体现了算法的有穷性 在算法中 每一步都能明确地执行 且有确定的结果 因此具有确定性 在所有算法中 每一步操作都是可以执行的 也就是具有可行性 为了便于计算机运算 它们必须先输入已知数据 而计算的目的分别是解方程组和求最大值等 因此必须输出结果 也就是必须有输入和输出 算法解决的都是一类问题 分别是解决求方程组的解和确定一个有理整数序列中的最大值问题 因此具有普适性 体验 写出解方程x2 2x 3 0的一个算法 配方法 s1移项 得x2 2x 3 s2 式两边同加1并配方得 x 1 2 4 s3 式两边开方 得x 1 2 s4解 式得x 3或x 1 因式分解法 s1将方程左边因式分解得 x 3 x 1 0 s2由 得x 3 0或x 1 0 s3解 得x 3或x 1 公式法 s1计算方程的判别式 判断其符号 2 2 4 3 0 s2将a 1 b 2 c 3代入求根公式 得x 3或x 1 例2写出一个求有限整数列中的最大值的算法 解 算法如下 s1先假定序列中的第一个整数为 最大值 s2将序列中的下一个整数值与 最大值 比较 如果它大于此 最大值 这时你就假定 最大值 是这个整数 s3如果序列中还有其他整数 重复s2 s4在序列中一直到没有可比的数为止 这时假定的 最大值 就是这个序列中的最大值 如果让你去找 你可能不会这样做 可能认为 这样太机械 太枯燥 不要忘了 我们写的是算法 算法要求按部就班地做 每一步都有唯一的结果 又要求写出的算法对任意整数序列都适用 总能得到结果 所以上面写的 符合算法的要求 下面我们用数学语言 写出对任意3个整数a b c求出最大值的算法 s1max as2如果b max 则max b s3如果c max 则max c s4max就是a b c中的最大值 例3写出求1 2 3 4 5 6的一个算法 解 算法1 s1计算1 2得到3 s2将第一步中的运算结果3与3相加得到6s3将第二步中的运算结果6与4相加得到10s4将第三步中的运算结果10与5相加得到15s5将第四步中的运算结果15与6相加得到21 算法2 s1 取n 6 s2 计算s3 输出运算结果 算法3 s1将原式变形为 1 6 2 5 3 4 3 7 s2计算3 7 s3输出运算结果 例4 求1 3 5 7 9 11的值 写出其算法 算法1 第一步 先求1 3 得到结果3 第二步 将第一步所得结果3再乘以5 得到结果15 第三步 再将15乘以7 得到结果105 第四步 再将105乘以9 得到945 第五步 再将945乘以11 得到10395 即是最后结果 算法2 用p表示被乘数 i表示乘数 s1使p 1 s2使i 3 s3使p p i s4使i i 2 s5若i 11 则返回到s3继续执行 否则算法结束 由于计算机动是高速计算的自动机器 实现循环的语句可以在很短的时间内完成 对于循环结构的详细情况 我们将在以后的学习中介绍 例6 利用二分法求函数y f x x在定义区间d 上的一个变号零点x0的近似值x 使它与零点的误差不超过正数 即使 x x0 写出它的一个算法 s1在d内取一个闭区间 a b 使f a 与f b 异号 即f a f b 0 s2令x0 计算f x0 s3若f x0 0 则x0就是y f x 的零点 若f x0 与f a 异号 则a a b x0 否则a x0 b b s4判断 a b 是否成立 若成立 则区间 a b 内任意实数都是x0的近似值 否则 返回s2 直到不等式 a b 成立为止 s5输出x0 例7 设计算法解决下面的问题 已知点p的坐标为 x0 y0 直线l的方程为ax by c 0 ab 0 求点p到直线l的距离 算法一 s1求出直线l的斜率为k s2求出与l垂直的直线的斜率k s3求出过点p且与直线l垂直的直线l 方程 直线l 的方程为 s4求出直线l和l 的交点m的坐标 把l和l 联立 得方程组 由此可以得到点m的坐标为 s5把点m的横坐标和纵坐标分别赋值给变量x1 y1 s6把点 x1 y1 代入两点间距离公式 计算求得d的值 算法二 s1计算的值s2计算z0 ax0 by0 c 的值 s3计算得所求的距离 例8一位商人有9枚银元 其中有1枚略轻的是假银元 你能用天平 不用砝码 将假银元找出来吗 算法一 s1任取2枚银元分别放在天平的两边 如果天平左右不平衡 则轻的一边就是假银元 如果天平平衡 则进行s2 s2取下右边的银元放在一边 然后把剩余的7枚银元依次在右边进行称量 直到天平不平衡 偏轻的那一枚就是假银元 算法二 s1任取2枚银元分别放在天平的两边 如果天平左右不平衡 则轻的一边就是假银元 如果天平平衡 则进行s2 s2从余下的7枚银元中再任取2枚分别放在天平的两边 如果天平左右不平衡则轻的一边就是假银元 如果天平平衡 则进行s3 s3从余下的5枚银元中再任取2枚分别放在天平的两边 如果天平左右不平衡 则轻的一边就是假银元 如果天平平衡 则进行s4 s4从余下的3枚银元中再任取2枚分别放在天平的两边 如果天平左右不平衡 则轻的一边就是假银元 如果天平平衡 则最后剩下的还未称的1枚银元就是假银元 算法三 s1任取4枚银元分别放在天平的两边 各2枚 如果天平左右不平衡 则轻的一边中含有假银元 并进行s2 如果天平平衡 则进行s3 s2将轻的一边的两枚银元分别放在天平的两边 则轻的一边的那枚银元就是假银元 称量结束 s3从余下的5枚银元中再任取4枚分别放在天平的两边 各2枚 如果天平左右不平衡 则轻的一边就含有假银元 并转向s2 如果天平平衡 则最后剩下的还未称的1枚银元就是假银元 称量结束 算法四 s1把银元分成3组 每组3枚 s2先将两组分别放在天平的两边 如果天平不平衡 那么假银元就在轻的那一组 如果天平左右平衡 则假银元就在未称的第3组里 s3取出含假银元的那一组 从中任取两枚银元放在天平的两边 如果左右不平衡 则轻的那一边就是假银元 如果天平两边平衡 则未称的那一枚就是假银元 1 下面的四种叙述不能称为算法的是 a 广播的广播操图解 b 歌曲的歌谱 c 做饭用米 d 做米饭需要刷锅 淘米 添水 加热这些步骤 练习题 c 2 下列关于算法的说法正确的是 a 某算法可以无止境地运算下去 b 一个问题的算法步骤可以是可逆的 c 完成一件事情的算法有且只有一种 d 设计算法要本着简单 方便 可操作的原则 d 3 下列关于算法的说法中 正确的是 a 算法就是某个问题的解题过程b 算法执行后可以不产生确定的结果c 解决某类问题的算法不是惟一的d 算法可以无限地操作下去不停止 c 4 下列运算中不属于我们所讨论算法范畴的是 a 已知圆的半径求圆的面积b 从一副扑克牌随意抽取3张扑克牌抽到24点的可能性c 已知坐标平面内的两点求直线的方程d 加减乘除运算法则 b 5 下列语句表达中是算法的有 从济南到巴黎可以先乘火车到北京再坐飞机抵达 利用公式s ah 2计算底为1高为2的三角形的面积 x 2x 4 求m 1 2 与n 3 5 两点连