C语言程序设计课件 第11章

第11章计算机算法基础11.1常用算法11.2查找算法11.3排序算法本章小结

11.1常用算法

11.1.1迭代法迭代法也称辗转法，是一种不断用变量的旧值递推新值的方法，通常用于解决无法直接求解或者求解较为复杂的问题。迭代法的基本思想是将一个复杂问题的求解过程转化为相对简单的迭代算式，然后从一个初始值开始，通过不断迭代运算，逐步逼近问题的解，直到满足预设的精度要求或者收敛条件为止。

迭代分为精确迭代和近似迭代。精确迭代是指迭代算法本身提供了问题的精确解。如最大公约数、进制转换、质因数的分解等问题都适合使用精确迭代来解决。而近似迭代是指迭代算法不能得到精确解，只能通过控制迭代次数或精度使解无限逼近精确解，可用于解决优化问题、数值积分等问题。比如，在机器学习中，梯度下降法就是一种典型的近似迭代算法，它通过不断地调整模型参数来最小化损失函数，从而得到最优的模型。求解方程根常用的“二分法”和“牛顿迭代法”也属于近似迭代。

例11-1任意给出两个正整数m和n，求它们的最大公约数和最小公倍数。

解题思路利用辗转法求最大公约数，然后根据最大公约数得到最小公倍数，迭代方法如下：

(1)用m对n求余，余数记作r，即有语句r=m%n；

(2)将除数作为被除数，余数作为除数求新的余数，即m=n，n=r；

(3)重复执行步骤(2)，直到余数为0为止，此时n即为最小公倍数。

迭代法更主要的应用是进行数值的近似求解，它既可以用来求解代数方程，又可以用来求解微分方程。在科学计算领域，人们常会遇到求微分方程的数值解或解方程f(x)=0等计算问题。这些问题无法用类似求和或求均值那样的精确求解方法进行求解。例如，一般的一元五次或更高阶方程、几乎所有的超越方程以及描述电磁波运动规律的麦克斯韦方程等，它们的解都无法用解析方法求解，为此，人们只能用数值计算的方法求出问题的近似解，而解的误差是人们可以估计和控制的。

例11-2用迭代法求方程x3 - 4x - 6 = 0在x = 2附近的一个根。

重复以上步骤，可以逐次求得更精确的值。显然，迭代过程就是通过重复执行一系列计算来获得问题近似答案，且每一次重复计算将产生一个更精确的解。

用计算机算法实现这一计算过程，不可能让迭代无限制循环进行，因此只能通过控制迭代次数或精度使解无限接近精确解。

下面介绍计算机算法的设计。

设方程为f(x)=0，用某种数学方法导出等价的形式x=g(x)，然后按以下步骤执行。

(1)选一个方程的近似根，赋给变量x0；

(2)将x0的值保存于变量x1，然后计算g(x1)，并将结果存于变量x0；

(3)当x0与x1的差的绝对值还不满足指定的精度要求时，重复步骤(2)的计算。

若方程有根，并且用上述方法计算出来的近似根序列收敛，则按上述方法求得的x0就认为是方程的根。上述算法用C程序的形式表示如下：

例11-3编写求解例11-2问题的C语言程序。

程序运行结果为

由以上介绍可知，近似迭代的基本构建方法是：首先确定一个适当的迭代算式，并选择一个初始近似值以及解的误差，然后通过循环处理来执行迭代过程。终止循环的条件是前后两次得到的近似值之差的绝对值小于或等于预先设定的误差，此时将最后一次迭代得到的近似值视为问题的解。

11.1.2穷举法

穷举法又称为枚举法或者蛮力法，是一种在问题域的解空间中对所有可能的解进行穷举搜索，并根据条件选择最优解的方法。穷举法的基本思想是根据题目的部分条件确定解的大致范围，并在此范围内对所有可能的情况逐一验证，直到全部情况验证完毕。若某个情况验证符合题目的全部条件，则为题目的一个解；若全部情况验证后都不符合题目的全部条件，则题目无解。

