学位论文 > 优秀研究生学位论文题录展示

PAR方法在解信息学奥林匹克赛题中的应用研究

作　者: 罗晓娟
导　师: 薛锦云
学　校: 江西师范大学
专　业: 现代教育技术
关键词: PAR方法信息学奥林匹克竞赛算法程序
分类号: TP301
类　型: 硕士论文
年　份: 2006年
下　载: 68次
引　用: 0次
阅　读: 论文下载

内容摘要

信息学奥林匹克竞赛的试题出现了越来越难的趋势。要解好这类题目，需要有相当扎实的各科基础知识，并且具备很强的全面素质与综合能力。这些题目要求学生能透过现象看本质，能在纷繁复杂的矛盾中抓住主要矛盾，迅速切入主题，并运用所学知识对问题进行抽象、形式化和模型化，并最终编写出程序将问题加以解决。薛锦云教授在多项国家级课题和省部级项目资助下，提出并开发的PAR(Partition And Recur)方法是一种新的算法程序设计方法。通过对这种新的算法设计方法的学习和掌握，学生可以消除对程序设计的恐惧心理，让程序设计成为_门科学和艺术，成为犹如赋诗或作曲那样的美学实践，成为程序设计者美的享受而不是负担。本论文主要完成了以下几项工作：首先对信息学奥林匹克竞赛中近几年题型的变化做了一定的的研究；对PAR方法做了简单的介绍，进一步研究了它的特点，阐述了PAR方法的开发步骤；选出了信息学奥林匹克竞赛中四道比较典型的试题(GODI的旅游问题；公路规划问题；导弹拦截问题；加分二叉树问题)，并对这四道题进行了详尽的算法分析，分别用常用算法编制了解决问题的程序，最后运用PAR方法开发了这四道题的算法。在本论文研究过程中，分别用PAR方法解决了穷举法、分治法、动态规划法、贪心算法等多种方法能解决的问题，进一步验证了PAR方法在解决复杂算法问题上的可行性，说明很多的奥赛问题其实都可以用PAR方法来解决。

全文目录

摘要  2-3
Abstract  3-6
第一章引言  6-10
  1.1 研究背景  6-7
  1.2 相关研究情况  7-8
  1.3 研究的主要内容  8-10
第二章 PAR方法的关键技术及开发步骤  10-15
  2.1 PAR方法的关键技术  10
  2.2 循环不变式的新定义和开发新策略  10-11
  2.3 Radl语言和Apla语言简介  11-13
    2.3.1 自定义泛型算法设计语言Radl  12
    2.3.2 抽象程序设计语言Apla  12-13
  2.4 PAR方法的开发步骤  13-15
第三章 PAR方法在解信息学奥林匹克竞赛试题中的应用  15-48
  3.1 GDOI的旅游问题  15-26
    3.1.1 GDOI的旅游问题的穷举算法  15-18
    3.1.2 GDOI的旅游问题的分治算法  18-21
    3.1.3 GDOI的旅游问题的动态规划算法  21-23
    3.1.4 GDOI的旅游问题的PAR方法解题步骤  23-26
  3.2 公路规划问题  26-36
    3.2.1 公路规划问题的Dijkstra算法  27-29
    3.2.2 公路规划问题的ford算法  29-31
    3.2.3 公路规划问题的PAR方法解题步骤  31-36
  3.3 导弹拦截问题  36-41
    3.3.1 导弹拦截问题的动态规划算法  37-38
    3.3.2 导弹拦截问题的PAR方法解题步骤  38-41
  3.4 加分二叉树问题  41-48
    3.4.1 加分二叉树问题的递归算法  41-44
    3.4.2 加分二叉树前序遍历的非递归解法的PAR方法解题步骤  44-48
第四章结束语  48-50
  4.1 本文总结  48
  4.2 进一步的工作和展望  48-50
参考文献  50-52
附录  52-58
致谢  58-59

PAR方法在解信息学奥林匹克赛题中的应用研究

内容摘要

全文目录

相似论文