《算法合集之《论数学策略在信息学问题中的应用》》由会员分享，可在线阅读，更多相关《算法合集之《论数学策略在信息学问题中的应用》（30页珍藏版）》请在金锄头文库上搜索。
1、IOI2000 集训队论文 论数学策略在信息学问题中的应用1/31 杨江明论数学策略在信息学问题中的应用(北京十二中 , 杨江明 , 100071)【关键字】策略 可扩展性 效率 整数问题【摘 要】本文研究的是，在信息学竞赛中十分重要，却常常被忽略的数学策略。本文通过分析数学策略中的方程思想、不等式思想及构造法在具体问题中的应用，比较他们同其他策略的优劣，较为详细地介绍了数学策略的效率、应用范围以及可扩展性。并总结了在信息学问题中引入数学策略的原因。引申出如何在一般解题过程中应用数学策略。展望了数学策略在今后信息学竞赛中应用的前景。本文所选的例题都是近年来各级信息学竞赛的试题，针对某些题目提出
2、了区别于标准算法的更高效的数学策略解法，具有很强的现实意义【目 录】【关 键字】【摘 要】【目 录】【 正 文】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. 为什么应用数学策略小结数学策略的应用【附 录】【参考 书目】【源 程序】IOI2000 集训队论文 论数学策略在
3、信息学问题中的应用2/31 杨江明【正 文】1. 数学与策略数学,是研究现实世界的空间形式和数量关系的科学,是处理客观问题的强有力的工具,几乎在一切自然科学领域中都起着基础性的作用。策略，是指解决问题所采取的方法。它包括解决各种问题及问题的方方面面的方法。本文讨论的策略，是指利用计算机编程解题时所采取的行之有效的方法，即编程策略。编写程序解决问题常见的策略有:数学(规律)策略,分治策略,贪心策略,穷举(含搜索)策略等等。判断某种策略的优劣，通常都从三方面进行考察：效率 ：也就是我们所说的算法复杂度。在竞赛中考察程序的复杂度，一般都是考察程序的时间复杂度。当然，时间复杂度同空间复杂度是相互制约的
4、。应用范围 ：就是说该策略可以解决哪些类型的题目，是对该策略中“所有”算法所能解决题目总的概括。可扩展性 ：针对一个题目所构造的算法，是否可以沿用在其它题目上，如果一个算法可以用在多个题目上，我们就说这种算法的可扩展性大。我们对下面要研究的数学策略，都从这三方面同其他策略进行比较。从广义上讲，数学策略包括应用图论的策略，动态规划策略以及应用初等数学手段的策略。图论及动态规划的策略在近年来的比赛中被频频涉及，而初等数学中的方程思想、不等式思想等化简题目、解决问题的手段却没有受到应有的重视。事实上，利用这些基本手段是化简题目的已知条件和建立一个优秀的数学模型必不可少的前提条件。有时能取得意想不到的
5、收获。本文所讨论的数学策略，是从狭义上，指应用初等数学手段的策略。文章通过分析几道近年来信息学竞赛的题目，比较应用数学策略解决、化简题目与直接运用一般策略在效率上的巨大差异，从而说明数学策略在信息学竞赛中的巨大潜力及在解题上的优势，并尝试总结解决一般问题的应有步骤。2. 数学策略在信息学题目中的应用我们看看我们人类是如何解决具体问题的：人类自身既没有快速的运算系统，也没有大容量的存储系统，我们解题运用的就是我们所擅长的逻辑推理和强大的数学工具，我们有完善的方程理论和不等式思想等等，而这正是计算机所欠缺的。于是，我们尝试让计算机也具有这些优点，贪心策略，A*算法等实际上都是这种有益的尝试。利用人
6、类思考的方式做一些选择，而我们现在所讨论的数学策略，实际上就是这些数学手段的直接运用。 【附录 1】数学策略在信息学中的运用包括两个方面：化简题目和直接解决问题。应用数学策略化简题目是解决问题必不可少的重要步骤，也是分析题目的基本方法。通过应用数学策略化简题目，发掘题目中的隐含条件，寻求更多的“已知”条件，从而为建立数学模型打下良好的基础。而用数学策略直接解题，其效率更是一般算法所不可企及的。下面我们分别从方程、不等式及构造法三个方面，对数学策略的应用加以分析。IOI2000 集训队论文 论数学策略在信息学问题中的应用3/31 杨江明2.1 数学策略之方程思想化简、解决题目的途径方程是建立在题
7、目的基础上，对条件的抽象和总结。对于同一题目的不同条件，具有普遍适用性。因此，方程弥补了枚举（包括搜索）策略需要尝试所有情况才能得出结论的缺点。方程是数学策略中较为重要的一种手段。一般来说，运用方程解决问题，都是运用我们程序较擅长的 n 元一次代数方程组求解，这就涉及到解此类方程组的高斯消元法。下面讲讲用高斯消元法解一元联立方程组。一元 n 阶线性联立方程组的一般形式为：a1 x1+a12 x2+a1n xn=b1 (1)a2 1x1+a22 x2+a2n xn=b2 (2) an1 x1+an2 x2+ann xn=bn (n)在代数中一般用消元法来解方程组。即：先将第一行乘以一个常数再与其
8、它行相加，以消去其它各行的 x1那一项（使 a21，a 31，a n1为 0） 。然后再以新的第二行乘以一个常数并与第 3 行到第 n 行相加，以消去第 3 行到第 n 行上x2的那一项（使 x2的系数为 0） 。最后再以新的第（n-1）行乘一个常数并与第 n 行相加，以消去第 n 行上的 xn-1项。最后得到一个如下形式的三角方程组：a11x1+a12x2+a13x3+a1nxn=b1a22x2+a23x3+a2nxn=b2a33x3+a3nxn=b3annxn=bn此过程可用图 1 表示。IOI2000 集训队论文 论数学策略在信息学问题中的应用4/31 杨江明图 1从此方程组最后一个方程
9、式可以直接求出 xn= bn/ann ，然后逐步“回代” ，求出 xn-1,xn-2，x 1。 还要考虑一个问题：如果在上面过程中，a 为零，则在消元过程中会出现使第 i 行乘以常数 aki/aii而出现无穷大，溢出。例如，本来为了消去第 2 行的 x1项，要进行的是：（1）式a 21/a11-（2）式，若 aii=0，则发生溢出错误。必须保证 aii0。若发生 aii为零，可从第 i+1 行到 n 行中找到一个第 m 行，其ami0，将此第 m 行与第 i 行对调。如果找不到，则方程无解或无定解。可用图 2 表示。图 2根据上面介绍的方法，利用图 2 所示的 NS 图，得到上面列出三角方程组
10、。再使该三角方程组中各 Aii的值为 1，以得到以下三角方程组：x1+a12x2+a13x3+a1nxn=b1x2+a23x3+ +a2nxn=b2x n-1+a(n-1) nxn=bn-1xn=bn这样就得到 xn=bn，然后回代，求出 x n-1，x 1值。画出这部分流程图（图 3） 。上述过程表示为图 2 和图 3。为清晰起见，最好用子程序，一个子程序完成一个功能。IOI2000 集训队论文 论数学策略在信息学问题中的应用5/31 杨江明刚刚过去的 IOI99 为我们留下了许多思考，那我们就由 IOI99 中的纸牌问题引入吧。图 32.1.1 方程思想的运用我们把均分纸牌问题简要描述一下
11、：【例 1】这是一个均分纸牌的游戏，有 N 列纸牌，每列有纸牌若干张（可能是零张） 。纸牌列用从 1 到 N 的整数标号。在移动纸牌时你需要指定一个确定的列 p，和一个确定的数字 m。而后从 p 列上移动 m 张纸牌到每一个相邻的列上。如果 1pN 的话，则 p 列有两个相邻的列，分别是 p-1 和 p+1；如果 p=1的话，则只有一个相邻列，其列号为 2；如果 p=N 的话，则只有一个相邻列，其列号为 N-1。注意，如果 p 列有两个相邻的列，则进行上述移动时，p 列至少要有 2m 张纸牌；如果 p 列只有一个相邻的列，则进行这样的移动时，p 列就需要至少 m张纸牌。这个游戏的目的是“均分”
12、所有的纸牌列，使每列都有相同的纸牌数，且用最少的移动达到这一目的。假定有超过一种符合上述要求的移动方法，你只需给出其中一种。 附录中 2我们运用数学策略化简题目是为了寻求更好的思路，只有化简题目才能更好地解决题目。但实际上，许多人拿到这道题目时都发懵了，怎样才能“均分”呢？于是，各种学过的算法在头脑中打架：选手：搜索，你行吗？搜索：嗯， 10000 步呢，要我嘛，恐怕得等等了。选手：动态规划，你呢？动态规划：我？这道题我也没辙。怎么办？首先，我们对题目进行分析，必须先认识到这样一重关系，第列的纸牌只能向两侧的+1 列、-1 列移动，而且移动的总牌数是相等的（第1 列和第 n 列例外） 。其次，
13、只有+1 列、-1 列可以向第列移动纸牌，而且移到第列的牌数必然等于第+1 列、-1 列移动总牌数的一半。要保证均分，于是对于第IOI2000 集训队论文 论数学策略在信息学问题中的应用6/31 杨江明列牌移走的总牌数与移来的总牌数的差值，必然等于首末状态纸牌数的差值。首状态即初始状态，而末状态即均匀状态。于是，对于 N 列纸牌，则共有 N 个未知数，即为每列须移走的纸牌数。第列须移走的纸牌数记为 Mi，第 i 列首末状态的差值记为 i，于是有方程组：M2 M1 = A-C1 = 1 M2-M1= 1M1 2M2 +M 3= A-C2 = 2 利用高斯消元法 M 3 M2 = 1 + 2 M2 2M3+M4 = A C3 = 3 M4 M3 = 1 + 2+ 3M3 2M4 +M5 =A C4 = 4 化简得 Mn-2 2Mn-1 +Mn =A Cn-1 = n-1 Mn Mn-1 = 1 + 2 +nMn Mn-1 =A-Cn =n共有 n 个未知数，n-1 个方程，为一不定方程组。假设 M1 =0 代入可求出对应的一组解 x1,x2,x3xn ，其中 x1 =0，根据 n 元一次方程组的性质x1+t,x2+t,x3+txn+t , t 为整数，也一定为方程组的一组解，代入化简即可证明。题目要求最小的移动次数
