文档库

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

解题报告

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位的样子)。

总结:

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

结题报告
《教师反思与教师专业化成长的研究》 结题报告课题编号:2008-JKGHBzD-...
解题报告
程序设计方法与艺术 解题报告班组组级:计算机科学与技术 13-1 班长:2013...
结题报告完整版
大学生创新项目结题报告项目名称:大数据时代下自出版模式的发展前景分析项目成员:吴...
课题结题报告范本【三篇】
课题结题报告范本【三篇】篇一 《儿童传统游戏的现代好处挖掘》课题结题报告 一、研...
(完整版)结题报告
立项课题《无偿献血电脑语音咨询服务系统》成果鉴定材料结题报告成 果名称:无偿献血...
结题报告——范文
一、结题报告的基本结构 结题报告是一项课题研究结束,研究者客观地、概括地介绍研究...
结题报告范本
结题报告范本_调查/报告_表格/模板_实用文档。一、课题的提出:灰色的天空中弥漫...
课题研究结题报告(完整版)
*** 课题研究结题报告(完整版) 备注:该报告书文本主要按照原定计划完成任务后...
结题报告1
大学生科技创新训练计划(STITP)结题报告 项目名称 项目负责人 项目级别 学...
结题报告范文
结题报告 试验名称 药物名称 申办单位 药物分类 承担专业 分期 主要研究者 主...
课题结题报告的写法
结题报告的这 8 个部分, 除了第 8 部分外, 从第 1 到第 7 部分在填报...
结题报告包括哪些内容
v1.0 可编辑可修改结题报告是是我们在课题研究结束后对整个研究过程和研究成 果...
结题报告(模板)
第二届教师“个人课题”结题报告课题名称 课题编号 负责人 联系电话 填报日期太原...
(完整版)项目结题报告
淮南师范学院学生科学研究项目结题报告 项目名称 大蒜素对线虫生殖细胞凋亡和增殖的...
课题结题报告的格式要求范文
课题结题报告实验学校 建议包含以下部分: 领导小组成员 实验校 起止时间4、课题结题报告的理论依据 (500~800 字左右) 建议包含以下部分: 理论依据 课题结题报告......
结题报告范文
结题报告范文 一、课题的研究背景 路曼曼其修远兮,吾将上下而求索预设目标 加德纳...
结题报告怎么写
课题结题报告格式要求 一、 课题背景及立项 (800~1000 字左右) 二、 ...
结题报告范例
结题报告范例_调查/报告_表格/模板_实用文档。. 潍坊学院毕业论文结题报告 学...
结题报告——范文
一、结题报告的基本结构 结题报告是一项课题研究结束,研究者客观地、概括地介绍研究...
结题报告
绵 阳 职业技术学计算机科学系 院 实训项目结题报告项目名称 课程名称 专业 项...