第一章 算法初步1.1.1算法的概念.ppt

算法 1 1 1算法的概念 答 分三步 第一步 打开冰箱门 第二步 把大象装冰箱 第三步 把冰箱门关上 问 要把大象装冰箱 分几步 一 问题情境 1 小品 钟点工 片段 2 现有九枚硬币 有一枚略重 你能用天平 不用砝码 将其找出来吗 设计一种方法 解决这一问题 一 问题情境 第一步 把九枚硬币平均分成三份 取其中两份放天平上称 若平衡则重的在剩下的一份里 若不平衡则在重的一份里 第二步 在重的一份里取两枚放天平的两边 若平衡则剩下的一枚就是所找的 若不平衡则重的那枚就是所要找的 3 猜商品价格 第一步报4000 第二步若正确 就结束 若高了 则报2000 若低了 则报6000 第三步重复第二步的报数方法 直到得出正确结果 一 问题情境 一商品价格在0 8000元之间 问竞猜者采取什么策略才能在较短时间内猜出商品价格 解 第一步 由 得x 2y 1 第二步 将 代入 解得y 3 5 思考 对于一般的二元一次方程组来说 上述步骤应该怎样进一步完善 问题一 第三步 将 代入 解得x 1 5 算法的含义 广义 完成某项工作的方法和步骤 现代 可以用计算机来解决的一类问题的程序和步骤 教材 在数学中 算法通常是按照一定规则解决某一类问题的明确和有限的步骤 1 程序性 2 明确性 3 有限性 算法的特点 例1 设计一个算法 判断7是否为质数 算法 第一步 用2除7 得到余数1 因为余数不为0 所以2不能整除7 第二步 用3除7 得到余数1 因为余数不为0 所以3不能整除7 第三步 用4除7 得到余数3 因为余数不为0 所以4不能整除7 第四步 用5除7 得到余数2 因为余数不为0 所以5不能整除7 第五步 用6除7 得到余数1 因为余数不为0 所以6不能整除7 因此 7是质数 35 例2 设计一个算法 判断53是否为质数 第一步 用2除53 得到余数1 因为余数不为0 所以2不能整除53 第二步 用3除53 得到余数2 因为余数不为0 所以3不能整除53 第三步 用4除53 得到余数1 因为余数不为0 所以4不能整除53 第五十一步 用52除53 得到余数1 因为余数不为0 所以52不能整除53 因此 53是质数 不是算法 算法分析 根据质数的定义 很容易设计出下面的步骤 第一步 判断n是否等于2 若n 2 则n是质数 若n 2 则执行第二步 第二步 令i 2 例3任意给定一个大于1的整数n 试设计一个程序或步骤对n是否为质数做出判定 第三步 用i除n 得到余数是r 第四步 判断r是否为0 若是 则n不是质数 否则 将i的值增加1 仍用i表示 第五步 判断i n 1 是否成立 若是 则n是质数 结束算法 否则 返回第三步 例4 用二分法设计一个求方程x2 2 0的近似根的算法 算法分析 回顾二分法解方程的过程 并假设所求近似根与准确解的差的绝对值不超过0 005 则不难设计出以下步骤 第一步 令f x x2 2 因为f 1 0 所以a 1 b 2 第二步 令m a b 2 判断f m 是否为0 若是 则m为所求 若否 则继续判断f a f m 大于0还是小于0 第三步 若f a f m 0 则令a m 否则 令b m 第四步 判断 a b 0 005是否成立 若是 则a b之间的任意取值均为满足条件的近似