穷举法由于会进行大量的重复计算，自然会用到程序的循环结构，因此灵活运用循环结构进行程序设计是穷举法程序设计的关键。

例11-4100块砖由100个人来搬，成年男人一人搬4块，成年女人一人搬3块，小孩(不限男女)3人抬一块，问成年男人、成年女人、小孩各几人？请列出所有可能的取值结果。

解题思路这是一个典型的穷举问题。如果用x、y、z分别代表成年男人、成年女人、小孩的人数，根据题意可列出方程：4x + 3y + z/3 = 100。先确定每种类型人员的数量的取值范围，由题意可知，成年男人x的取值范围是0～100/4 = 25，成年女人y的取值范围是0～100/3 = 33，小孩的取值范围是0～99(必须不大于100且为3的倍数)。使用穷举法遍历所有可能的取值结果，逐一判断筛选出正确的结果。

例11-5抓贼问题。警察审问四名窃贼嫌疑犯。已知，这四人当中仅有一名是窃贼，还知道这四人中每人要么是诚实的，要么总是说谎。他们给警察的回答是：

甲说：“乙没有偷，是丁偷的。”

乙说：“我没有偷，是丙偷的。”

丙说：“甲没有偷，是乙偷的。”

丁说：“我没有偷。”

请根据这四人的回答判断谁是窃贼。

解题思路本题用穷举法求解。假设甲乙丙丁四人是否为窃贼用数组a表示，第i个元素的值等于“1”表示第i个人是窃贼；等于“0”表示该人不是。根据题意可列出求解的条件。

①甲说：“乙没有偷，是丁偷的。”对应于(a[1]+a[3]==1)窃贼要么是乙，要么是丁。

②乙说：“我没有偷，是丙偷的。”对应于(a[1]+a[2]==1)窃贼要么是乙，要么是丙。

③丙说：“甲没有偷，是乙偷的。”对应于(a[0]+a[1]==1)窃贼要么是甲，要么是乙。

④丁说：“我没有偷。”对应于(a[0]+a[1]+a[2]==1||a[3]==1)窃贼只有一个。

上述4个条件之间是“与”的关系。整理表达式后，就可以得到完整的问题求解条件：

(a[3]+a[1]==1&&a[1]+a[2]==1&&a[0]+a[1]==1)

穷举法的特点是算法简单，容易理解，但运算量较大。通常适用于可确定取值范围，但没有更好的算法可用的情况。穷举法常用于解决“有几种组合”“是否存在”“求解不定方程”等问题类型。这种算法的设计通常依赖于循环控制结构来实现。

11.1.3递推法

递推是一种数学方法和算法技术，主要用于解决问题和计算数值。它基于初始信息(如数列的初始项)和递推关系(如数列的规则)来逐步推导问题的答案或计算未知项的值。递推法通常以循环的形式进行，每一步都依赖于前一步的结果，从而避免求通项公式的复杂过程。

递推法适用于具有明显规律和线性关系的问题，具有高效和简洁的优势。例如，斐波那契数列的计算就是一个典型的递推法的应用，通过递推公式F(n)=F(n-1)+F(n-2)(其中F(0)=0，F(1)=1)来计算数列的每一项。

例11-6采用递推法求4的阶乘值。

例11-7斐波那契数列为：1，1，2，3，5，8，13，21，34，55…即满足

请编写求斐波那契(Fibonacci)数列的第n项的函数。

用递推法编写的fib(n)函数如下：

11.1.4递归法

递归法是设计和描述算法的一种有力的工具，它通过将一个大问题拆分成一个或多个相似的子问题，并逐步解决这些子问题来解决整个问题。递归法的两个关键组成部分是基本情况和递归调用。基本情况是指可以直接求解或返回结果的简单情况，而递归调用是指函数在执行过程中调用自身来解决更小规模的子问题。

