【优教通-备课参考】2020年高中数学同步学案：第2章-算法初步-算法的概念文字(北师大版必修3).docx

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