算法合集之“数学思想助你1臂之力”.ppt

数学思想助你一臂之力; 数学和计算机原本就是密不可分的学科。有许多计算机编程问题如果不利用数学思想则很难甚至无法达到预期的效果。; 也就是说，有些问题利用数学思想可以走捷径（例如NOI2002的“荒岛野人”），而还有一些问题，如果不利用数学思想，就根本无法解决（例如NOI2002的“机器人M号”）。今天，我们将从四个方面探讨利用数学思想提高算法效率，简化问题的例子：;一．利用数学思想直接找出解的一般规律;例题一 最优分解方案;算法分析; 对于一些较小的数，我们发觉这个猜想是完全正确的。这促使我们跃跃欲试：证明这个猜想的正确性。 我们先来明确一下拆分方案的几种情况： N=2＋3＋…＋s＋（s＋2）＋…＋k（如N=55) N=3＋4＋…＋k（如12＝2＋3＋4＋3＝3＋4＋5） N=3＋4＋…＋k＋（k＋2）（如13＝2＋3＋4＋4＝3＋4＋6） 由此，我们可以把证明过程分为四步：; 实际上，对每一步的证明过程并不难。总的来说，是利用反证法和调整的思想——先假设命题不正确，然后构造出另一列和为N的自然数，但乘积更大，从而导出矛盾。下面简单说一下每一步的证明：;; 至此，我们的问题应该已经得到了圆满的解答。 让我们再回顾一下解题过程，对于较原始的动态规划算法，我们觉得里面显然有许多不必要的计算，从而提出：能否直接导出一般规律？通过大胆的猜想和严密的证明，这一点得到了肯定，而算法的时间复杂度也从动态规划的O(N2），下降到了现在的O(N)。而这一切都应该归功于数学思想的大胆和合理的应用。;二．利用数学模型化繁为简。;例题二 三角形灯塔 ;[输入] 第一行行首为三角形灯塔的行数N，从第2行开始每行为一个已知状态的编号为（I，j）的灯的信息（1=I=N，1=j=I），即三个由空格隔开的整数：I，j，k，其中k为该灯的状态，由0，1表示（0表示暗，1表示亮）。输入数据以满足I=j=k=0的一行结束。 [输出] 若问题无解，则输出“NO ANSWER！”；否则输出可能的状态总数。 ;算法分析; 运用无进位的二进制加法，简单地说就是：1＋1＝0，1＋0＝1，0＋1＝1，0＋0＝0，其结果与“xor”运算是等价的，但由于其本质是加法运算，因此在本题中容易处理。 这样，我们便可利用最底部的灯的状态用加法表达出所有灯的状态（当然，这里的加法指的都是无进位的二进制加法），于是，根据已知的一些灯的状态，可以列出若干方程，组成方程组。这个方程组有n个未知数，即light[n，I]（I＝1，2，…，n），于是问题的解就转化为求方程组的解数。而这是不难求得的： 步骤一：用高斯消元法把方程个数减为一个，若在此过程中出现了矛盾，则输出“0”； 步骤二：若最后剩下的那个方程为恒等式，则输出2n；否则，若含有p（p0）个未知数，则由于随意确定其中的p-1个未知数的值，都将唯一确定另一个的值，故解数为2p-1。; 这样，我们就找到了一个较为高效的算法。 在本题中，我们先是由灯的亮暗所遵循的规律发觉了一个较为一般的递推关系，而下面一步才是非常关键的——把递推关系中的逻辑运算转换成数学运算，这一步，为我们构造方程组这一数学模型提供了极大的方便，使问题迎刃而解。 数学思想在本题的应用，使我们方便地构造出了数论模型，使问题圆满地解决。;三. 通过数学分析化未知为已知。;例题三 配锁问题;算法分析; 让我们先利用这个条件进行一番分析： 由于“至少要有N个人同时使用各自磁卡才能将锁打开”，意即任意N-1个人在一起，都无法将锁打开，从而必然缺少一种开锁的密码特征A；并且在其余的M-（N-1）个人中，任意一人加入到N-1个人中，他们就能将锁打开，故这其余的M-（N-1）个人必同时拥有密码特征A。而容易证明：每N-1个人在一起，他们缺少的一种密码特征A不能和其他一组N-1个人一起缺少的密码特征相同（否则，由于这两组至少有N个不同的人，且他们都缺少密码特征A，故这些至少N个人在一起无法将锁打开，矛盾）。从而电子锁上特征数tot应满足 ; 另外，对于每一个工作人员T来说，在其余M-1个人中，任选N-1个人在一起，都会因为缺少某种特征而无法开锁，而这缺少的特征必须是T所具备的。故每个工作人员的磁卡上的特征数per应满足; 初始时，特征数置为1，在M个人中每选取M-N+1个人的组合，就为组合中每个工作人员配备当前特征，并将特征数+1。这样，枚举出了所有的组合后，便得出了所有工作人员磁卡上特征的方案了。 ;四．利用数学结论优化算法。;例题四 骨牌覆盖问题;[输出