(程序设计竞赛辅导.docVIP

程序设计竞赛辅导 一、算法设计方法 （一）枚举法（Enumeration） 枚举法亦称穷举法，它的基本思想是：首先依据题目的部分条件确定答案的大致范围，然后在此范围内对所有可能的情况逐一验证，直到全部情况验证完为止。若某个情况使验证符合题目的条件，则为本题的一个答案；若全部情况验证完后均不符合题目的条件，则问题无解。枚举的思想作为一种算法能解决许多问题。 【例1】“百鸡问题”：公鸡每只 5元，母鸡每只 3元，小鸡 3只 1元。花 100元钱买100只鸡，若每种鸡至少买一只，试问有多少种买法？ 【解】“百鸡问题”是求解不定方程的问题：设x，y，z分别为公鸡、母鸡和小鸡的只数，公鸡每只五元、母鸡每只三元、小鸡三只一元。对于百元买百鸡问题，可写出下面的代数方程： x + y + z = 100 5x + 3y + z/3 = 100 除此之外，再也找不出方程了，那么两方程怎么解三个未知数？这是典型的不定方程（组），这类问题用枚举法写算法就十分方便： void BuyChicks() { for (x=1； xx++) /* 最多可以买20只公鸡、33只母鸡 */ for (y =1； y； y++) { z ? 100 - x - y； if (5x + 3y + x／3 = 100) printf(%d, %d, %d\n, x，y, z)； } 其基本思想是把z、y、z可能的取值只数—一列举，解必在其中，而且不止一个。枚举法的实质是枚举所有可能的解，用检验条件判定哪些是有用的，哪些是无用的，而题目往往就是检验条件。枚举法的特点是算法简单，对于可确定解的取值范围且一时又找不到其他更好的算法时，就可以用它。 【例2】求自然数M，N的最大公约数。 【解】类似这样的题用枚举法来求解也是很简单的，我们可以先找出M与N之中的较小者，设为T，则M，N的公约数的取值范围即可确定为：［1，T］，最大公约数自然也在此区间中，接下来在此区间里枚举即可找到解。从大（即T）往小（即1）枚举，找到的第一个公约数即为解。算法如下： int Max(int M, int N) { if ( M ≥ N ) t ? N； else t ? M； while ( M mod t ≠ 0 or N mod t ≠ 0) t ? t – 1; return ( t ); } 枚举是一种经常采用的方法。采用这种方法时，应注意避免不必要的枚举，以减少操作次数。 （二）递推法（Recurrence） 如果对求解的问题能够找出某种规律，采用归纳法可以提高算法的效率。著名数学家Guass在幼年时，有一次老师要全班同学计算自然数1至100之和。Guass迅速算出了答案，令全班吃惊。当时Guass正是应用了归纳法，才得出： 1 + 2 + …… + 99 + 100 = 100 *（100 + 1）／2 = 5050 的结果。归纳法在算法设计中应用很广，最常见的便是递推和递归。 递推是算法设计中最常用的重要方法之一，有时也称迭代。在许多情况下，对求解的问题不能归纳出简单的关系式，但在其前、后项之间却能够找出某种普遍适用的关系。利用这种关系，便可从已知项的值递推出未知项的值来。求多项式值的秦九韶算法，就利用了这种递推关系，其关系式为 Pi ＝ Pi-l * x + ai 只要知道了前项Pi-1，就可以由此计算出后项Pi。 按照问题的具体情况，递推的方向既可以由前向后，也可以由后向前。广义地说，凡在某一算式的基础上从已知的值推出未知的值，都可以视作递推。在这个意义上，用算式s = s + ai求累加和，算式p = p * ai求累乘积，都包含了递推思想的运用。 所谓递推法，它的数学公式也是递归的。只是在实现计算时与递归相反。从给定边界出发，逐步迭代到达指定计算参数。它不需反复调用自己（节省了很多调用时参数匹配开销），效率较高。 【例3】用递推算法计算N的阶乘函