1213高一数学 111 算法的概念课件2 新人教A版必修3.ppt

1 1 1算法的概念 例1 有鸡 兔同笼 共48条腿 17只头 问鸡 兔各多少 解析 算术解法 假定全为小鸡 应有腿2 17 34条 现有48条腿 是因为将小兔看成鸡每只减少了两条腿 故应有小兔 7只 鸡应有10只 点评 1 想一想还可以怎样解 方程解法 设有x只鸡 y只小兔 将 的两边同乘以 2加到 中得 2y 14 解 得 y 7 将y 7代入 中得x 10 2 把解决问题的程序或步骤用语言表述出来 就是解决这个问题的算法 解析 s1计算d a1b2 b1a2 s2如果d 0 则原方程组无解或者有无穷多组解 否则 d 0 s3输出计算的结果x y或者无法求解信息 点评 教材上本例是我们求解这类二元一次方程组的一般步骤 我们把这个步骤提炼简化让计算机执行可得到上面的算法 例2 给出求1 2 3 4 5 6的值的一个算法 解析 算法1 按照逐一相加的程序进行 s1计算1 2得3 s2将s1中的运算结果3与3相加得6 s3将s2中的运算结果6与4相加得10 s4将s3中的运算结果10与5相加得15 s5将s4中的运算结果15与6相加得21 点评 算法2是运用已知的结果作为公式进行计算 算法1更切合 算法 的含义 描述求解mul 1 2 3 4 5 6 7 8的算法 解析 解法1 s1计算1 2得2 s2将第一步中的运算结果2与3乘得6 s3将第二步中的运算结果6与4乘得24 s4将第三步中的运算结果24与5乘得120 s5将第四步中的运算结果120与6乘得720 s6将第五步中的运算结果720与7乘得5040 s7将第六步中的运算结果5040与8乘得40320 还可以将此算法改造得更加简练 科学 解法2 s1设i 1 p 1 s2如果i 8 执行第三步s3 否则执行第五步s5 s3计算p i并用结果代替p s4将i用i 1代替 转去执行s2 s5输出p 点评 i称作计数变量 每一次循环它的值增加1 并从1变到8 p是一个累乘变量 每一次循环后得到一个新的结果 并由新结果替代原值 例3 在下列数字序列中 写出搜索89的算法 21 3 0 9 15 72 89 91 93 解析 s1先将序列中的第一个数赋给m m 21 s2将m与89比较 看是否相等 如果相等 则搜索到89 如果m与89不相等 则往下执行 s3继续将序列中的下一个数赋给m 重复s2 直到搜索到89 点评 1 有的同学可能不以为然 认为89我一眼就能看到 何必费上面许多周折 其实这是没有理解算法思想的缘故 只有以上这几个数 你一眼就能看穿 假如让你从有一百万人口的城市户籍中寻找满足某特征的一个人就不是件容易事了 而只要我们按上面解析设计出算法编出程序 计算机会马上给出结果 这正是我们研究算法的原因所在 2 如果事先确知 这一数字序列中仅有一个89 则用上述算法 假如这一序列中 不止一个89 请想一想怎样修改算法 才能符合要求 一位商人有9枚银元 其中有1枚略轻的是假银元 你能用天平 无砝码 将假银元找出来吗 写出解决这一问题的一种算法 解析 最容易想到的解决该问题的办法是 把9枚银元按顺序排成一列 先称前2枚 若不平衡 则可找出假银元 若平衡 则2枚银元都是真的 再依次与剩下的银元作称量比较 就能找出假银元 算法步骤如下 s1任取2枚银元分别放在天平的两边 如果天平左右不平衡 则轻的那一边就是假银元 如果天平平衡 则进行第二步 s2取下右边的银元 放在一边 然后把剩下的7枚银元依次放在右边进行称量 直到天平不平衡 偏轻的那一边就是假银元 点评 1 对于这种非数值型问题的算法设计问题 应当首先建立过程模型 根据过程设计步骤 完成算法 2 解决此问题的算法有好多 如 算法2 s1任取两枚银元分别放在天平的两端 如果左右不平衡 则轻的那一边是假银元 否则进行第二步 s2重复执行s1 到第4次称量时如果平衡 则剩下的那一枚是假银元 算法1至少称量1次 最多称量7次 算法二至少称量1次 最多称量4次 仔细分析我们还可以有如下更好的算法 算法3 算法步骤如下 第一步 把9枚银元平均分成3组 每组3枚 第二步 先将其中两组放在天平的两边 如果天平不平衡 那么假银元就在轻的那一组 如果天平左右平衡 则假银元就在未称量的那一组里 第三步 取出含假银元的那一组 从中任取2枚银元放在天平左右两边进行称量 如果天平不平衡 则假银元在轻的那一边 若天平平衡 则未称的那一枚就是假银元 这样利用上述算法 只需2次称量就可以将假银元找出来 显然要比第一种算法简洁 有效 这说明算法的设计有最优化问题 尽管如此我们主要精力应放在对算法概念的理解上 初学千万莫在算法的最优化设计上下功夫 舍本逐末 例4 设计一个能够找出a b c d四个数中最小值的算法 a b c d两两不同 解析 s1假定最小值为min 使min a s2如果b min 则用b的值替换min的值 否则min还是原来的值 s3如果c min 则用c的值替换min的值 否则min还是原来的值 s4如果d min 则用d的值替换min的值 否则min还是原来的值 s5输出min 写出一个能从a b c三个不同数中 找出最大值的算法 解析 s1假设max a s2如果b max 则max取原来的值 否则max取b的值 s3如果c max 则max取原来的值 否则max取c的值 s4输出max 例5 用自然语言描述求y x2 2x 3的最大值的算法 错解 第一步配方得y x 1 2 4 第二步函数的最大值为4 辨析 作为一个具体问题来说 上述解法没有什么错误 但是我们要描述的是求这一类问题的算法 它可以用来解决这个问题 也可以用来求