毕业设计（论文）-NOI算法分析与例题解析.doc

西北师范大学毕业论文 NOI算法分析与例题解析 PAGE 2 毕 业 论 文 题 目： NOI算法分析与例题解析 学 院： 数学与信息科学学院 专 业： 计算机科学与技术（师） 毕业年限： 2011年6月 学生姓名： 学 号： 指导教师： 目 录 TOC \o 1-3 \h \z \u 1 引言 2 1.1 动态规划法 2 1.2排列与组合 2 2 算法解析及程序实现 2 2.1数字三角形 2 2.2最长公共子序列 2 2.3球迷购票问题 2 参考文献 2 致 谢 2 NOI算法分析与例题解析 曹黎斌 (西北师范大学 数学与信息科学学院计算机科学与技术(师),甘肃 兰州 730070) 中文摘要：论文是选取了全国青少年信息学奥林匹克联赛里面的题目，对题目的算法进行了详细的分析，并对里面的一些例题的进行了详细的解析。选取的题目都是关于动态规划的问题，即：对于一个具体的大问题，我们总是想方设法把它分成两个或多个更小的问题，然后分别解决每个小问题；再把各个小问题的解组合起来，即可得到原问题的解答。所选的题目包括数字三角形、最长公共子序列和花店橱窗布置三道题目。以上的题目都是由Pascal语言编写的，但现在c语言的学习和使用比较多，所以本论文的主要任务是将用Pascal语言写的以上题目的程序用c语言写出来，并能够正常的运行，能达到与Pascal语言一样的运行效果。 关键词：动态规划，Pascal程序，c程序 NOI Algorithm Analysis and Examples Resolution Abstract: Paper is to select a national youth league Olympiad in Informatics ,the subject carried out a detailed analysis of algorithms, and there were some examples of detailed analysis. Topics are selected on the dynamic programming problem, namely: the big issue for a specific, we are always trying to put it into two or more smaller problems, then solve each small problem, respectively; then every small problem combined solution, you can get answers to the original problem. The selected topics include digital triangle, the longest common subsequence and flower shop window display of three topics. The above questions are written by the Pascal language, but now c language learning and use more, so the main task of this paper is to use the Pascal language programs written in the above subject written by c language, and the normal operation , can achieve the same with the Pascal language operating results. Keywords: dynamic programming, Pascal program, c program 1 引言 教育部和中国科协委托中国计算机学会举办了全国青少年 计算机程序设计竞赛（简称：NOI），旨在向那些在中学阶段学习的青少年普及计算机科学知识；给学校的 信息技术教育课程提供动力和新的思路；给那些有才华的学生提供相互交流和学习的机会；通过竞赛和相关的活动培养和选拔优秀计算机人才。1984年参加竞赛的有8000多人。这一新的活动形式受到党和政府的关怀，得到社会各界的关注与支持。中央领导 王震同志出席了首届竞赛发奖大会，并对此项活动给