算法合集之《数学思想助你一臂之力》

《算法合集之《数学思想助你一臂之力》》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数学思想助你一臂之力复旦大学附属中学邵烜程[关键字]数学思想、构造算法[摘要]数学和计算机原本就是密不可分的学科。有许多计算机编程问题如果不利用数学思想则很难甚至无法达到预期的效果。如果把问题和编程实现看成是河的两岸，那么数学思想就是连接河两岸的一座桥梁，有了这座桥，从河的一岸到另一岸便不再是件难事了。有些问题，利用这座桥可以更方便地往返于河两岸，而还有一些问题，如果不利用这座桥，可能根本无法到达河对岸。也就是说，有些问题利用数学思想可以走捷径（例如NOI2002的“荒岛野人”），而还有一些问题，如果不利用数学思想，就根本无法解决（例如NOI2002的“机器人M号”）。我们将从四个

2、方面探讨利用数学思想提高算法效率，简化问题的例子：一．利用数学思想直接找出解的一般规律。有些问题，如果直接用动态规划或是图论的方法来解决效率可能会并不理想。这时，我们首先应该想到的是优化，而如果优化无法达到预期的效果，那我们只有重新寻找算法了。于是，我们就试图找出问题的一般规律、或是该问题所用到的一个小问题的一般规律，这样，时间效率将会大大提高。我们首先来看一个直接找出原问题的一般规律的例子——例题一最优分解方案把正整数N分解成若干个互不相等的自然数的和，且使这些自然数的乘积最大。[输入]只有一行，包括数N（）。9[输出]第一行输出最优分解方案，相邻两数之间用单个空隔隔开；第二行输

3、出最大的乘积。算法分析设把N分解成m个互不相等的自然数，且满足：。直觉告诉我们：要使乘积最大，就要使尽量接近，并且m尽可能大。不要怀疑自己的感觉，它往往给我们带来了正确的思路，有时甚至是比其它方法简便得多的。而本题正是这样。让我们先把这个“感觉”表述成数学语言：先令，这里k满足：设，由于rest

4、：矛盾。因此，有：而无论哪种情况，都产生矛盾。故原命题得证。第四步：若且存在使得，则必有证明：由以上几步的证明，我们便可确认：我们的感觉是无误的。这样，这道题似乎变得异常的简单，因为我们接着要做的，就只是计算这个最大的乘积的值了，这里用到了高精度计算。让我们再回顾一下解题过程，对于较原始的动态规划算法，我们觉得里面显然有许多不必要的计算，从而提出：能否直接导出一般规律？通过大胆的猜想和严密的证明，这一点得到了肯定，而算法的时间复杂度也从动态规划的O(N2），下降到了现在的O(N)。而这一切都应该归功于数学思想的大胆和合理的应用。二．利用数学模型化繁为简。能够对原题导出数学结论无疑是

5、最直接地运用了数学思想，而在很多情况下，往往没有那么简单。在有些实际应用中，我们需要将原来的实际问题抽象成数学模型，然后加以解决。而在某些程序设计竞赛的试题中，建立数学模型也需要一定的技巧，需要运用一定的数学思想。下面，我们来考虑一个利用数学思想“建模”的例子——9例题二三角形灯塔的状态的状态的状态暗亮亮亮暗亮暗暗暗亮亮暗请你编一个程序，从已知的P个灯的状态出发，推出最底一行N个灯的所有可能的状态总数。[输入]第一行行首为三角形灯塔的行数N，从第2行开始每行为一个已知状态的编号为的灯的信息，即三个由空格隔开的整数：，其中k为该灯的状态，由0，1表示（0表示暗，1表示亮）。输入数据以

6、满足的一行结束。[输出]若问题无解，则输出“NOANSWER！”；否则输出可能的状态总数。算法分析乍一看，似乎只能用搜索来解决，但搜索的时间效率不尽如人意。因此，我们不得不另觅他路。我们把注意力集中在灯的亮暗规则上。我们容易发现，如果令表示灯的亮暗情况（灯亮时为1，灯暗时为0），则我们发觉：我们希望利用上面这个特点，得到一个效率更高的算法。为此，我们不希望使用“xor”运算，如果能用加、减、乘或除号来代替“xor”，那么我们就能够用第N行的灯的状态来用表达式表示出所有灯的状态。这不由使我们想到了“二进制的无进位加法”，即：9为方便起见，这里仅用普通的加号来代表二进制的无进位加法（即

7、0+1=1，1+0=1，0+0=0，1+1=0）。这样，若令我们就可以把每个用表示出来，根据所给的已知条件，就可以得到若干个关于x[1]，x[2]，…，x[n]的方程，构成方程组。我们只需要求出该方程组的解的组数即可。求这个特殊的方程组的解的组数的大致方法是：但在求解过程中必须考虑一些特殊情况。这样，我们就找到了一个较为高效的算法。在本题中，我们先是由灯的亮暗所遵循的规律发觉了一个较为一般的递推关系，而下面一步才是非常关键的——把递推关系中的逻辑运算转换成数学运算，这