文档库

最新最全的文档下载
当前位置:文档库 > 解题报告

解题报告

NOIp2002普及组解题报告

湖南黄艺海

题一:级数求和

[问题描述]:

已知:S n=1+1/2+1/3+…+1/n。显然对于任意一个整数K,当n足够大的时候,Sn大于K。现给出一个整数K(1<=K<=15),要求计算出一个最小的n,使得Sn>K

[问题分析]:

这道题目非常简单,题目的意思已经把该题的算法描述得再清楚不过了,初始时Sn=0,n=0,然后每次循环n←n+1,Sn←Sn+1/n,,直到Sn大于K,最后输出K。另外实型(Real 是最慢的,建议用Extended)的运算速度不是很快,而K为1~15之间的整数,所以最后可以交一张表(常量数组),以达到最好的效果

[参考程序]:

解题报告

题二:选数

[问题描述]:

已知n(1<=n<=20)个整数x1,x2,…,xn(1<=xi<=5000000),以及一个整数k(k

[问题分析]:

本题动态规划无从下手,也无数学公式可寻,看来只能搜索(组合的生成算法),其实1<=n<=20这个约束条件也暗示我们本题搜索是有希望的,组合的生成可用简单的DFS来实现,既搜索这k个整数在原数列中的位置,由于组合不同于排列,与这k个数的排列顺序无关,所以我们可以令a[I]

解题报告

接下来的问题就是判断素数,判断一个整数P(P>1)是否为素数最简单的方法就是看是否存在一个素数a(a<=sqrt(P))是P的约数,如果不存在,该数就为素数,由于在此题中1<=xi<=5000000,n<=20,所以要判断的数P不会超过100000000,sqrt(p)<=10000,因此,为了加快速度,我们可以用筛选法将2…10000之间的素数保存到一个数组里(共1229个),这样速度估计将提高5~6倍。

特别注意:本题是要求使和为素数的情况有多少种,并不是求有多少种素数,比赛时就有很多同学胡乱判重而丢了12分;还有1不是素数,在判素数时要对1做特殊处理。

题四:过河卒

[问题描述]:

棋盘上A点有一个过河卒,需要走到目标B点。卒行走的规则:可以向下、或者向右。

同时在棋盘上C点有一个对方的马,该马所在的点和所有跳跃一步可达的点称为对方马的控制点。

棋盘用坐标表示,A点(0,0)、B点(n, m) (n,m为不超过20的整数),同样马的位置坐标是需要给出的。现在要求你计算出卒从A点能够到达B点的路径的条数

[问题分析]:

这是一道老得不能再老的题目了,很多书上都有类似的题目,NOIp97普及组的最后一题就和本题几乎一模一样。有些同学由于没见过与之类似的题目,在比赛时用了搜索,当n 到14,15左右就会超时,其实,本题稍加分析,就能发现:要到达棋盘上的一个点,只能从左边过来或是从上面下来,所以根据加法原理,到达某一点的路径数目,等于到达其相邻上,左两点的路径数目之和,因此我们可以使用逐列(或逐行)递推的方法来求出从起始顶点到重点的路径数目,即使有障碍(我们将马的控制点称为障碍),这一方法也完全适用,只要将到达该点的路径数目置为0即可,用F[i,j]表示到达点(i,j)的路径数目,g[i,j]表示点(i, j)有无障碍,递推方程如下:

F[0,0] = 1

F[i,j] = 0 { g[x,y] = 1 }

F[i,0] = F[i-1,0] {i > 0, g[x,y] = 0}

F[0,j] = F[0,j-1] {j > 0, g[x,y] = 0}

F[i,j] = F[i-1,j] + F[i,j-1] {i > 0, j > 0, g[x, y] = 0}

本题与第三题一样,也要考虑精度问题,当n,m都很大时,可能会超过MaxLongInt,所以要使用Comp类型计数(Comp类型已经足够了,即使n=20,m=20,没有任何障碍的情况下的结果也只有14,5位的样子)。

总结:

四道题目其实都很容易,要想到正确可行的方法并不难,考察的是大家的编程基础,一些基本算法的简单应用,并不需要什么优化技巧,关键是看大家对这些基本算法是否已熟练掌握,只有熟练掌握这些算法,在考试中才能在较短的时间内做好每道题,我们一定要重视基础!