下载此文档

《论文 算法合集之《论数学策略在信息学问题中的应用》(定稿)》.docx


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

《论文 算法合集之《论数学策略在信息学问题中的应用》(定稿)》 来自淘豆网www.taodocs.com转载请标明出处.

相关文档 更多>>
非法内容举报中心
文档信息
  • 页数58
  • 收藏数0 收藏
  • 顶次数0
  • 上传人小博士
  • 文件大小148 KB
  • 时间2020-01-01