NOI算法分析与例题解析 计算机毕业论文.doc
《NOI算法分析与例题解析 计算机毕业论文.doc》由会员分享,可在线阅读,更多相关《NOI算法分析与例题解析 计算机毕业论文.doc(19页珍藏版)》请在三一文库上搜索。
1、NOI算法分析与例题解析目 录1 引言11.1 动态规划法11.2排列与组合12 算法解析及程序实现12.1数字三角形12.2最长公共子序列12.3球迷购票问题1参考文献1致 谢1NOI算法分析与例题解析 中文摘要:论文是选取了全国青少年信息学奥林匹克联赛里面的题目,对题目的算法进行了详细的分析,并对里面的一些例题的进行了详细的解析。选取的题目都是关于动态规划的问题,即:对于一个具体的大问题,我们总是想方设法把它分成两个或多个更小的问题,然后分别解决每个小问题;再把各个小问题的解组合起来,即可得到原问题的解答。所选的题目包括数字三角形、最长公共子序列和花店橱窗布置三道题目。以上的题目都是由Pa
2、scal语言编写的,但现在c语言的学习和使用比较多,所以本论文的主要任务是将用Pascal语言写的以上题目的程序用c语言写出来,并能够正常的运行,能达到与Pascal语言一样的运行效果。关键词:动态规划,Pascal程序,c程序NOI Algorithm Analysis and Examples ResolutionAbstract: Paper is to select a national youth league Olympiad in Informatics ,the subject carried out a detailed analysis of algorithms, and
3、 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
4、 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 t
5、o 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 program1 引言教育部和中国科协委托中国计算机学会举办了全国青少年计算机程序设计竞赛(简称:NOI),旨在向那些在中学阶段学习的青少年普及计
6、算机科学知识;给学校的信息技术教育课程提供动力和新的思路;给那些有才华的学生提供相互交流和学习的机会;通过竞赛和相关的活动培养和选拔优秀计算机人才。1984年参加竞赛的有8000多人。这一新的活动形式受到党和政府的关怀,得到社会各界的关注与支持。中央领导王震同志出席了首届竞赛发奖大会,并对此项活动给予了充分肯定。从此每年一次NOI活动,吸引越来越多的青少年投身其中。为了在更高层次上推动普及,培养更多的计算机技术优秀人才。竞赛及相关活动遵循开放性原则,任何有条件和兴趣的学校和个人,都可以在业余时间自愿参加。本人亦对此对于其中的几种算法进行了分析并读了NOI相关的教程及C语言、Pascal语言的程
7、序设计和教程,并选出几道有代表性的题目,将原教程上用Pascal语言实现的程序进行了改写或重写,并全部改用C语言编程实现.1.1 动态规划法 动态规划问世以来,在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题,用动态规划方法比用其它方法求解更为方便。虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题,但是一些与时间无关的静态规划(如线性规划、非线性规划),只要人为地引进时间因素,把它视为多阶段决策过程,也可以用动态规划方法方便地求解。动态规划程序设计是对解最优化问题的一种途径、一种方法,而不是一种特殊算法。不象
8、前面所述的那些搜索或数值计算那样,具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题,由于各种问题的性质不同,确定最优解的条件也互不相同,因而动态规划的设计方法对不同的问题,有各具特色的解题方法,而不存在一种万能的动态规划算法,可以解决各类最优化问题。因此本人在学习时,不仅对基本概念和方法正确理解外,必须具体问题具体分析处理,以丰富的想象力去建立模型,用创造性的技巧去求解。动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中,可能会有许多可行解。每一个解都对应于一个值,我们希望找到具有最优值的解。动态规划算法与分治法类似,其基本思想也是将待求解问题分
9、解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。1.2排列与组合排列组合是组合学最基本的概念。所谓排列,就是指从给定个数的元素中取出指定个数的元素进行排序。组合则是指从给定个数的元素中仅仅取出指定个数的元素,不考虑排序。排列组合的中心问题是研究给定要求的排列和组合可能出现的情况总数。2 算法解析及程序实现2
10、.1数字三角形【问题描述】73 88 1 02 7 4 44 5 2 6 5上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径,把路径上面的数加起来可以得到一个和,和最大的路径称为最佳路径。你的任务就是求出最佳路径上的数字之和。注意:路径上的每一步只能从一个数走到下一层上和它最近的左边的数或者右边的数。输入:输入的第一行是一个整数 N (1 N maxsum(i+1,j)+ai,j else maxsum:=maxsum(i+1,j+1)+ai,jend;beginmain write(input number of line(=ai,j+maxi-1,j-1 th
11、en maxi,j:=ai,j+maxi-1,j else maxi,j:=ai,j+maxi-1,j-1; maxi,j:=maxi-1,i-1+ai,i end; t:=0; for i:=1 to line do if tmaxline,i then t:=maxline,i; writeln(Then maximun sum is :,t)end.【C程序代码】#include #define MAX_NUM 110int N,aMaxSumMAX_NUMMAX_NUM,DMAX_NUMMAX_NUM;int MaxSum(int i,int j)if(i=N)return Dij;i
12、f(aMaxSumi+1j=-1)aMaxSumi+1j=MaxSum(i+1,j);if(aMaxSumi+1j+1=-1)aMaxSumi+1j+1=MaxSum(i+1,j+1);if(aMaxSumi+1jaMaxSumi+1j+1)return aMaxSumi+1j+Dij;return aMaxSumi+1j+1+Dij;int main()int i,j;scanf(%d,&N);for(i=1;i=N;i+)for(j=1;j=i;j+)aMaxSumij=-1;for(i=1;i=N;i+)for(j=1;j=i;j+)scanf(%d,&Dij);printf(%dn,M
13、axSum(1,1);return 0;【运行结果】2.2最长公共子序列【问题描述】一个给定的序列的子序列是该序列中删除去若干元素后得到的序列。确切的説,若给定序列X=,则另一序列Z=是x的子序列是指存在一个严格的递增的下标序列使得对j=1,2,.,k, 有xij=zj。比如Z= 是X=的子序列。现在给出两个序列X和Y,你的任务是找到X和Y的最大公共子序列,也就是说要找到一个最长的序列 Z,使得Z既是X的子序列也是Y的子序列。例如,若x=和y=,则序列是x和y的一个公共子序列,序列也是x和y的一个公共子序列。而且,后者是x和y的一个最长公共子序列,因为x和y没有长度大于4的公共子序列。给定两个
14、序列X=和Y=,要求找出x和y的一个最长公共子序列。输入:输入文件共有两行,每行为一个由大写字母构成的长度不超过200的字符串,表示序列x和y。输出:输出文件第一行为一个非负整数,表示所求得的最长公共子序列的长度,若不存在公共子序列,则输出文件仅有一行输出一个整数0,否则在输出文件的第二行输出所求得的最长公共子序列(一用一个大写字母组成的字符串表示),若符合条件的最长公共子序列不止一个,只需输出其中任意一个。【样例输入】 LCS.INABCBDABBDCABA【样例输出】LCS.OUTBCBA【问题分析】动态规划算法可有效的解决此问题,下面我们按照动态规划算法设计的各个步骤来设计一个解决此问题
15、的有效算法。最长公共子序列的结构 解最长公共子序列问题时最容易想到的算法是穷举搜索法,即对么一个子序列,检查它是否也是y的子序列,从而确定他是否为x和y的公共子序列。并且在检查过程中选出最长的公共子序列。X的所有子序列都检查过后即可求出x和y的最长公共子序列。X的一个子序列相应于下标序列1,2,,m的一个子序列,因此,x共有2m个不同子序列,从而穷举搜索法需要指数时间。事实上,最长公共子序列问题也有最优子结构性质,因为我们有如下定理:定理:LCS的最优子结构性质设序列X=和Y=的一个最长公共子序列Z=,则:若Xm = Yn ,则 Zk=Xm=Yn且Zk-1是Xm-1和Yn-1的最长公共子序列:
16、若Xm!=Yn ,则Zk!= Xm,则Z是Xm-1和Y的最长公共子序列:若Xm!=Yn 且Zk!=Yn,则Z是X和Yn-1的最长公共子序列。证明:用反证法。若Zk!= Xm,则是X和Y的长度为k+1的公共子序列。这与z是x和y的一个最长公共子序列相矛盾。因此,必有Zk=Xm=Yn。由此可知Zk-1是Xm-1和Yn-1的一个长度为k-1的公共子序列。若Xm-1和Yn-1有一个长度大于k-1的公共序列w,则将Xm加在其尾部将产生x和y的一个长度大于k的公共子序列,此为矛盾。故Zk-1是Xm-1和Yn-1的一个最长公共子序列。又由于Zk!= Xm,Z是Xm-1和Y的一个公共子序列。若Xm-1和Y 有
17、一个长度大k的公共子序列w,则w也是X和Y的一个长度大于k的公共子序列。这与Z是X和Y的一个最长公共子序列矛盾,由此即知Z是Xm-1和Y的一个最长公共子序列。这个定理告诉我们,两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列。因此最长公共子序列问题具有最优子结构性质。2.子问题重叠性质 有最长公共子序列问题的最优子结构性质可知,要找出X=和Y=的最长公共子序列,可按照以下方式递归的进行:当Xm = Yn时,找出Xm-1和Yn-1的最长公共子序列,然后在其尾部加上Xm(=Yn)即可得X和Y的一个最长公共子序列。当Xm!=Yn时,必须解两个子问题,即找出Xm-1和Y的一个最长公共子序
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- NOI算法分析与例题解析 计算机毕业论文 NOI 算法 分析 例题 解析 计算机 毕业论文
链接地址:https://www.31doc.com/p-3902638.html