递归法常常应用于解决具有自相似性的问题，如树和图的遍历、分治算法等。尽管递归法能提供简洁、直观的解决方案，但也可能带来额外的开销和运行效率低的问题，特别是在处理大规模数据时需要注意堆栈溢出等情况。

例11-8用递归法编写例11-7所需的函数fib(n)。

递归法的执行过程分递推和回归两个阶段。在递推阶段，复杂问题的求解被推导为规模较小的子问题的求解，例如，对于fib(n)，它被推导为求解fib(n-1)和fib(n-2)。换言之，计算fib(n)需要先计算fib(n-1)和fib(n-2)，而这两者又依赖于更小规模的问题，如fib(n-3)和fib(n-4)，以此类推，直至得到fib(2)和fib(1)的结果为1。在递推阶段，必须定义终止递推的情况，如在fib()函数中，当n为2或1时终止递推。

在回归阶段，当获得最简单情况的解后，逐级返回，逐步获得较为复杂问题的解。例如，得到fib(2)和fib(1)的解后，返回得到fib(3)的结果，直至得到fib(n-1)和fib(n-2)的结果后，返回得到fib(n)的结果。

在编写递归函数时要注意，函数中的局部变量和参数只是局限于当前调用层，当递推进入“简单问题”层时，原来层次上的参数和局部变量便被隐蔽起来。在一系列“简单问题”层，它们各自有自己的参数和局部变量。

递归法必须确保在每次递归调用时问题规模都能够缩小，否则可能导致无限递归和堆栈溢出等问题。此外，递归法的运行效率可能较低，因为它涉及多次函数调用和重复计算。当某个递归法能较方便地转换为递推法时，通常按递推法编写程序。例如上例计算斐波那契数列的第n项的函数fib(n)应采用例11-7所示的递推法，即从斐波那契数列的前两项出发，逐次由前两项计算出下一项，直至计算出第n项。

11.1.5回溯法

回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解；若当前候选解除了不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。在回溯法中，扩大当前候选解的规模，并继续试探的过程称为向前试探(前探)。放弃当前候选解，寻找下一个候选解的过程称为回溯。

回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术称为回溯，而满足回溯条件的某个状态的点称为“回溯点”。例11-9就是一个典型的利用回溯法求解的例子。

例11-9迷宫问题。在指定的迷宫中找一条从入口到出口的可通路径。

解题思路图11-1所示的方块图表示迷宫，其中空白方块表示通道，灰色方块表示墙，在迷宫数组中分别用0和1表示。现要在迷宫中找一条从入口到出口的可通路径，基本的算法思想是：从入口处开始向前探路(探的方向有右、下、左和上)，当沿着某个方向往前探一步时，若可通则继续往前探，若不通则换个方向后再探，若4个方向上均不通(四个方向上的相邻方块要么是墙块，要么是已探过的通道块)，则按原路回退一步后换个方向再探。在探路的过程中，用一个二维数组记录迷宫的可通路径。

图11-1迷宫问题示意图

下面对程序进行一些说明。

(1)程序中使用的函数如下：

①输出迷宫数组的函数printMaze()。

②在迷宫中探寻可通路径的函数findOnePath()。

(2)函数findOnePath()中使用的数组如下：

①迷宫数组maze[N1][N2]。数组元素值为0代表通(通道)，为1代表不通(墙)。

②可通路径数组stack[N1*N2][2]。

程序中，所设置的条件编译语句可以将每一步前探或回退后的可通路径显示出来，用以对回溯过程进行跟踪。整个过程可以通过图11-2形象地描绘出来。图11-2(a)演示从入口连续向前探寻12步后到达b位置。图11-2(b)演示从b位置开始，连续回退8步后到达a位置。图11-2(c)演示从a位置开始，连续前探14步后到达迷宫出口。最终，根据本程序探寻到的从入口到出口的一条迷宫可通路径如图11-2(c)中的实线箭头所示。

图11-2例11-9程序实现的前探与回退过程

