算法合集之《论数学策略在信息学问题中的应用》

IOI’2000集训队论文论数学策略在信息学问题中的应用1/30杨江明论数学策略在信息学问题中的应用(北京十二中,杨江明,100071)【关键字】策略可扩展性效率整数问题【摘要】本文研究的是，在信息学竞赛中十分重要，却常常被忽略的数学策略。本文通过分析数学策略中的方程思想、不等式思想及构造法在具体问题中的应用，比较他们同其他策略的优劣，较为详细地介绍了数学策略的效率、应用范围以及可扩展性。并总结了在信息学问题中引入数学策略的原因。引申出如何在一般解题过程中应用数学策略。展望了数学策略在今后信息学竞赛中应用的前景。本文所选的例题都是近年来各级信息学竞赛的试题，针对某些题目提出了区别于标准算法的更高效的数学策略解法，具有很强的现实意义【目录】【关键字】【摘要】【目录】【正文】§1.数学与策略§2.数学策略在信息学题目中的应用§2.1数学策略之方程思想——化简、解决题目的途径§2.1.1方程思想的运用§2.1.2运用方程思想同一般策略的比较§2.2数学策略之不等式——抽象与具体的桥梁§2.2.1不等式的应用§2.2.2应用不等式同一般策略的比较§2.3特殊的问题——构造法——到达想象力的尽头§2.3.1构造法的应用§2.3.2构造法同其它策略的比较§3.为什么应用数学策略——小结数学策略的应用【附录】【参考书目】【源程序】IOI’2000集训队论文论数学策略在信息学问题中的应用2/30杨江明【正文】§1.数学与策略数学,是研究现实世界的空间形式和数量关系的科学,是处理客观问题的强有力的工具,几乎在一切自然科学领域中都起着基础性的作用。策略，是指解决问题所采取的方法。它包括解决各种问题及问题的方方面面的方法。本文讨论的策略，是指利用计算机编程解题时所采取的行之有效的方法，即编程策略。编写程序解决问题常见的策略有:数学(规律)策略,分治策略,贪心策略,穷举(含搜索)策略等等。判断某种策略的优劣，通常都从三方面进行考察：效率：也就是我们所说的算法复杂度。在竞赛中考察程序的复杂度，一般都是考察程序的时间复杂度。当然，时间复杂度同空间复杂度是相互制约的。应用范围：就是说该策略可以解决哪些类型的题目，是对该策略中“所有”算法所能解决题目总的概括。可扩展性：针对一个题目所构造的算法，是否可以沿用在其它题目上，如果一个算法可以用在多个题目上，我们就说这种算法的可扩展性大。我们对下面要研究的数学策略，都从这三方面同其他策略进行比较。从广义上讲，数学策略包括应用图论的策略，动态规划策略以及应用初等数学手段的策略。图论及动态规划的策略在近年来的比赛中被频频涉及，而初等数学中的方程思想、不等式思想等化简题目、解决问题的手段却没有受到应有的重视。事实上，利用这些基本手段是化简题目的已知条件和建立一个优秀的数学模型必不可少的前提条件。有时能取得意想不到的收获。本文所讨论的数学策略，是从狭义上，指应用初等数学手段的策略。文章通过分析几道近年来信息学竞赛的题目，比较应用数学策略解决、化简题目与直接运用一般策略在效率上的巨大差异，从而说明数学策略在信息学竞赛中的巨大潜力及在解题上的优势，并尝试总结解决一般问题的应有步骤。§2.数学策略在信息学题目中的应用我们看看我们人类是如何解决具体问题的：人类自身既没有快速的运算系统，也没有大容量的存储系统，我们解题运用的就是我们所擅长的逻辑推理和强大的数学工具，我们有完善的方程理论和不等式思想等等，而这正是计算机所欠缺的。于是，我们尝试让计算机也具有这些优点，贪心策略，A*算法等实际上都是这种有益的尝试。利用人类思考的方式做一些选择，而我们现在所讨论的数学策略，实际上就是这些数学手段的直接运用。【附录1】数学策略在信息学中的运用包括两个方面：化简题目和直接解决问题。应用数学策略化简题目是解决问题必不可少的重要步骤，也是分析题目的基本方法。通过应用数学策略化简题目，发掘题目中的隐含条件，寻求更多的“已知”条件，从而为建立数学模型打下良好的基础。而用数学策略直接解题，其效率更是一般算法所不可企及的。下面我们分别从方程、不等式及构造法三个方面，对数学策略的应用加以分析。IOI’2000集训队论文论数学策略在信息学问题中的应用3/30杨江明§2.1数学策略之方程思想——化简、解决题目的途径方程是建立在题目的基础上，对条件的抽象和总结。对于同一题目的不同条件，具有普遍适用性。因此，方程弥补了枚举（包括搜索）策略需要尝试所有情况才能得出结论的缺点。方程是数学策略中较为重要的一种手段。一般来说，运用方程解决问题，都是运用我们程序较擅长的n元一次代数方程组求解，这就涉及到解此类方程组的高斯消元法。下面讲讲用高斯消元法解一元联立方程组。一元n阶线性联立方程组的一般形式为：a1x1+a12x2+…+a1nxn=b1(1)a21x1+a22x2+…+a2nxn=b2(2)……an1x1+an2x2+…+annxn=bn(n)在代数中一般用消元法来解方程组。即：先将第一行乘以一个常数再与其它行相加，以消去其它各行的x1那一项（使a21，a31，…an1为0）。然后再以新的第二行乘以一个常数并与第3行到第n行相加，以消去第3行到第n行上x2的那一项（使x2的系数为0）。…最后再以新的第（n-1）行乘一个常数并与第n行相加，以消去第n行上的xn-1项。最后得到一个如下形式的三角方程组：a11x1+a12x2+a13x3+…+a1nxn=b1a22`x2+a23x3+…+a2n`xn=b2`a33`x3+…+a3n`xn`=b3`…ann`xn=bn`此过程可用图1表示。图1IOI’2000集训队论文论数学策略在信息学问题中的应用4/30杨江明从此方程组最后一个方程式可以直接求出xn=bn`/ann`，然后逐步“回代”，求出xn-1,xn-2…，x1。还要考虑一个问题：如果在上面过程中，aｉｉ为零，则在消元过程中会出现使第i行乘以常数aki/aii而出现无穷大，溢出。例如，本来为了消去第2行的x1项，要进行的是：（1）式×a21/a11-（2）式，若aii=0，则发生溢出错误。必须保证aii≠0。若发生aii为零，可从第i+1行到n行中找到一个第m行，其ami≠0，将此第m行与第i行对调。如果找不到，则方程无解或无定解。可用图2表示。图2根据上面介绍的方法，利用图2所示的N—S图，得到上面列出三角方程组。再使该三角方程组中各Aii的值为1，以得到以下三角方程组：x1+a12``x2+a13``x3+…+a1n``xn=b1x2+a23``x3+…+a2n``xn=b2…xn-1+a(n-1)n``xn=bn-1xn=bn``这样就得到xn=bn``，然后回代，求出xn-1，…x1值。画出这部分流程图（图3）。上述过程表示为图2和图3。为清晰起见，最好用子程序，一个子程序完成一个功能。IOI’2000集训队论文论数学策略在信息学问题中的应用5/30杨江明刚刚过去的IOI’99为我们留下了许多思考，那我们就由IOI’99中的纸牌问题引入吧。图3§2.1.1方程思想的运用我们把均分纸牌问题简要描述一下：【例1】这是一个均分纸牌的游戏，有N列纸牌，每列有纸牌若干张（可能是零张）。纸牌列用从1到N的整数标号。在移动纸牌时你需要指定一个确定的列p，和一个确定的数字m。而后从p列上移动m张纸牌到每一个相邻的列上。如果1＜p＜N的话，则p列有两个相邻的列，分别是p-1和p+1；如果p=1的话，则只有一个相邻列，其列号为2；如果p=N的话，则只有一个相邻列，其列号为N-1。注意，如果p列有两个相邻的列，则进行上述移动时，p列至少要有2m张纸牌；如果p列只有一个相邻的列，则进行这样的移动时，p列就需要至少m张纸牌。这个游戏的目的是“均分”所有的纸牌列，使每列都有相同的纸牌数，且用最少的移动达到这一目的。假定有超过一种符合上述要求的移动方法，你只需给出其中一种。[附录中2]我们运用数学策略化简题目是为了寻求更好的思路，只有化简题目才能更好地解决题目。但实际上，许多人拿到这道题目时都发懵了，怎样才能“均分”呢？于是，各种学过的算法在头脑中打架：选手：搜索，你行吗？搜索：嗯，10000步呢，要我嘛，恐怕得等等了。选手：动态规划，你呢？动态规划：我？这道题我也没辙。怎么办？首先，我们对题目进行分析，必须先认识到这样一重关系，第ｉ列的纸牌只能向两侧的ｉ+1列、ｉ-1列移动，而且移动的总牌数是相等的（第1列和第n列例外）。其次，只有ｉ+1列、ｉ-1列可以向第ｉ列移动纸牌，而且移到第ｉ列的牌数必然等于第ｉ+1列、ｉ-1列移动总牌数的一半。要保证均分，于是对于第ｉIOI’2000集训队论文论数学策略在信息学问题中的应用6/30杨江明列牌移走的总牌数与移来的总牌数的差值，必然等于首末状态纸牌数的差值。首状态即初始状态，而末状态即均匀状态。于是，对于N列纸牌，则共有N个未知数，即为每列须移走的纸牌数。第ｉ列须移走的纸牌数记为Mi，第i列首末状态的差值记为Δi，于是有方程组：M2–M1=A-C1=△1M2-M1=△1M1–2M2+M3=A-C2=△2利用高斯消元法M3–M2=△1+△2M2–2M3+M4=A–C3=△3M4–M3=△1+△2+△3M3–2M4+M5=A–C4=△4化简得………………………………………………Mn-2–2Mn-1+Mn=A–Cn-1=△n-1Mn–Mn-1=△1+△2+…△nMn–Mn-1=A-Cn=△n共有n个未知数，n-1个方程，为一不定方程组。假设M1=0代入可求出对应的一组解{x1,x2,x3……xn}，其中x1=0，根据n元一次方程组的性质{x1+t,x2+t,x3+t……xn+t},t为整数，也一定为方程组的一组解，代入化简即可证明。题目要求最小的移动次数，当然移动的纸牌总数也要尽量小。因为xi≥0,所以若得到最小解为零的一组解，则该解对应移动纸牌总数一定最小。得出结论：对应每列移动的纸牌数是确定的，且是可求的，而且能够保证均分。有了均分的保证，剩下的问题就好说了，无论是贪心策略，随机化算法，还是一些算法的综合运用都不成问题。即便用最基本的贪心算法，对于IOI’99的测试数据也都能应付自如。实际上IOI’99的这道题目提示我们，数学毕竟是基础，完全脱离数学的算法是没有的，脱离对题目本身的分析，单纯地套用算法是不现实的，而这正是许多选手常犯的毛病。我们再看一道相关的题目。【例2】在物理学中，我们常常对一些复杂的电路问题十分头疼，为了便于分析，我们需要把一些电阻的混连电路，用一个等效电阻来取代。而等效电阻的计算往往是十分繁琐的。于是，我们尝试用程序代替我们完成这项任务。程序需要计算的，是一个纯电阻的混连电路中两点间的总电阻。【附录3】【说明】为了阐述方便，我们建立这样一个模型来描述电路：电路由一个一个结点连接构成，结点就是导线的交点，若两结点间的电路上不存在其它结点，则称这两个结点是两相邻结点。两相邻结点之间只允许有两种情况：（1）它们之间是一个已知电阻（如图4）；图4（2）它们之间是x个已知电阻的纯并联电路（如图5）；IOI’2000集训队论文论数学策略在信息学问题中的应用7/30杨江明图5两相邻结点间总电阻不为零（若为零，则两结点必可以合并成一个结点）。没有孤立的结点。此模型必然可以描述所有的纯电阻电路。在此基础上我们对此题进行分析。【输入】第一行是一个整数N，表示结点数；第二行是一个整数M，表示相邻结点的对数；第三行有两个数，a和b，程序就是要求结点a和结点b间的总电阻。以下M行每行有三个整数，i,j和k（1≤i＜j≤N），表示结点i和结点j之间连结着大小为k的电阻。【输出】仅需输出一个数，就是结点a和结点b间的总电阻。我们手算解决此类题目，通常都是在结点a、b两端接一个外接电源，根据局部电路欧姆定律，测量a、b间的电压值和流入的总电流值，从而计算出总电阻。我们用程序解决这道题也可以利用这种手段：加一理想外接电源，给定电压值，解出总电流值，从而求出等价电阻值（如图6）。对于两相邻结点间存在x个电阻的纯并联电路，我们可以在输入的时候将其直接化