高中数学《算法与程序框图-算法的概念》文字素材2 新人教A版必修3

用心 爱心 专心1 1 1 11 1 1 算法的概念算法的概念 算法是指完成一个任务所需要的具体步骤和方法 也就是说给定初始状态或输入数据 经过计算机程序的有限次运算 能够得出所要求或期望的终止状态或输出数据 算法常常含有重复的步骤和一些比较或逻辑判断 如果一个算法有缺陷 或不适合于某个 问题 执行这个算法将不会解决这个问题 不同的算法可能用不同的时间 空间或效率来 完成同样的任务 一个算法的优劣可以用空间复杂度与时间复杂度来衡量 算法的历史 算法 algorithm 来自于 9 世纪波斯数学家比阿勒 霍瓦里松的名字 al Khwarizmi 比阿勒 霍瓦里松在数学上提出了算法这个概念 算法 原为 algorism 意思是阿拉 伯数字的运算法则 在 18 世纪演变为 algorithm 第一次编写算法是 Ada Byron 于 1842 年为巴贝奇分析机编写求解解伯努利方程的程序 因此 Ada Byron 被大多数人认为是 世界上第一位程序员 因为巴贝奇 Charles Babbage 未能完成他的巴贝奇分析机 这个算 法未能在巴贝奇分析机上执行 因为 well defined procedure 缺少数学上精确的定义 19 世纪和 20 世纪早期的数学家 逻辑学家在定义算法上出现了困难 20 世纪的英国数学 家图灵提出了著名的图灵论题 并提出一种假想的计算机的抽象模型 这个模型被称为图 灵机 图灵机的出现解决了算法定义的难题 图灵的思想对算法的发展起到了重要的作用 算法的特征 一个算法应该具有以下五个重要的特征 有穷性 一个算法必须保证执行有限步之后结束 确切性 算法的每一步骤必须有确切的定义 输入 一个算法有 0 个或多个输入 以刻画运算对象的初始情况 所谓 0 个输入是指 算法本身定除了初始条件 输出 一个算法有一个或多个输出 以反映对输入数据加工后的结果 没有输出的算 法是毫无意义的 可行性 算法原则上能够精确地运行 而且人们用笔和纸做有限次运算后即可完成 形式化算法 算法是计算机处理信息的本质 因为计算机程序本质上是一个算法来告诉计算机确切的步 骤来执行一个指定的任务 如计算职工的薪水或打印学生的成绩单 一般地 当算法在处 用心 爱心 专心2 理信息时 会从输入设备或数据的存储地址读取数据 把结果写入输出设备或某个存储地 址供以后再调用 算法的实现 算法不单单可以用计算机程序来实现 也可以在神经网络 电路或者机械设备上实现 例子 这是算法的一个简单的例子 我们有一串随机数列 我们的目的是找到这个数列中最大的数 如果将数列中的每一个数 字看成是一颗豆子的大小 可以将下面的算法形象地称为 捡豆子 首先将第一颗豆子放入口袋中 从第二颗豆子开始检查 直到最后一颗豆子 如果正在检查的豆子比口袋中的还大 则将 它捡起放入口袋中 同时丢掉原先口袋中的豆子 最后口袋中的豆子就是所有的豆子中最大的一颗 下面是一个形式算法 用近似于编程语言的伪代码表示 给定 一个数列 list 以及数列的长度 length list largest list 1 for counter 2 to length list if list counter largest largest list counter print largest 符号说明 用于表示赋值 即 右边的值被赋予给左边的变量 List counter 用于表示数列中的第 counter 项 例如 如果 counter 的值是 5 那么 List counter 表示数列中的第 5 项 用于表示 小于或等于 例子 求两个自然数的最大公约数 设两个变量 M 和 N 1 如果 M N 则交换 M 和 N 2 以 N 除以 M 得到余数 R 3 判断 R 0 正确则 N 即为 最大公约数 否则下一步 4 将 N 赋值给 M 将 R 赋值给 N 重做第一步 用 Basic 代码 表示 用心 爱心 专心3 If M N Then Swap M N Do While R 0 R M Mod N M N N R Loop Print R 算法设计和分析的基本方法 分治法 字面上的解释是 分而治之 就是把一个复杂的问题分成两个或更多的相同或 相似的子问题 再把子问题分成更小的子问题 直到最后子问题可以简单的直接求解 原问题的解即子问题的解的合并 这个技巧是很多高效算法的基础 如排序算法 快速排序 归并排序 傅立叶变换 快速傅立叶变换 动态规划 动态规划在查找有很多重叠子问题的情况的最优解时有效 它将问题重新组合 成子问题 为了避免多次解决这些子问题 它们的结果都逐渐被计算并被保存 从简单的 问题直到整个问题都被解决 因此 动态规划保存递归时的结果 因而不会在解决同样的 问题时花费时间 贪心法 亦作饕餮法 就是一种在每一步选择中都采取在当前状态下最好 优的选择 从 而希望导致结果是最好 优的算法 贪心法可以解决一些最优性问题 如 求图中的最小生 成树 求哈夫曼编码 对于其他问题 贪心法一般不能得到我们所要求的答案 一旦一 个问题可以通过贪心法来解决 那么贪心法一般是解决这个问题的最好办法 由于贪心法 的高效性以及其所求得的答案比较接近最优结果 贪心法也可以用作辅助算法或者直接解 决一些要求结果不特别精确的问题 算法的分类 基本算法 枚举 搜索 深度优先搜索 广度优先搜索 启发式搜索 遗传算法 数据结构的算法 数论与代数算法 计算几何的算法 凸包算法 图论的算法 哈夫曼编码 树的遍历 最短路径算法 最小生成树算法 最小树形图 网络 流算法 匹配算法 动态规划 用心 爱心 专心4 其他 数值分析 加密算法 排序算法 检索算法 随机化算法 还可以分成串行算法 并行算法 算法的复杂性 算法的复杂性是算法效率的度量 在评价算法性能时 复杂性是一个重要的依据 算法的 复杂性的程度与运行该算法所需要的计算机资源的多少有关 所需要的资源越多 表明该 算法的复杂性越高 所需要的资源越少 表明该算法的复杂性越低 计算机的资源 最重要的是运算所需的时间和存储程序和数据所需的空间资源 算法 的复杂性有时间复杂性和空间复杂性之分 算法在计算机上执行运算 需要一定的存储空间存放描述算法的程序和算法所需的数 据 计算机完成运算任务需要一定的时间 根据不同的算法写出的程序放在计算机上运算 时 所需要的时间和空间是不同的 算法的复杂性是对算法运算所需时间和空间的一种度 量 不同的计算机其运算速度相差很大 在衡量一个算法的复杂性要注意到这一点 对于任意给定的问题 设计出复杂性尽可能低的算法是在设计算法时考虑的一个重要 目标 另外 当给定的问题已有多种算法时 选择其中复杂性最低者 是在选用算法时应 遵循的一个重要准则 因此 算法的复杂性分析对算法的设计或选用有着重要的指导意义 和实用价值 在讨论算法的复杂性时 有两个问题要弄清楚 1 一个算法的复杂性用怎样的一个量来表达 2 怎样计算一个给定算法的复杂性 找到求解一个问题的算法后 接着就是该算法的实现 至于是否可以找到实现的方法 取决于算法的可计算性和计算的复杂性 该问题是否存在求解算法 能否提供算法所需要 的时间资源和空间资源 筛选法求质数 质数亦叫作素数 是大于 1 的自然数 并且除了该数本身和 1 以外没有其它的数能整除它 如 2 3 5 7 11 13 质数有无穷多个 1 判断 143 是否为质数 解 Step1 143 2 不为整数 Step2 143 3 不为整数 Step3 143 4 不为整数 Step4 143 5 不为整数 Step5 143 6 不为整数 Step6 143 7 不为整数 Step7 143 8 不为整数 Step8 143 9 不为整数 Step9 143 10 不为整数 Step10 143 11 13 143 能被 11 整除 Step11 结论 143 不是质数 2 判断 17 是否为质数 解 用心 爱心 专心5 Step1 17 2 不为整数 Step2 17 3 不为整数 Step3 17 4 不为整数 Step4 17 5 不为整数 Step5 17 6 不为整数 Step6 17 7 不为整数 Step7 17 8 不为整数 Step8 17 9 不为整数 Step9 17 10 不为整数 Step10 17 11 不为整数 Step11 17 12 不为整数 Step12 17 13 不为整数 Step13 17 14 不为整数 Step14 17 15 不为整数 Step15 17 16 不为整数 Step16 结论 17 是质数 3 判断 216