11.1.6贪婪法

贪婪法又称为贪心法，是一种不追求最优解，只希望得到较为满意解的方法。贪婪法一般可以快速得到满意的解，因为它省去了为找最优解要穷举所有可能而必须耗费的大量时间。贪婪法常以当前情况为基础进行最优选择，而不考虑各种可能的整体情况，所以贪婪法不需要回溯。因为不进行回溯处理，贪婪法只在很少的情况下可以得到真正的最优解，比如最短路径、图的最小生成树等。

例11-10找零钱问题。当前使用的货币面额分别是100、50、20、10、5、2、1元。在购物找钱时，怎样找钱才能使找零的张数最少?请根据找零的金额输出找零的方案。

解题思路用贪婪法解决这个问题，在找钱时，为使找回的零钱的张数最少，不考虑找零钱的所有可能方案，而是从最大面值的币种开始，按递减的顺序考虑各币种，先尽量用大面值的币种，当不足大面值币种的金额时才去考虑下一种较小面值的币种。

11.2查找算法

11.2.1顺序查找顺序查找又称线性查找，适用于顺序存储结构和链式存储结构的线性表的查找。要查找的数一般称为关键字，顺序查找就是将给定的关键字与数组元素(或链表结点)逐个进行比较，一旦查找到与关键字相等的数组元素(或链表结点)，则表示查找成功并输出有关信息，否则查找失败并提示没有匹配值。例11-11是一个简单的顺序查找算法示例。

11.2.2二分查找

二分查找要求数组是有序数组，如果不是有序数组，必须先排序，然后才能使用二分查找。二分查找的算法思想如下：

(1)把查找范围平分为两部分，首先判断中点元素是否为要查找的关键字。

(2)如果要查找的关键字不位于中点，则将该关键字与中点元素比较大小，判断它位于中点左边还是右边，缩小查找范围。

(3)锁定查找范围后，在该部分排除上一步中比较的中点，并在此范围内重复步骤(1)(2)。

(4)逐步缩小查找范围，如果查找到要找的关键字，则输出相关信息，否则输出查找失败信息。

例11-12在一个有序的数列中查找指定的数。

解题思路数列有序则可以使用二分查找：假设有序数列递增且存放在一个数组中。查找时，先查找中点值，若待查找的数等于中点值，则查找成功；若待查找的数小于中点值，则到数组的前半部分查找；若待查找的数大于中点值，则到数组的后半部分查找。这样一直查找下去，如果找到了要查找的数，则查找成功，否则查找失败，表明有序数列中不存在要查找的数。

此例要用到3变量：low、high和mid，分别指示被查找的那一部分有序数列的低下标值、高下标值和中间位置。如在有序数列(13,25,34,48,57,62,71,88,96)中查找88，则二分查找过程如图11-3所示。

二分查找的算法流程如图11-4所示。图11-3二分查找88的过程图11-4二分查找的算法流程

11.3排序算法

排序算法有直接插入排序、折半插入排序、简单选择排序、希尔排序、冒泡排序、快速排序、堆排序、归并排序等，这些排序算法在数据结构课程中将会详细阐述。本节主要介绍最简单的两种排序算法：冒泡排序和快速排序。

11.3.1冒泡排序

若对N个数进行升序排列，则冒泡排序的算法思想如下：

(1)从第1个数开始，将第1个数与第2个数进行比较，若为逆序，则交换。然后比较第2个数与第3个数，若为逆序，则交换。依次类推，直至第N - 1个数与第N个数比较并处理完为止。此时完成第一趟冒泡排序，最大的数已经排在第N个位置上。

(2)对前N - 1个数按上述同样的方法进行第二趟冒泡排序。这样，次大的数将排在第N - 1个位置上，以此类推，再对前N - 2个数进行第三趟冒泡排序。

(3)重复上述过程，总共进行N - 1趟排序。

例11-13输入5个数，用冒泡排序将5个数按升序排列