国家集训队论文集邵烜程.docVIP

数学思想助你一臂之力 复旦大学附属中学 邵烜程 [关键字] 数学思想、构造算法 [摘要] 数学和计算机原本就是密不可分的学科。有许多计算机编程问题如果不利用数学思想则很难甚至无法达到预期的效果。 如果把问题和编程实现看成是河的两岸，那么数学思想就是连接河两岸的一座桥梁，有了这座桥，从河的一岸到另一岸便不再是件难事了。 有些问题，利用这座桥可以更方便地往返于河两岸，而还有一些问题，如果不利用这座桥，可能根本无法到达河对岸。也就是说，有些问题利用数学思想可以走捷径（例如NOI2002的“荒岛野人”），而还有一些问题，如果不利用数学思想，就根本无法解决（例如NOI2002的“机器人M号”）。我们将从四个方面探讨利用数学思想提高算法效率，简化问题的例子： 一．利用数学思想直接找出解的一般规律。 有些问题，如果直接用动态规划或是图论的方法来解决效率可能会并不理想。这时，我们首先应该想到的是优化，而如果优化无法达到预期的效果，那我们只有重新寻找算法了。于是，我们就试图找出问题的一般规律、或是该问题所用到的一个小问题的一般规律，这样，时间效率将会大大提高。 我们首先来看一个直接找出原问题的一般规律的例子—— 例题一 最优分解方案 把正整数N分解成若干个互不相等的自然数的和，且使这些自然数的乘积最大。 [输入] 只有一行，包括数N（ ）。 [输出] 第一行输出最优分解方案，相邻两数之间用单个空隔隔开；第二行输出最大的乘积。 算法分析 设把N分解成m个互不相等的自然数 ，且满足： 。 直觉告诉我们：要使乘积最大，就要使 尽量接近，并且m尽可能大。不要怀疑自己的感觉，它往往给我们带来了正确的思路，有时甚至是比其它方法简便得多的。而本题正是这样。 让我们先把这个“感觉”表述成数学语言： 先令 ，这里k满足： 设 ，由于restk+2，故若restk+1，则令 通俗一点讲，就是将 首先依次置为2，3，4，等等。当已经确定的数之和要达到N时，将还剩下平均分在前面一些数上。 下面我们来简单证明这个结论：（设 是最优分解方案） 第一步：不存在 ,使得 。 证明：若存在 ，使得 。则令 显然 矛盾。 第三步： 。 证明：假设 。 若不然，则令 显然，有： 矛盾。 因此，有： 而无论哪种情况，都产生矛盾。故原命题得证。 第四步：若 且存在 使得 ，则必有 证明： 由以上几步的证明，我们便可确认：我们的感觉是无误的。这样，这道题似乎变得异常的简单，因为我们接着要做的，就只是计算这个最大的乘积的值了，这里用到了高精度计算。 让我们再回顾一下解题过程，对于较原始的动态规划算法，我们觉得里面显然有许多不必要的计算，从而提出：能否直接导出一般规律？通过大胆的猜想和严密的证明，这一点得到了肯定，而算法的时间复杂度也从动态规划的O(N2），下降到了现在的O(N)。而这一切都应该归功于数学思想的大胆和合理的应用。 二．利用数学模型化繁为简。 能够对原题导出数学结论无疑是最直接地运用了数学思想，而在很多情况下，往往没有那么简单。在有些实际应用中，我们需要将原来的实际问题抽象成数学模型，然后加以解决。而在某些程序设计竞赛的试题中，建立数学模型也需要一定的技巧，需要运用一定的数学思想。 下面，我们来考虑一个利用数学思想“建模”的例子—— 例题二 三角形灯塔 的状态 的状态 的状态 暗 亮 亮 亮 暗 亮 暗 暗 暗 亮 亮 暗 请你编一个程序，从已知的P 个灯的状态出发，推出最底一行N个灯的所有可能的状态总数。 [输入] 第一行行首为三角形灯塔的行数N，从第2行开始每行为一个已知状态的编号为 的灯的信息 ，即三个由空格隔开的整数： ，其中k为该灯的状态，由0，1表示（0表示暗，1表示亮）。输入数据以满足 的一行结束。 [输出] 若问题无解，则输出“NO ANSWER！”；否则输出可能的状态总数。 算法分析 乍一看，似乎只能用有哪些信誉好的足球投注网站来解决，但有哪些信誉好的足球投注网站的时间效率不尽如人