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

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

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

2、法解决（例如NOI2002的“机器人M号”）。今天，我们将从四个方面探讨利用数学思想提高算法效率，简化问题的例子：利用数学思想直接找出解的一般规律利用数学模型化繁为简通过数学分析化未知为已知利用数学结论优化算法一．利用数学思想直接找出解的一般规律有些问题，如果直接用动态规划或是图论的方法来解决效率可能会并不理想；这时，我们首先应该想到的是优化，而如果优化无法达到预期的效果，那我们只有重新寻找算法了。于是，我们就试图找出问题的一般规律、或是该问题所用到的一个小问题的一般规律，这样，时间效率将会大大提高。我们首先来看一

3、个直接找出原问题的一般规律的例子——例题一最优分解方案把正整数N分解成若干个互不相等的自然数的和，且使这些自然数的乘积最大。[输入]只有一行，包括数N（3<=N<=1000）。[输出]第一行输出最优分解方案，相邻两数之间用单个空格隔隔开；第二行输出最大的乘积。算法分析初看本题，发觉很显然可以用动态规划解决，但我们并不满足——直觉告诉我们，应该可以找到最优分解方案的一般规律，而一旦找到，时间效率将大大提高。我们的直觉告诉我们，将N分解成的m个数应尽量接近，而且m应该尽量得大。更一般地说，就是把N写成连续自然数2，3，

4、…，k之和（当然，由于自然数1不影响乘积，自然不将其加入），然后，将剩下的数依次平均分配到k，k-1，…，s上，让这些数都加1。例如，当N=55时由于55=2+3+…+10＋1，将多余的1分配到10上，就得到55＝2＋3＋…＋8＋9＋11对于一些较小的数，我们发觉这个猜想是完全正确的。这促使我们跃跃欲试：证明这个猜想的正确性。我们先来明确一下拆分方案的几种情况：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＋

5、4＋4＝3＋4＋6）由此，我们可以把证明过程分为四步：实际上，对每一步的证明过程并不难。总的来说，是利用反证法和调整的思想——先假设命题不正确，然后构造出另一列和为N的自然数，但乘积更大，从而导出矛盾。下面简单说一下每一步的证明：至此，我们的问题应该已经得到了圆满的解答。让我们再回顾一下解题过程，对于较原始的动态规划算法，我们觉得里面显然有许多不必要的计算，从而提出：能否直接导出一般规律？通过大胆的猜想和严密的证明，这一点得到了肯定，而算法的时间复杂度也从动态规划的O(N2），下降到了现在的O(N)。而这一切都应该

6、归功于数学思想的大胆和合理的应用。二．利用数学模型化繁为简。能够对原题导出数学结论无疑是最直接地运用了数学思想，而在很多情况下，往往没有那么简单。在有些实际应用中，我们需要将原来的实际问题抽象成数学模型，然后加以解决。而在某些程序设计竞赛的试题中，建立数学模型也需要一定的技巧，需要运用一定的数学思想。下面，我们来考虑一个利用数学思想“建模”的例子——例题二三角形灯塔有一个N行（0

7、每个灯有明、暗两种状态，第i行（1<=I=0）个灯的状态出发，推出最底一行N个灯的所有可能的状态总数。[输入]第一行行首为三角形灯塔的行数N，从第2行开始每行为一个已知状态的编号为（I，j）的灯的信息（1<=I<=N，1<=j<=I），即三个由空格隔开的整数：I，j，k，其中k为该

8、灯的状态，由0，1表示（0表示暗，1表示亮）。输入数据以满足I=j=k=0的一行结束。[输出]若问题无解，则输出“NOANSWER！”；否则输出可能的状态总数。算法分析乍一看，可能会觉得此题只有用枚举搜索的办法解决，但其效率却并不理想。因此，我们不得不另觅他路。如果我们仔细研究一下灯亮暗所遵循的规律，会发现：如果用light[I，j]表示灯（I，j）的状态（