NOI算法分析与例题解析计算机毕业论文.doc

NOI算法分析与例题解析目 录1 引言11.1 动态规划法11.2排列与组合12 算法解析及程序实现12.1数字三角形12.2最长公共子序列12.3球迷购票问题1参考文献1致 谢1NOI算法分析与例题解析 中文摘要：论文是选取了全国青少年信息学奥林匹克联赛里面的题目，对题目的算法进行了详细的分析，并对里面的一些例题的进行了详细的解析。选取的题目都是关于动态规划的问题，即：对于一个具体的大问题，我们总是想方设法把它分成两个或多个更小的问题，然后分别解决每个小问题；再把各个小问题的解组合起来，即可得到原问题的解答。所选的题目包括数字三角形、最长公共子序列和花店橱窗布置三道题目。以上的题目都是由Pascal语言编写的，但现在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 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 program1 引言教育部和中国科协委托中国计算机学会举办了全国青少年计算机程序设计竞赛（简称：NOI），旨在向那些在中学阶段学习的青少年普及计算机科学知识；给学校的信息技术教育课程提供动力和新的思路；给那些有才华的学生提供相互交流和学习的机会；通过竞赛和相关的活动培养和选拔优秀计算机人才。1984年参加竞赛的有8000多人。这一新的活动形式受到党和政府的关怀，得到社会各界的关注与支持。中央领导王震同志出席了首届竞赛发奖大会，并对此项活动给予了充分肯定。从此每年一次NOI活动，吸引越来越多的青少年投身其中。为了在更高层次上推动普及，培养更多的计算机技术优秀人才。竞赛及相关活动遵循开放性原则，任何有条件和兴趣的学校和个人，都可以在业余时间自愿参加。本人亦对此对于其中的几种算法进行了分析并读了NOI相关的教程及C语言、Pascal语言的程序设计和教程,并选出几道有代表性的题目,将原教程上用Pascal语言实现的程序进行了改写或重写,并全部改用C语言编程实现.1.1 动态规划法 动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此本人在学习时，不仅对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。1.2排列与组合排列组合是组合学最基本的概念。所谓排列，就是指从给定个数的元素中取出指定个数的元素进行排序。组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。排列组合的中心问题是研究给定要求的排列和组合可能出现的情况总数。2 算法解析及程序实现2.1数字三角形【问题描述】73 88 1 02 7 4 44 5 2 6 5上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径,把路径上面的数加起来可以得到一个和,和最大的路径称为最佳路径。你的任务就是求出最佳路径上的数字之和。注意:路径上的每一步只能从一个数走到下一层上和它最近的左边的数或者右边的数。输入：输入的第一行是一个整数 N (1 < N <= 100),给出三角形的行数。下面的 N 行给出数字三角形。数字三角形上的数的范围都在 0 和 100 之间。输出：输出为单独的一行，这一行中是一个整数，该整数为数字三角形的最大和。【输入样例】573 88 1 02 7 4 44 5 2 6 5【输出样例】30【问题分析】假设从顶至数字三角形的某一位置的所有路径中，所经过的数字总和最大的那条路径我们称之为该位置的最大路径。由于问题规定每一步只能沿直线或右斜线向下走，若要走到某一位置，则其前一位置比为其左上方或正上方两个位置之一。由此可知，当前位置的最优路径必定与其左上方或正上方两个位置的最优路径有关，且来自与其中更优的一个。我们可以用一个两位数组a记录数字三角形中的数，ai,j表示数字三角形中第i行第j列的数，再用一个两维数组maxsum记录每个位置的最优路径的数字总和。计算maxsum数组可以像计算杨辉三角形一样用逐行递推的方法实现，具体细节请看程序清单。【pascal源代码】Program p8_1(input,output);const maxline=100;var i,j,t,line:integer; a,max:array1.maxline,1.maxlineof integer;function maxsum(i,j:integer):integer;begin if i=line then maxsum:=ai,j else if maxsum(i+1,j)>maxsum(i+1,j)+ai,j else maxsum:=maxsum(i+1,j+1)+ai,jend;beginmain write('input number of line(<=100):');readln(line); for i:=1 to line do begin for j:=1 to i do begin ai,j:=random(99)+1; write(ai,j:3) writeln end; writeln; writeln('maxsum=',maxsum(1,1); max1,1:=a1,1; for i:=2 to line do begin maxi,1:=maxi-1,1+a1,1; for j:=2 to i-1 do if ai,j+maxi-1,j>=ai,j+maxi-1,j-1 then 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 t<maxline,i then t:=maxline,i; writeln('Then maximun sum is :',t)end.【C程序代码】#include <stdio.h>#define MAX_NUM 110int N,aMaxSumMAX_NUMMAX_NUM,DMAX_NUMMAX_NUM;int MaxSum(int i,int j)if(i=N)return Dij;if(aMaxSumi+1j=-1)aMaxSumi+1j=MaxSum(i+1,j);if(aMaxSumi+1j+1=-1)aMaxSumi+1j+1=MaxSum(i+1,j+1);if(aMaxSumi+1j>aMaxSumi+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",MaxSum(1,1);return 0;【运行结果】2.2最长公共子序列【问题描述】一个给定的序列的子序列是该序列中删除去若干元素后得到的序列。确切的説，若给定序列X=<x1,x2,.,xm>，则另一序列Z=<z1,z2, .,zk>是x的子序列是指存在一个严格的递增的下标序列<i1,i2,.,ik>使得对j=1,2,.,k, 有xij=zj。比如Z=<a,b,f,c> 是X=<a,b,c,f,b,c>的子序列。现在给出两个序列X和Y,你的任务是找到X和Y的最大公共子序列,也就是说要找到一个最长的序列 Z,使得Z既是X的子序列也是Y的子序列。例如，若x=<A,B,C,B,D,A, B>和y=<B,D,C,A,B,A>,则序列<B,C,A>是x和y的一个公共子序列，序列<B,C,B,A>也是x和y的一个公共子序列。而且，后者是x和y的一个最长公共子序列，因为x和y没有长度大于4的公共子序列。给定两个序列X=<x1,x2,.,xm>和Y=<y1,y2,yn>,要求找出x和y的一个最长公共子序列。输入：输入文件共有两行，每行为一个由大写字母构成的长度不超过200的字符串，表示序列x和y。输出：输出文件第一行为一个非负整数，表示所求得的最长公共子序列的长度，若不存在公共子序列，则输出文件仅有一行输出一个整数0，否则在输出文件的第二行输出所求得的最长公共子序列（一用一个大写字母组成的字符串表示），若符合条件的最长公共子序列不止一个，只需输出其中任意一个。【样例输入】 LCS.INABCBDABBDCABA【样例输出】LCS.OUTBCBA【问题分析】动态规划算法可有效的解决此问题，下面我们按照动态规划算法设计的各个步骤来设计一个解决此问题的有效算法。最长公共子序列的结构 解最长公共子序列问题时最容易想到的算法是穷举搜索法，即对么一个子序列，检查它是否也是y的子序列，从而确定他是否为x和y的公共子序列。并且在检查过程中选出最长的公共子序列。X的所有子序列都检查过后即可求出x和y的最长公共子序列。X的一个子序列相应于下标序列1,2，,m的一个子序列，因此，x共有2m个不同子序列，从而穷举搜索法需要指数时间。事实上，最长公共子序列问题也有最优子结构性质，因为我们有如下定理：定理：LCS的最优子结构性质设序列X=<x1,x2,.,xm>和Y=<y1,y2,yn>的一个最长公共子序列Z=<z1,z2, .,zk>，则：若Xm = Yn ,则 Zk=Xm=Yn且Zk-1是Xm-1和Yn-1的最长公共子序列：若Xm!=Yn ,则Zk!= Xm,则Z是Xm-1和Y的最长公共子序列：若Xm!=Yn 且Zk!=Yn，则Z是X和Yn-1的最长公共子序列。证明：用反证法。若Zk ！= Xm,则<z1,z2, .,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 有一个长度大k的公共子序列w，则w也是X和Y的一个长度大于k的公共子序列。这与Z是X和Y的一个最长公共子序列矛盾，由此即知Z是Xm-1和Y的一个最长公共子序列。这个定理告诉我们，两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列。因此最长公共子序列问题具有最优子结构性质。2.子问题重叠性质 有最长公共子序列问题的最优子结构性质可知，要找出X=<x1,x2,.,xm>和Y=<y1,y2,yn>的最长公共子序列，可按照以下方式递归的进行：当Xm = Yn时，找出Xm-1和Yn-1的最长公共子序列，然后在其尾部加上Xm（=Yn）即可得X和Y的一个最长公共子序列。当Xm!=Yn时，必须解两个子问题，即找出Xm-1和Y的一个最长公共子序列即X和Yn-1的一个最长公共子序列。这两个公共子序列中较长者即为X和Y的一个最长公共子序列。由此递归结构容易看到最长公共子序列问题具有子问题重叠性质。例如，在计算X和Y的最长公共那个子序列时，可能要计算X和Yn-1及Xm-1和Y的最长公共子序列。而这两个子问题都含一个公共子问题，即计算Xm-1和Yn-1的最长公共子序列。我们来建立子问题的最优值的递归关系。用ci,j记录序列Xi和Yj的最长公共子序列的长度。其中X=<x1,x2,.,xi>，Y=<y1,y2,yj>。当i=0或j=0时，空序列是xi和Yj的最长公共子序列，故ci,j=0。其他情况下，有定理可建立递归关系如下。 0 当i=0 或j=0时Ci,j= ci-1,j-1+1 当i,j>0且Xi=Yj时 max(cI,j-1,ci-1,j) 当i,j>0且Xi!=Yj时3计算最优值直接利用上式容易写出一个计算ci,j的递归算法，但其计算时间是随输入长度指数增长的。由于在所考虑的子问题空间中，总共有O(m*n)个不同的子问题，因此，用动态规划算法自底向上的计算最优值能提高算法的效率。计算最长公共子序列长度的动态规划算法LCS_LENGTH(X,Y)以序列X=<x1,x2,.,xm>和Y=<y1,y2,yn>作为输入。输出两个数组c0.m,0.n和b2.m,2.n。其中ci,j存储Xi和Yj的最长公共子序列的长度，bi,j记录指示ci,j的值是有哪一个子问题的解达到的，这在构造最长公共子序列是要用到。最后，x和y的最长公共子序列的长度记录与cm,n中。由于每个数组单元的计算耗费o(1)时间，算法LCS_LENGTH耗时O(MN)。4.构造最长公共子序列由算法LCS_LENGTH计算得到的数组b可用于快速构造序列X=<x1,x2,.,xm>和Y=<y1,y2,yn>的最长公共子序列。首先从bm,n开始，沿着其中的箭头所指的方向在数组b中搜索。当bI,j中遇到斜箭头时，表示Xi与Yj的最长公共子序列是由Xi-1与Yj-1的最长公共子序列在尾部加上Xi得到的子序列；当bI,j中遇到向时表示Xi与Yj的最长公共子序列和Xi-1与Yj的最长公共子序列相同；当当bI,j中遇到向时表示Xi与Yj的最长公共子序列和Xi与Yj-1的最长公共子序列相同；【pascal源程序】program p8_2(input,output);const maxlen=200;var i,j:longint; c:array0.maxlen,0.maxlenof byte; x,y,z:string;begin assign(input,'lcs.in'); reset(input); readln(x); readln(y); close(input); fillchar(c,sizeof(c),0); for i:=1 to length(x) do for j:=1 to length(y) do if xi=yj then ci,j:=ci-1,j-1+1 else if ci-1,j>ci,j-1 then ci,j:=ci-1,j else ci,j:=ci,j-1; z:='' i:=length(x); j:=length(y); assign(output,'lcs.out'); rewrite(output); writeln(ci,j); while(i>0)and(j>0)do if xi=yj then begin z:=xi+z; i:=i-1; j:=j-1; end else if ci-1,j>ci,j-1 then i:=i-1 else j:=j-1; if z<>'' then writeln(z); close(output)end.【c程序】#include <stdio.h>#include <string.h>#define MAX_LEN 200int main()char s1MAX_LEN+10,s2MAX_LEN+10;int MaxLenMAX_LEN+10MAX_LEN+10;int i,j,len1,len2,len3,len4;while(scanf("%s%s",s1+1,s2+1)>0)len1=strlen(s1+1);len2=strlen(s2+1);for(j=0;j<=len1;j+)MaxLen0j=0;for(i=0;i<=len2;i+)MaxLeni0=0;for(i=1;i<=len1;i+)for(j=1;j<=len2;j+)if(s1i=s2j)MaxLenij=MaxLeni-1j-1+1;elselen3=MaxLeni-1j;len4=MaxLenij-1;if(len3>len4)MaxLenij=len3;elseMaxLenij=len4; printf("%dn",MaxLenlen1len2); return 0;【运行结果】2.3球迷购票问题【问题描述】盛况空前的足球赛即将举行。球赛门票售票处排起了长龙。按售票处规定每位购票者限购一张门票，且每张售票价为50元。在排成长龙的球迷中，有m个人手持面值50元的钱币，另有n个人手持面值100元的钱币。假设售票处在开始售票时没有零钱。试问这m+n个球迷有多少种排队方式可使售票处不致出现找不出钱的尴尬局面。例如当m=3,n=2时，用A表示手持面值50元钱币的球迷，用B表示手持面值100元钱币的球迷，则最多可以得到以下5组不同的排队方式，使售票处不致出现找不出钱的尴尬局面。售票处AAABB售票处AABAB售票处ABAAB售票处AABBA售票处ABABA编程任务：对于给定的m和n的值（0m,n5000）,编程计算出m+n个球迷有多少种排队方式可使售票处不致出现找不出钱的尴尬局面。数据输入：【输入】football.in,共一行表示m和n的值。【输出】程序运行结束时，将计算出的排队方式数写入文件名为football.out的文本文件中。每个计算结果占两行，第一行为输出数据的十进制位数，第二行是相应的输出数据。【样例】football.in2football.out15【问题分析】假设将手持50元人民币的球迷记为S，持100元人民币的球迷则记为X，则m个手持50元人民币与n个手持100元人民币的球迷队伍就可表示为一个具有m个S和n个X的字符串，显然这样的字符串共有个，其中不满足问题要求的串一定存在一个最靠左的位置P，使得从第一个字符到第P个字符为止的子串中X的个数比S的个数大1，如SX-SXX就是一个不满足条件的串，其中P=5。我们将从头到P为止的串中的字符S与X互换，则得到一个具有m+1个S和n-1个X的串，可以证明这种转换是一一对应的，即任意一个具有m+1个S，n-1个X的串都可以按照逆规则转换成一个不满足题目条件的串。转换规则为在任意一个m+1个S和n-1个X的串中找到最靠左边的位置P，使得从头到P的子串中S的个数比X的个数大1，将到P为止的子串中的字符S与X互换，则得到一个m个S和n个X的串，且此串肯定不满足题目要求，而具有m+1个S，n-1个X的串共有个，所以共有-=种排队方式可使售票处不致出现找不出钱的尴尬局面。由于问题的规模较大，结果远远超出长整型的范围，所以程序运用了高精度运算，虽然结果表达式中有分母，但实际结果一定是整数，所以不需要做除法运算，具体运算时只要求出的质因子分解式，然后做高精度乘法即可，而任意一个质因子r在n!中出现的次数为+。【pascal源代码】program p9_4(input,output);const maxm=5000;type arraytype=array0.maxm of longint;var i,j,k,m,n,h:longint; t:arraytype; p:array1.maxm*2 of boolean;function d(m,n,i:longint):longint; var s,temp:longint; begin s:=0; temp:=m+1-n; while temp mod i=0 do begin s:=s+1; temp:=temp div i end; temp:=(m+n) div i; while temp>0 do begin s:=s+temp; temp:=temp div i end; temp:=(m+1) div i; while temp>0 do begin s:=s-temp; temp:=temp div i end; temp:=n div i; while temp>0 do begin s:=s-temp; temp:=temp div i end; d:=s. end;begin main assign(input,'football.in'); reset(input); readln(m,n); close(input); assign(output,'football.out'); rewrite(output); if m<n then begin writeln(0);writeln(0);close(output);halt end; fillchar(t,sizeof(t),0); t0:=1; h:=0; for i:=1 to maxm*2 do pi:=true; i:=2; while i*i<maxm*2 do begin j:=2*i; while j<=maxm*2 do begin pj:=false; j:=j+i; end; i:=i+1; end; for i:=2 to m+n do if pi then for j:=1 to d(m,n,i) do begin for k:=0 to h do tk:=tk*i; for k:=0 to h-1 do begin tk+1:=tk+1+tk div 10; tk:=tk mod 10 end; k:=h; while tk>9 do begin tk+1:=tk+1+tk div 10; tk:=tk mod 10; k:=k+1 end; h:=k end; writein(h+1); for i:=h downto 0 do write(ti); writeln; close(output)end.【c源代码】#include <iostream>using namespace std;#include <ctime>int sum = 0;void print_queue(const char * container, const int size) for(int i=0; i<size-1; i+) cout<<containeri<<", " cout<<endl;void ticket(char * container, const int size, int pos, int m, int n) if(n<=0 && m<=0) sum +; /print_queue(container, size); int countX=0, countY=0; if(m>0) m -; containerpos +='X' for(int count=0; containercount != 0x00; count+) if(containercount = 'X') countX +; else if(containercount = 'Y') countY +; if(countX >= countY) ticket(container, size, pos, m, n); containerpos = 0x00; pos -; m +; if(n>0) n -; containerpos +='Y' countX = countY = 0; for(int count=0; containercount != 0x00; count+) if(containercount = 'X') countX +; else if(containercount = 'Y') countY +; if(countX >= countY) ticket(container, size, pos, m, n); containerpos = 0x00; pos -; n +; int main() int m, n; cout<<"Input m:" cin>>m; cout<<"Input n:" cin>>n; if(m<n | m<0 | n<0 | m>5000 | n>5000) cout<<"Wrong number value!"<<endl; return -1; int size = m+n+1; char * container = new charsize; / save the sequenece of the queue memset(container, 0x00, size); clock_t t_start, t_end; t_start = clock(); ticket(container, size, 0, m, n); cout<<"Sum = "<<sum<<endl; t_end = clock(); cout<<"Time cost : "<< (double)(t_end-t_start)/CLOCKS_PER_SEC <<" seconds."<< endl; delete container; return 0;【运行结果】3 结束语上述几道题只简单的描述了动态规划算法和组合数学里面的排列组合问题，并没有做一些更加深入的探讨，并只是简单的将pascal程序翻译成c程序。但解决问题的算法还有很多，像回溯法、枚举法、递推法及递归法等等,将在以后继续研究分析。经分析论证,在使用相应算法的基础上,上述问题的解决方法达到了最优的时间复杂度,这说明上述问题可以通过这些算法得到较好的解决.仍然存在着许多不足之处,还可以作进一步的改进,如存储空间的浪费比较明显,某些细节的操作还可以优化等等.参考文献1 曹文.全国青少年信息学奥林匹克联赛培训教材(中学高级本)M.南京:南京大学出版社,2004.2 谭浩强,田淑清.PASCAL语言程序设计(第二版)M.北京:高等教育出版社,19