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

算法合集之《论数学策略在信息学问题中的应用》38475论数学策略在信息学问题中的应用(北京十二中,杨江明,100071)【关键字】策略可扩展性效率整数问题【摘要】本文研究的是,在信息学竞赛中十分重要,却常常被忽略的数学策略。本文通过分析数学策略中的方程思想、不等式思想及构造法在具体问题中的应用,比较他们同其他策略的优劣,较为详细地介绍了数学策略的效率、应用范围以及可扩展性。并总结了在信息学问题中引入数学策略的原因。引申出如何在一般解题过程中应用数学策略。展望了数学策略在今后信息学竞赛中应用的前景。本文所选的例题都是近年来各级信息学竞赛的试题,针对某些题目提出了区别于标准算法的更高效的数学策略解法,具有很强的现实意义【目录】【关键字】【摘要】【目录】【正文】§§§——化简、解决题目的途径§§§——抽象与具体的桥梁§§§——构造法——到达想象力的尽头§§§——小结数学策略的应用【附录】【参考书目】【源程序】【正文】§,是研究现实世界的空间形式和数量关系的科学,是处理客观问题的强有力的工具,几乎在一切自然科学领域中都起着基础性的作用。策略,是指解决问题所采取的方法。它包括解决各种问题及问题的方方面面的方法。本文讨论的策略,是指利用计算机编程解题时所采取的行之有效的方法,即编程策略。编写程序解决问题常见的策略有:数学(规律)策略,分治策略,贪心策略,穷举(含搜索)策略等等。判断某种策略的优劣,通常都从三方面进行考察:效率:也就是我们所说的算法复杂度。在竞赛中考察程序的复杂度,一般都是考察程序的时间复杂度。当然,时间复杂度同空间复杂度是相互制约的。应用范围:就是说该策略可以解决哪些类型的题目,是对该策略中“所有”算法所能解决题目总的概括。可扩展性:针对一个题目所构造的算法,是否可以沿用在其它题目上,如果一个算法可以用在多个题目上,我们就说这种算法的可扩展性大。我们对下面要研究的数学策略,都从这三方面同其他策略进行比较。从广义上讲,数学策略包括应用图论的策略,动态规划策略以及应用初等数学手段的策略。图论及动态规划的策略在近年来的比赛中被频频涉及,而初等数学中的方程思想、不等式思想等化简题目、解决问题的手段却没有受到应有的重视。事实上,利用这些基本手段是化简题目的已知条件和建立一个优秀的数学模型必不可少的前提条件。有时能取得意想不到的收获。本文所讨论的数学策略,是从狭义上,指应用初等数学手段的策略。文章通过分析几道近年来信息学竞赛的题目,比较应用数学策略解决、化简题目与直接运用一般策略在效率上的巨大差异,从而说明数学策略在信息学竞赛中的巨大潜力及在解题上的优势,并尝试总结解决一般问题的应有步骤。§:人类自身既没有快速的运算系统,也没有大容量的存储系统,我们解题运用的就是我们所擅长的逻辑推理和强大的数学工具,我们有完善的方程理论和不等式思想等等,而这正是计算机所欠缺的。于是,我们尝试让计算机也具有这些优点,贪心策略,A*算法等实际上都是这种有益的尝试。利用人类思考的方式做一些选择,而我们现在所讨论的数学策略,实际上就是这些数学手段的直接运用。【附录1】数学策略在信息学中的运用包括两个方面:化简题目和直接解决问题。应用数学策略化简题目是解决问题必不可少的重要步骤,也是分析题目的基本方法。通过应用数学策略化简题目,发掘题目中的隐含条件,寻求更多的“已知”条件,从而为建立数学模型打下良好的基础。而用数学策略直接解题,其效率更是一般算法所不可企及的。下面我们分别从方程、不等式及构造法三个方面,对数学策略的应用加以分析。§——化简、解决题目的途径方程是建立在题目的基础上,对条件的抽象和总结。对于同一题目的不同条件,具有普遍适用性。因此,方程弥补了枚举(包括搜索)策略需要尝试所有情况才能得出结论的缺点。方程是数学策略中较为重要的一种手段。一般来说,运用方程解决问题,都是运用我们程序较擅长的n元一次代数方程组求解,这就涉及到解此类方程组的高斯消元法。下面讲讲用高斯消元法解一元联立方程组。一元n阶线性联立方程组的一般形式为:a1x1+a12x2+…+a1nxn=b1(1)a21x1+a22x2+…+a2nxn=b2(2)……an1x1+an2x2+…+annxn=bn(n)在代数中一般用消元法来解方程组。即:先将第一行乘以一个常数再与其它行相加,以消去其它各行的x1那一项(使a21,a31,…an1为0)