111算法的概念1

1 1 1算法的概念 计算机与算法 在现代社会里 计算机已经成为人们日常生活和工作不可缺少的工具 听音乐 看电影 玩游戏 画卡通画 处理数据 计算机几乎可以是一个全能的助手 你可以用它来做你想做的任何事情 那么 计算机是怎样工作呢 要想弄清楚这个问题 就需要学习算法 什么是算法 发电子邮件的方法很多 下面是其中的一种操作步骤 新课导入 假如你的朋友不会发电子邮件 你怎么教会他 假设家中生火泡茶有以下几个步骤 a 生火b 将水倒入锅中c 找茶叶d 洗茶壶茶碗e 用开水冲茶请选出一个最优方案 A abcdeB bacdeC cadbeD dcabe 背景 广义的算法是指完成某项工作的方法和步骤 那么我们可以说洗衣机的使用说明书是操作洗衣机的算法 菜谱是做菜的算法等等 我们做任何事情都是在一定条件下按某种顺序执行的一系列操作 解决数学问题也是如此 例如用加减消元法解二元一次方程组时 就可以按照某一步骤进行操作 第二步 解 得 第三步 2得5y 3 第四步 解 得 你能写出解一般的二元一次方程组的步骤吗 第一步 第二步 解 3 得 第四步 解 4 得 第三步 第五步 得到方程组的解为 在数学中 算法通常是指按照一定规则解决某一类问题的明确和有限的步骤 现在 算法通常可以编成计算机程序 让计算机执行并解决问题 2 算法的要求 1 写出的算法 必须能解决一类问题 例如解任意一个二元一次方程组 并且能重复使用 2 算法过程要能一步一步执行 每一步执行的操作 必须确切 不能含混不清 而且在有限步之内完成后能得出结果 1 算法的定义 探究新知 3 算法的基本特征 明确性 算法对每一个步骤都有确切的 非二义性的规定 即每一步对于利用算法解决问题的人或计算机来说都是可读的 可执行的 而不需要计算者临时动脑筋 有效性 算法的每一个步骤都能够通过基本运算有效地进行 并得到确定的结果 对于相同的输入 无论谁执行算法 都能够得到相同的最终结果 有限性 算法应由有限步组成 至少对某些输入 算法应在有限多步内结束 并给出计算结果 信息输出 一个算法至少要有一个有效的信息输出 这就是问题求解的结果 不唯一性 求解某一个题的解法不一定是唯一的 对于一个问题可以有不同的算法 数据输入 算法一定要根据输入的初始数据或给定的初值才能正确执行它的每一步骤 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 两点连线的方程可先求MN的斜率再利用点斜式方程求得 A 1个B 2个C 3个D 4个 C 鸡兔同笼问题 我有2条腿一个脑袋 我有4条腿一个脑袋 问题1 一群小兔一群小鸡 两群合到一群中 腿一共有48条 脑袋共有17个 问一共有多少小鸡 多少小兔 解决步骤 1 设未知数 设有x只小鸡 y只小兔X Y 172 列方程组 2X 4Y 483 解方程组 X 10y 74 得到实际问题的答案 小鸡10只 小兔7只 例题 例2 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 变式 设计一个算法 判断35是否为质数 第一步 用2除35 得余数1 因为余数不是0 所以2不能除35 第二步 用3除35 得余数2 因为余数不是0 所以3不能除35 第三步 用4除35 得余数3 因为余数不是0 所以4不能除35 第四步 用5除35 得余数0 因为余数是0 所以5能除35 因此 35不是质数 变式 任意给定一个大于2的整数n 试设计一个程序或步骤对n是否为质数做出判断 例题 第一步 给定大于2的整数n 第二步 令i 2 第三步 用i除n 得到余数r 第四步 判断 r 0 是否成立 若是 则n不是质数 结束算法 否则 将i的值增加1 仍用i表示 即 i i 1 第五步 判断 i n 1 是否成立 若是 则n是质数 结束算法 否则 将返回第3步 1 任意给定一个正实数a 试设计一个算法求以a为直径的圆的面积 第一步 输入a的值 第二步 第三步 第四步 输出圆的面积的值 解 练习 计算 计算 例2 用二分法设计一个求方程的近似根的算法 对于区间 a b 上连续不断 且f a f b 0的函数y f x 通过不断地把函数f x 的零点所在的区间一分为二 使区间的两个端点逐步逼近零点 进而得到零点或其近似值的方法叫做二分法 二分法的基本思想 分析 第四步 若f a f m 0 则含零点的区间为 a m 否则 含零点的区间为 m b 第二步 给定区间 a b 满足f a f b 0 第三步 取中间点 第五步 判断f m 是否等于 或者 a b 的长度是否小于d 若是 则m是方程的