tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 学科竞赛 >>

杭州第四中学联赛辅导


复习内容
计算机的基础知识 学科知识(物理和数学知识、高精度运算、 表达式处理、进制转换) PASCAL语言 数据结构(顺序存储结构的线性表、栈、队列、串、非线性结构—
树和图)

归纳策略(递推法和递归法、贪心法)

开放性试题(用开放性的思维方式解题)
搜索策略( 枚举法、 回溯法、宽度优先搜索) 动态程

序设计方法

1、计算机基础知识 2、2002年—分区联赛高中 组试题解析

3、改善高精度运算的效率 4、构造法

一、 计算机的发展与应用

二、计算机组成与工作原理 和信息的表示与存储
三、多媒体应用 四、计算机网络使用基础

五、程序设计语言基础
六、程序的阅读分析

⑴计算机的发展历经了哪几个阶段; ⑵按照功能和规模,可将计算机分成哪几大 类,它们各自的分工是什么; ⑶武装计算机的软件系统包括了哪些东西; ⑷计算机的发展怎样促使人类走向丰富多彩 的信息社会;

⑸用户在使用计算机时应该遵守哪些道德规 范;

计算机发展史上的里程碑——计算机存储程 序的工作原理
美籍匈牙利数学家冯· 诺依曼(von Neumaml)在1946年提出的,其思想 是,在计算机中设置存储器,将符号化的计算步骤存放在存储器中,然 后依次取出存储的内容,由一个被称之为控制器的部件进行译码,译码 结果在一个被称为运算器的部件中进行计算,从而实现计算机工作的自 动化(运算器和控制器统称为CPU)。冯· 诺依曼依据此原理设计出一个 完整的计算机雏形,并确定了计算机的五大组成部分和基本的工作方法。

第四代
VISI——大规模集成电路 CISC——复杂指令系统计算机 RCSC——精简指令系统计算机 非冯· 诺依曼式语言:lisp、prologo、f.p

第五代
NC——网络计算机(将整个网络看成一个巨大的 磁盘驱动器,数据和文件存储在服务器) 非冯· 诺依曼式的计算机模型(以人脑神经系统处 理信息的原理为基础):生物计算机、光子计算 机、量子计算机

用户
应用软件 系统软件

裸机

操作系统是计算机系统中的一种系统软件,它 能对计算机系统中的软件和硬件资源进行有效地 管理和控制,合理地组织计算机的工作流程,为 用户提供一个使用计算机的工作环境。 手工操作 管理程序 单道批处理系统 分时系统 网络操作系统

多道批处理系统 实时操作系统

DOS——单用户的唯一任务占用计算机上所 有的硬件和软件资源,所能访问的主存地址 空间太小。 Windows——多作业、大内存管理、统一 的图形用户界面 ,并且发展到网络环境使 用 UNIX操作系统 、Linux操作系统 、Macintosh OS

数据库技术的特性 ⑴最小冗余 ⑵数据共享

目前,世界上比较流行的数据库管 理系统(DMS)有
⑴高档数据库产品,如Informix,Oracle, Sybase,Progress,Unify等 ⑵中、低档数据库产品,如DBASE,Paradox, Super-Base,Foxpro,Clipper,SQL Base, Focus等; ⑶数据库开发工具,如Access,Visual Basic, Uniface,Power Builder,Q+EDatabase Editor 等。

⑶数据独立性
⑷安全性 ⑸完整性 数据库管理系统的类型
⑴OLTP(联机事务处理) ⑵DSS(决策支持系统) ⑶EIS(行政信息系统) ⑷OA(办公室自动化)

⑸按其系统结构分为单机、Unix多用户、网络多用户、客户机/服务器、 集中式、分布式、集中分布式等。

计算机病毒的特征
⑴能够将自身复制到其他程序中。 ⑵不独立以文件形式存在,仅附加在别的程序上。 当调用该程序运行时,此病毒则首先运行。 防治病毒的步骤:

⑴不要用软盘启动机器
⑵不要运行来路不明的软件 ⑶定期备份重要系统数据 ⑷重要的数据盘,程序盘应写保护 ⑸使用杀毒软件检查和清除病毒

进位计数制之间的转换问题。 1、R进制转换为十进制
基数为R的数字,只要将各位数字与它的权相乘,其积相加,和数就 是十进制数 (xp…x0.x-1…x-k)R=(? ( x ? R ) )10
i i i ??k p

例: 1101101.01012 =1×2°+0×21+1×22+1×23十0×24+1×25+1×26+0×2-1+1×2-2 +0×2-3+1×2-4

=109.3125
当从R进制转换到十进制时,可以把小数点作为起点,分别向左右 两边进行,即对其整数部分和小数部分分别转换。对于二进制来说, 只要把数位是1的那些位的权值相加,其和就是等效的十进制数。

2、十进制转换为R进制
将此数分成整数与小数两部分分别转换,然后再拼接起来。 +进制整数转换成R进制的整数,可用十进制数连续地除以R,其 余数即为R系统的各位系数。此方法称之除R取余法。例如:将 5710转换为二进制数

十进制小数转换成R进制时,可连续地乘以R,直到小数部分为0, 或达到所要求的精度为止(小数部分可能永不为零),得到的整 数即组成R进制的小数部分,此法称为“乘R取整” 例:将0.312510转换成二进制数 0.3125×2 =0.625 0.625×2 =1.25 0.25×2=0.5 0.5×2 =1.0

3、二、八、十六进制的相互转换 即每位八进制数相当于三位二进制数,每位十六进制数相当 于四位二进制数。在转换时,位组划分是以小数点为中心向 左右两边延伸,中间的0不能省略,两头不够时可以补0。
例如:将1011010.10-转换成八进制和十六进制数 2 001 011 010. 100 1011010.102=132.48 1 3 2. 4 1011010.102=5A.816 0101 1010. 1000 5 A. 8

将十六进制数F7.28变为二进制数 F 7. 2 8 F7.2816=11110111.001012

1111 0111.0010 1000

将八进制数25.63转换为二进制数 2 5. 6 3 25.638=10101.1100112

10 101 . 110 011

三、在计算机中带符号数的表示法 1、机器数与真值
规定在数的前面增设一位符号位,正数符号位用“0”表示,负数符号位用“1”表 示。

为了区别原来的数与它在计算机中的表示形式,我们将已经数码化了的带符号数 称为机器数,而把原来的数称为机器数的真值。例如N1=+1001100、N2=-1001100为 真值,其在计算机中的表示01001100和11001100为机器数。 2、原码〈true form〉
在用二进制原码表示的数中,符号位为0表示正数,符号位为1表示负数,其余各 位表示数值部分。这种表示法称为原码表示法。字长为n的数(包括符号位)的 原码表示法可定义为[x]原=

若真值丨x丨<1,其原码表示法可定义为[x]原=

例如对于8位二进制原码
[+0]原=00000000,[-0]原=10000000 [-1101001]原=10000000-(-1101001)=11101001

3、补码(two’s complement)
即[x]补=模+x 对于正数, [x]补=x,正数的补码就是该正数本身。

对于负数, [x]补=2n+x(mod 2n)。
[+0]补=[-0]补=00…0 [-2n-1]补=2n-2n-1=2n-1

4、反码〈0ne’s Complement〉
对于正数,它的反码表示与原码相同。即[x]反=[x]原 对于负数,则除符号位仍为“1”外,其余各位“1”换成”0”,”0”换成1”, 即得到反码[X]反。例如[-1101001] 反=10010110。 对于0,它的反码有两种表示:[+0] 反=00…0 [-0] 反=11…1 当x为正数时,[x]反=[x]原=[x]补=x;当x为负数时,[x]补=2n+x=(2n-1)+x+1=[x]反+1, 即[x]原除符号位外求反加1。若把[x]补除符号位外求反加1,就得到[x]原,即[[x]补] 补=[x]原。例如x=-1101001。[x]原=11101001,[x]补=10010111, [[x]补]补=11101001 =[x]原。

5、补码的加减法运算 ⑴补码的加法运算
在计算机中进行两个带符号数的加法运算时,只要将给定的真值 用补码表示,就可以直接进行加法运算。在运算过程中不必判断加 数和被加数的正负,一律做加法,最后将结果转换为真值即可。

⑵补码的减法运算
对于补码的减法运算,由于存在x-y=x+(-y),因此

[x-y]补=[x+(-y)] 补=[x]补+[-y]补 (mod2n)
其中[-y]补=[[y]补]补。

信息存储单位
⑴位(bit,缩写为b):度量数据的最小单位,表示一位二进制信息。 ⑵字节(byte,缩写为B):一个字节由八位二进制数字组成(l byte=8bit)。 字节是信息存储中最常用的基本单位。 计算机存储器(包括内存与外存)通常也是以多少字节来表示它的容量。 常用的单位有:KB 1K=1024,MB 1M=1024K,GB 1G=1024M ⑶字(word):字是位的组合,并作为一个独立的信息单位处理。字又称 为计算机字,它的含意取决于机器的类型、字长以及使用者的要求。常用 的固定字长有8位、16位、32位等。 信息单位用来描述机器内部数据格式,即数据(包括指令)在机器内的排 列形式,如单字节数据,可变长数据(以字节为单位组成几种不同长度的 数据格式)等。 ⑷机器字长:在讨论信息单位时,还有一个与机器硬件指标有关的单位, 这就是机器字长。机器字长一般是指参加运算的寄存器所含有的二进制数 的位数,它代表了机器的精度。机器的功能设计决定了机器的字长。一般 大型机用于数值计算,为保证足够的精度,需要较长的字长,如32位、64 位等。而小型机、微型机、微机一般字长为16位、32位等。

非数值信息的表示 西文字符编码
⑴ASCII码 ——“美国信息交换标准代码”的简称。ASCII码包括0~9十个数字,大小写 英文字母及专用符号等95种可打印字符,还有33种控制字符(如回车、换行等)。一个字 符的ASCII码通常占一个字节,用七位二进制数编码组成,所以ASCII码最多可表示128个 不同的符号。最高位作为校验码,以便提高字符信息传输的可靠性。 数字和字母的ASCII码按照数字递增顺序或字典顺序排列排列,大写字母和小写字母的 ASCII码是不同的。 ⑵EBCDIC码——美国IBM公司在它的各类机器上广泛使用的一种信息代码。一个字符的 EBCDIC码占用一个字符,用八位二进制码表示信息,最多可以表示出256个不同代码。

中文信息编码
目前的汉字编码方案有二字节、三字节甚至四字节的。下面我们主要介绍“国家标准信息 交换用汉字编码”(CB2312-80标淮),以下简称国标码。

国际码是二字节码,用二个七位二进制数编码表示一个汉字。目前国标码收人6763个汉字, 其中一级汉字(最常用)3755个,二级汉字3008个,另外还包括682个西文字符、图符。 在计算机内部,汉字编码和西文编码是共存的。区分的方法之一是对于二字节的国标码, 将二个字节的最高位都置成1,而ASCIl码所用字节最高位保持0,然后由软件(或硬件) 根据字节最高位来作出判断。

“多媒体技术”就是用计算机交互地综合处理文 本、图形、图象、动画、音频及视频影象等多种
信息,并使这些信息建立逻辑连接。

显示模式
色彩数目 分辨率 特点
16 256 65536 16M 640*480 800*600 1024*768 1284*1024 Windows的最低配置、显示速度最快 性能虽好一些,但易产生调色板的冲突 全彩的显示模式,色彩逼真,不会再有调色板的 冲突。 高等级的3D绘图软件和专业级的视频录制人员使 用的真彩色模式,要求更多的RAM在显示卡和主 机板上,CPU最好也是顶级的。

显示卡
水平分辨率×垂直分辨率×色彩数目=显示存储空间 显示加速:VRAM、EDO RAM,Windows RAM,Ramlbus DRAM

数据压缩和解压缩技术
静止图像压缩标准JPEG(Joint Photographic ExpertsCroup) 动态图像压缩标准MPEG(Moving Picture Experts Croup) 多通道的动态图像压缩标准MP×64

相关名词
位图:由一点一点的像素点排成矩阵组成的,其中每一个像素点都可以是 任意颜色。 向量图:用向量代表图中所表现的元素。 像素 :图形的最小组成单位 真彩色:人的眼睛能够分辨出的颜色大约有1万6千多种,为了能表现出 这么多种色彩,我们得用24bit(224=16M)来描述一个像素的颜色,这种 显示模式就称为真彩色。 RGB模式:分别代表红、绿、蓝三种颜色,计算机以RGB模式来定义计算 机屏幕上的颜色。通过混色原理,不同比例的RGB色彩可调和出无穷多种 颜色。 HSB模式:分别表示色调(hue)、饱和度(saturation)、亮度(bright)。 不同的色调代表不同的颜色;饱和度指的是某区域中,该颜色量的多少, 饱和度越低,该区域看起来就越灰暗;亮度则是指颜色的亮、暗,极亮成 白色,极暗则成黑色。相对于RGB模式,HSB模式设定颜色的方式可产生 更好的视觉效果。

多媒体信息处理工具
图形制作平台FreeHand 图像处理平台Photoshop 动画制作平台 Animation Pro 数字动画的类型:
⑴基于模型的动画 ⑵帧动画

动画中加人声音的方法
⑴嵌人式—将声音文件经过转换合并到影片文件中去。 ⑵流式—声音与文件分开,在影片播放的各个时机启动声音文件

音乐
⑴波形音频文件 :通过现场录制和模数转化产生,存储量大 ⑵MIDI文件:使用键盘合成器和一个音序器 制作和编辑,存储量小

广域网( WAN ):实现远距离的计算机之间的数据传输和 信息共享的计算机网络。通信线路一般租用电话线路或铺设 专用电缆。 局域网络(LIN):为一个单位,或一个相对独立的局部范围 内大量存在的微机能够相互通信、共享昂贵的外部设备(如 大容量磁盘、激光打印机、绘图议等)、共享数据信息和应 用程序而建立的计算机网络。通信线路一般不租用电话线路, 使用专门铺设的线路。

互联网(Internet):将遍布全球的子网通过连网协议集成到
一个共享的、开放的、易于管理的主干网。

计算机网络的物理组成
? ? ? ? ? ?

网络中心主干机 、服务器 、网络工作站 共享的外部设备 网卡 通信线路(双绞线、同轴电缆和光缆、无线传输介质(如微波、红
外线和激光等))

?

局部网络通信设备(中继器、集线器 ) 网络互连设备 (网桥、路由器和网关 ) 网络软件 (对等式网络操作系统 、服务器上的网络操作系统)

计算机网络的拓扑结构
?

总线拓扑

?

星型拓扑

环型拓扑

树型拓扑

计算机网络的体系结构
?

所谓网络体系结构就是对构成计算机网络的各组成部分之间的关系及所要 实现功能的一组精确定义。国际标准化组织(ISO)提出的开放系统互联 参考模型(OSI)已成为网络体系结构的标准

Internet使用TCP/IP网络体系结构
TCP/IP的层号 3 TCP/IP的层次名 对应OSI模型的层次 应用层(ftp和 telnet等协议) 传输控制协议 TCP 网际协议IP 应用层、表示层、 会话层 传输层 网络层

2 1

计算机网络应用模式
? ? ? ? ?

客户机/服务器模型:将应用分成客户机和服务器两大部分,
并将它分配到整个网络上。由服务器提供资源,通常执行后台功能;而客 户机使用服务器,通常执行前台功能。

文件服务器:提供操作系统中文件管理的各种功能(网络文件的
访问方式:文件传输和文件访问 )

打印服务器:将一台或几台打印机物理地连接到打印服务器上,
可为多个客户机用户轮流使用

数据库服务器:侧重于传统数据库管理系统的功能(如数据的
定义及存取、数据的安全性与完整性、并发控制及事务处理等)的服务器

远程登录:通过用户帐号访问远地系统的资源

Internet 网络地址
?

IP地址:

网络数
A类网络 B类网络 C类网络 总计 126 16256 2064512 2084894

网络主机数 主机数
16387064 64516 254 2064770064 1048872096 524386048 3638028208

域名(或称主机名称):计算机主机名.子域名.子域名.最高层域名

Internet应用
? ?

文件传输 (使用匿名文件传输服务(匿名FTP)网上软件分类:公
共软件 、免费软件 、共享软件 )

?
?

远程登录(Telnet 命令) 电子邮政服务 (电子邮箱地址:用户名@计算机域名) 网络新闻与公告牌服务 (网络新闻是由USENET在Internet中
的新闻服务器节点之间进行传递的,阅读新闻组的软件有Outlook Express)

?

信息查询服务 (最为流行的信息查询服务系统是万维网(World
Wide Web),简称WWW。 注意超文本和超媒体的概念 )

程序设计语言的组成
?
? ?

程序设计语言的基础是一组记号和规则。根据规 则由记号构成的记号串的总体就是语言。 包括
语法:程序的结构或形式。编译系统会自动进行语法检验; 语义:程序的含义,亦即表示按照各种方法所表示的各个记号的特定 含义,但不涉及使用者。语义的错误是在源程序编译通过后的运行过程 中出现的,属于算法类的错误。 语用:程序和使用者的关系;

?

?
? ? ?

语言的成分
⑴数据成分,用以描述程序中所涉及的数据; ⑵运算成分,用以描述程序中所包含的运算; ⑶控制成分,用以描述程序中的控制构造; ⑷传输成分,用以表达程序中数据的传输。

?

语言和程序设计的发展
? ?

?
?

?

第一代语言——机器语言 第二代语言——汇编语言 第三代语言——高级语言、算法语言(BASIC、 FORTRAN、COBOL、Pascal、C ) 第四代语言——非过程化语言(SQL语言) 第五代语言——智能性语言(PROLOG语言 、 LISP语言 )

面向对象方法的主要概念
? ?

?
?

?

⑴对象——系统中用来描述客观事物的一个实体,是 构成系统的一个基本单位,对象由两个主要因素组成: 属性:描述对象静态特征的一个数据项; 服务:描述对象动态特征的一个操作序列; ⑵消息——对象之间通过服务请求发生联系,这种向 对象发出的服务请求称为消息。 ⑶类——为了很好地控制软件的复杂度,将具有相同 属性和服务的一组对象组成类。

面向对象语言分为两大阵营
? ⑴Smalltalk和Eiffel为代表的纯粹型

面向对象语言,主要强调软件开发 的探索性和原型化开发方法; ? ⑵以C++、Object Pascal为代表的混 合型面向对象语言,主要扩充现有 语言,强调运行时的时空效率;

程序设计的特点
?
?

构造性 :不同的人为解决同一问题编制的程序,其面貌颇不相
同,然而,程序的功效却是等价的。

严谨性:以上下文无关的形式语言实现。无法补充缺损信息、
去掉冗余信息、将暂时不懂的信息暂时搁置起来,待下文或经过 推理予以补充和理解

?

叠加性: 一般是将自己设计的子程序尽量分割成独立的、功能
明确单一的小模块,以便充分利用;甚至还会利用系统内的库函 数。

?

抽象性:把客观事物的描述抽象为数据和算法,并且利用抽象
使得程序能够正确的映射客观事物 。抽象是有层次的 ,不同层次 上的抽象是相互独立和互相作用的 。

计算程序的运行结果
?

一、直接推理

二、由流程图推断算法
三、动态模拟 四、由底向上阅读分析

对于一些语句少、结构简单且可读性较强的程序,不妨 通过分析程序流程,直接寻找其间蕴含的计算模型。
{$n+}

var m,n,I:integer; t:extended; begin

readln(n,m);
t:=1; for i:=1 to m do t:=t*(n-i+1)/i; writeln(t:0:0); end. 输入 10 5 输出:

【分析】由for循环可以看出

t=

n ? i ?1 ? i ,即
i ?1

m

i=1时,t=n; i=2时,t=n*(n-1)/2;

i=3时,t=n* (n-1)/2 * (n-2)/3 ;
……… i=m时,t= c(n,m)=n!/(m!*(n-m)!)

显然,这是求组合数。当输入n=10、m=5时,程序应输出252。
这个算法的效率不错,因为计算与n和m的大小有直接的关系。所以,我们 要设法使运算的中间结果尽可能地小。如果我们先把N~(N-M+1)这M个连 续的自然数乘起来,再依次除以1~M就是一种不太明智的选择。上述程序 先乘N除1,然后乘(N-1)除2,再乘(N-2)除3,……最后乘(N-M+1)除M。因 为连续的K个自然数的积一定能被K!整除,所以在这一过程中不会出现除 不尽的情况。同时也使得中间结果比较小,从而提高了运算速度。告诫读 者的是,对于上述算法来说,n和m不能超过102。如果超过了这个上限,t 就会溢出,尽管它采用了extended类型。

对于一些易读性不十分好的程序,最 好的办法是画流程图。其步骤如下 ⑴跟着程序画流程图,一句一框; ⑵根据上下文的联系合并流程图。 若前几句计算值都要代入后一表达式, 则合并为一框。接连合并几次,使程 序成为一个大功能块; ⑶由大功能块推断算法; ⑷代入输入值,计算结果。

label 10,20,30; var s,p:string; i,k,n,j,m:integer;

30:
writeln(i); end. 输入 asabcdffdin fdi 输出

begin
readln(s); n:=length(s); readln(p); m:=length(p);

i:=0;
10: i:=i+1; j:=i; k:=1;

20: if s[j]<>p[k] then begin if i<n-m+1 then goto 10; end else if k<m then begin j:=j+1; k:=k+1; goto 20;end; i:=0; goto 30;

这个程序的功能是计算s串中与p匹配的子串的首指针。当程序 输入 asabcdffdin fdi

程序应输出8,即s[8]…s[10]=p=‘fdi’。

动态模拟方法是采用人工模仿机器执行程序的方 法计算结果值。首先选择程序中比较重要的变量 作为工作现场。人工执行程序时,只要按照时间 先后一步步记录下现场的变化,就能最后得出程 序的运算结果。其具体布置如下: ⑴画表,画出程序执行时要用的现场情况表; ⑵基本读懂各语句的功能 ⑶走程序,即动态模拟程序。主要根据各语句 的功能,按照程序执行路径的先后顺序逐项填写 现场情况表,直至得出最后结果; 动态模拟方法对简单程序、尤其是循环次数 少的程序是很有效的。但对语句多和计算过程长
的程序,这个方法则由于模拟速度太慢而不实用。

var

i,j:integer;
a:array[1..3,1..3]of integer; begin for i:=1 to 3 do begin for j:=1 to 3 do begin if i=3 then a[i,j]:=a[i-1,a[i-1,j]]+1 else a[i,j]:=j; write(a[i,j]); end;

writeln
end; readln end.

输出:

j

1

2

3

i

1

1

2

3

2

1

2

3

3

2

3

4

显然,最后应输出 123 123 234

var a,d:array[1..100] of integer; n,i,j,k,x,s:integer; begin n:=5;a[1]:=1;d[1]:=1; for i:=1 to n do begin s:=i+1;x:=0; for j:=1 to n+1-i do begin
3 4 2 3 i = 1 S= 2

外循环 d[i+1] 2 a[1]= 2 2 3 4 5 4 4 2 3 k= 2 3 4 5 6 3 4 5 x= 1 2 3 4 5 1 2 3

内循环 a[j+1]= 3 6 10 15 21 5 9 14 输出a[j] 1 3 6 10 15 2 5 9

4
7 7 2 3 4 5 11 11 2

6
4 5 6 5 6 6

4
1 2 3 1 2 1

20
8 13 19 12 18 17

14
4 8 13 7 12 11

k:=s+x;x:=x+1;a[j+1]:=a[j]+k;
write(a[j],' '); end; writeln('...');d[i+1]:=d[i]+i;a[1]:=d[i+1];

5

6

end;
end. 输出:

最后应输出 1 3 6 10 15 ? 2 5 9 14 ? 4 8 13 ? 7 12 ? 11 ?

由底向上分析的阅读分析方法就是在剖析了子程序和模块资 源的基础上,建立对高层程序结构的理解,从而完成整个程 序的阅读分析,即从最底层的子目标开始分析起,看它们做 了哪些事情;然后分析上一层的子目标,看这些子目标在下 一层子目标实现的基础上实现了哪些功能……。经过自底而 上的阅读分析,最后得出计算模型。

const limit = 3000; type tdata=array [0..limit] of longint; var

procedure mult(var a:tdata;b:integer); var i, j:integer; begin for i:=0 to limit do a[i] := a[i] * b; update(a);

Begin read(n); fillchar(num, sizeof(num),0); for i:= 0 to n do begin add(i+1,-1);

ans ,num : tdata;
i,j,n:longint; procedure update(var a:tdata); var

end;

add(n+n-i,1);
end;{for}

procedure add(x, ob:longint); var i:longint;

add(n+1, -1); fillchar(ans,sizeof(ans),0); ans[0] := 1;

int i;
begin for i:=0 to limit-1 do begin inc(a[i+1],a[i] div 10); a[i] := a[i] mod 10; end; end;

begin
for i:=2 to x do while (x mod i =0) do begin inc(num[i], ob);

for i:=2 to limit do
for j:=1 to num[i] do mult(ans,i); for i:=limit downto 0 do if (ans[i] > 0) then begin

x := x div i;
end; end;

for j:=i downto 0 do write(ans[j]);
writeln;break; end;{then} End. 输入 5 输出

update(var a)是将数组a规整为高精度的十进制数组
mult(var a,b)是将高精度的十进制数组a乘以整数b,积存 储在a中。

add(x, ob)计算因子表,ob=1,num←num*x;ob=-1, num←num/x。其中num[i]为因子i的个数
主程序计算catalan数1/(n+1)*c(2*n,n) 。显然n=5,则程 序输出42(1/6*c(10,5))

完善程序
?

填空内容:
? ? ? ? ?

1、变量方面的填空 2、循环方面的填空 3、分支转移方面的填空 4、主程序和子程序关系方面的填空 5、输入输出方面的填空

填空方法:
按照自顶向下的思维方法阅读程序——从主程序开始, 沿控制层次向下阅读。在查到某一个子程序(子模块)时,比 照题目给出的说明和调用它的“父程序(父模块)”,弄清该 子程序(子模块)究竟要达到什么样的子目标,然后查程序, 看它是如何实现这个子目标的。如果该子程序(子模块)有空 格,则按照算法的逻辑进行填空。依次类推,直至最底层的 子程序(子模块)中的空格全部填完为止。

1、完善不含子程序的程序
首先划分各个子模块的层次结构,并确定每个子模块的子 目标。然后自顶向下,根据子目标和上层子模块给出的线索, 对当前层次的各个模块进行填空。依次类推,直至最底层的子 模块中的空格全部填完为止。
?

?

求元素之和最大的子方阵:在m×n(m,n≤20)的正整数数字方阵中, 找出一个p×q的子阵(1≤p≤m,1≤q≤n)使其元素之和最大。例如,下 面5×4的数字阵中,元素之和最大的一个2×3子阵。 5×4数字阵 元素之和最大的2×3子阵为
3 8 4 22 5 21 6

11

1

7

9

5

21

6

2

10

3

8

10

3

8

9

2

7

12

3

var a:array[1..20,1..20] of integer;

for i:=1 to m-p+1 do for j:=1 to n-q+1 do begin ① ;

m,n,p,q,i,j,max,p1,q1,s,i1,j1:integer;
begin for i:=1 to 20 do for j:=1 to 20 do a[i,j]:=0; readln(m,n); for i:=1 to m do

for i1:=i to p+i-1 do for j1:=j to q+j-1 do ② ;

if s>max then begin ③ p1:=i; ;

begin
for j:=1 to n do read(a[i,j]); readln end;
end;

q1:=j
end;

for i:=p1 to



do

readln(p,q);
max:=0;

begin
for j:=q1 to write(a[i,j]:3); writeln ⑤ do

end;
readln end.

模块1(初始化,白色):方阵清零;读方阵规模; 读方阵;读子阵规模;子阵的最大数和初始化
模块2(湖蓝)通过枚举所有可能子阵,求数和最大 的子阵 。其中
子模块1(深蓝):累计(i,j)为左上角的子阵的数和 子模块2(淡绿):调整子阵的最大数和

模块3(红色)——输出最大数和的子阵。

由此得出解 ① s:=0 ② s:=s+a[i1,j1] ③ max:=s ④ p1+p-1 ⑤ q1+q-1

以下程序完成对数组每个元素向后移动n个 单位。数组元素的下标依次为0到m-1,对任 意一个数组元素a[i]而言,它的值移动后将存 储在数组元素a[(i+n) mod m]中。 例如,m=10,n=3,移动前数组中存储的数 据如下前一行所示,则程序运行后数组中存 储的数据如下后一行所示。

0 3 86 20 27 67 31 16 37 42
16 37 42 0 3 86 20 27 67 31

const maxm=10000;

repeat

k:=(k+n) mod m until k<=start;

var i,k,m,n,rest,start,temp:longint;
a:array longint; begin write('input m,n:'); readln(m,n); for i:=0 to m-1 a[i]:=random(100); writeln('before move'); for i:=0 to m-1 do write(a[i]:5); writeln; do [0..maxm] of

if



then

begin temp:=a[k]; repeat a[k]:=a[(m*n+k-n) mod m]; k:=(m*n+k-n) mod m; ③

until k=start;
④ end; ⑤

rest:=m; start:=0;
while begin k:=start; ① do

end;
writeln('after move'); for i:=0 to m-1 do write(a[i]:5); writeln end.

模块1——初始化 模块2——移动计算 ,其中
子模块1:判断以a[k]开始的的循环链上的元素是否都未移 动过 子模块2:若以a[k]开始的的循环链上的元素都未移动过, 则该循环链进行移动

子模块3:寻找下一个未移动过的循环链

模块3——输出移动后的数组 由此得出解为 ① rest>0 或 rest<>0 ② k=start ③ rest:=rest-1

④ a[(k+n) mod m]:=temp 或 a[(start+n) mod m]:=temp
⑤ start:=start+1

完善含子程序结构的程序
?

如果子模块采用过程或函数,则通常以子程 序为单位划分层次结构,这样可以使得其层 次性相对不含子程序的程序来说要清晰一些。
程序的任务是用0?9中的n个数字填入如下乘法运算的*处,数字可重复使用, 且所用的数字至少有一个是素数,要求输出满足下列算式的方案数。
* * * × * *

----------------* * * * * * ----------------* * * *

const p:set of 0..9=[2,3,5,7]; var s:set of 0..9; n:integer; ans:longint; f:text; procedure init; var i:integer;

function ok(x,l:integer):boolean; {此函数判断x是否符合条件}

var t:byte;
begin ok:=false; if exit; _______①________< >l then

inset:=false;
while ______②_______ do begin t:=x mod 10;

if t in p then
begin inset:=true; exit; end; ________③________ end; end;

while x<>0 do begin t:=x mod 10; if not (t in s) then exit; x:=x div 10;

t:byte;
begin readln(n); s:=[];

end; ok:=true; end;

for i:=1 to n do begin read(t); end; close(f); end; s:=s+[t];

function inset(x:integer):boolean; {此函数判断x中是否包含素数字} var t:byte; begin

procedure work; var i,i1,i2,i3,j1,j2:integer; begin then inc(ans); ans:=0; end; for i1:=1 to 9 do end; if i1 in s then if (i1 in p) or (i2 in p) or (i3 in p) or (j1 in p) or (j2 in p) or inset(j1*i) or inset(j2*i)

writeln(ans);
for i2:=1 to 9 do end; if i2 in s then begin for i3:=1 to 9 do init;

if i3 in s then
work; begin end. _________④_________ for j1:=1 to 9 do if (j1 in s) and ok(j1*i,3) then for j2:=1 to 9 do if (j2 in s) and ok(j2*i,3) and _________⑤_________ then begin

模块1——初始化。读入数字个数n和n个整数,并将它们送入集合s(init过程)。
模块2——计算和输出方案数ans(work过程)
在s集合中枚举所有可能的被乘数i1 i2 i3和所有可能的乘数j1 j2,被乘数和乘数必须满足 如下条件 ⑴j1*i的积和j2*i的积分别为3位,(j1 j2)*i的积为4位,且积的每一位数字在集合s中。 在work过程中,通过调用布尔函数ok(x,l)来判别数字x是否满足各位数字在集合s且位 数为l位的条件 ⑵i1、i2、i3、j1、j2、j1*i的各位数、j2*i的各位数中至少有一个为素数。在work过程中, 通过调用布尔函数inset(x)来判别多位数x中是否存在素数字

由此得出解为

①trunc(ln(x)/ln(10))+1
④ i:=i1*100+i2*10+i3

②x>0



x:=x div 10

⑤ ok(j1*i*10+j2*i,4)

菲波拉契数列为1,1,2,3,5,8,13,21,……, 其元素产生的 规则是前两个数为1,第三个数开始每个数等于它前 面两个数之和。已知任意一个正整数可以表示为若 干个互不相同的菲波拉契数之和。
例如:36=21+13+2 下面的程序是由键盘输入一个正整数n,输出组成n 的互不相同的菲波拉契数 ⑴寻找小于等于n的最大菲波拉契数a,并以a作为组 成n的一个数; ⑵若n≠a,则以n-a作为n的新值,重复步骤(1)。若a =n,则结束:

var n:integer;

procedure p(n:integer);

first:boolean;
function find(n:integer):integer; var a,b,c:integer; begin a:=1;b:=1; repeat c:= ① ;

var a:integer;
begin a:=find(n); if first then begin write(a:4); first:=false end else write('+',a:4); if a<n then p end; begin ④ ;

a:=b;b:=c; until b>=n;

if b=n then find:=
else find:= ③ end;



readln(n); first:=true;{设定表达式首项标志}
write(n:5,'='); p(n); writeln; readln

end.

p(n)的功能:计算和输出n对应的表达式。
p(n)的子函数find(n)的功能:寻找小于 等于n的最大菲波拉契数 由此得出解为 ① a+b ② n (或b , c ) ③a ④ (n-a)

1、凸现信息学知识和学科知识整合的趋势。
为了考核学生运用学科知识的能力,激发学生 的创造力,2002年全国奥林匹克信息联赛(NOIP) 2、“构造法” 或贪心策略类试题的引 中学科类的试题增加,并且首次出现了计算几 入,使得算法知识的不确定性和不稳定 何类的试题(矩形覆盖)。这说明信息学与学科的依赖 性增加。这正体现了科学的本质—知识 关系日益凸现,学科基础好、尤其是数学素质 是不断推陈出新的。 好的人虽然不一定会编程,但希望学习编程的 人愈来愈多;编程解题能力强的人势必有数学 的潜质和爱好,他们中愈来愈多的人也希望深 造数学。各门学科的交融和整合是奥林匹克信 息学联赛活动发展的一个大趋势(有专家提议,数学教材

特 点

讲算法,信息科技教材讲语言,上海的信息科技教材出现真值表(初中)和 c语言(高中))。

3、试题的综合性增加,并不一定随知 4、经常面对着不知道算法的试题, 识的分类而发生变化,有时几乎找不 面对着谁都不知如何处置的情境(经 到一个单一的经典算法(字串变换——回溯法中有 常出现许多选手在一题中得0分、优秀选手表现失常的情 字符串处理),也找不到一个纯粹的数据结 况),因此必须使学生正确地理解问 构问题(级数求和——需要为表达式的计算结果设计合适的 题、深入问题的空间并形成解决问 数据类型),关键是你从哪个角度去分析, 题的意识、习惯和能力。能不能创 也就是说能不能综合所学的知识,应 造性地应答没有遇到过的挑战,成 用自如地解决问题。选手的综合素质 为培训的基本要求和目标。 愈高,得胜的机率愈大;

2、 处理好前沿性与基础性、直线培训和

散点培训、循序渐进与跳跃式的矛盾。 如果恪守按部就班的培训程序,不谋求跳跃式 1、培养问题意识和问题能力。创造始 学习,将离全国和国际奥林匹克信息学活动的 于问题。“有了问题才会思考,有了思 前沿、离世界程序设计知识的前沿愈来愈远。 考才有解决问题的方法,才有找到独立 因此在进行基础课程学习的同时,必须有追逐 思路的可能(陶行知)”。有问题虽然 前沿的选择性学习。这里,有时候心理的障碍 不一定有创造,但没有问题一定没有创 比科学上的障碍更难跨越,敢不敢的问题比能 造(想一想当前的解法有没有缺陷,有没有更好的算法,它 不能的问题更突出。其实在学习中或多或少地





与哪些问题有联系,与哪些知识相关联,还可以拓延出哪些 都有必要的跳跃,不少人还能够实现比较大的 问题,要解决这些问题还需要哪些知识) 跳跃( 爱笛生小学三年级退学、比尔.盖茨大学三年级退学)



?学生必须学会从浩如烟海的信息中选择最有 价值的知识,构建个性化(符合自己能力结构 和兴趣结构)和竞争需要的知识结构

3、参与活动的学生应由竞 争关系和独立关系 (你做你的, ?培训内容要有选择性,因为除了出题者,谁
我干我的,程序和算法互相保密,彼此 也说不清楚在未来竞赛中究竟什么知识是必要 津津乐道于对方的失败和自己的成功) 的(对基础的理解是主观的选择。例如中国、美国和俄罗斯的理科教材 大不相同,有的同年级同学科的教材相差三分之二) ,因此不可 (通过研 能把所有重要的东西都选择好了给学生,而是 讨算法、集中编程、互测数据等互相合 应该将直线培训与散点培训相结合,选择部分 作的方式完成学习任务) 重要的东西交给学生,让他们自己去探索若干 知识点之间的联系,补充自己认为需要补充的 知识。

转向合作学习的关系

学生的心理调适: 合作学习的效应:
?我掌握的知识仅不过是沧海一粟(进取心); ?集思广益容易出好的算法;

?固守错误的概念比一无所知更可怕(明智); ?群体设计的测试数据相对全面; 前提条件:水平相当的同质成员

或各有所长(包括数学知识、编 ?三人之行必有我师(谦虚); ?在群体活动中能比较客观的反映自己 程能力和思维方式等解题所需的 能力情况; ?知识生产社会化条件下人的基本素质之一

各种因素)的异质成员是开展合 是合作精神(现在的重大科学发明需要成百 ?每个学生在付出与给予中可提高合作 上千科学家进行长期甚至跨国的合作,例如 作学习的组织基础; 精神和编程能力,成功者往往是那些相 制作windows,人类基因工程)(现代意识); 容性好、 乐于帮助他人,并且善于取 他人之长的学生(符文杰、张一飞等)。

4、选手面对从未遇到过的 挑战应调整好心态, 不要急
功近利,要只管耕耘、不问收获、 潜心钻研、其乐无穷。那怕是一两 次失误,也是砥砺之石,可从中汲 取有益的经验和教训。“不是一番 寒彻骨,哪得梅花扑鼻香”。


与课内知识相关 字符串处理 贪心法 回溯法




字符近似查找 均分纸牌 选数、字串变换



自由落体、级数求和

动态程序设计方法
几何计算

过河卒
矩形覆盖

?
?

?
?

?

这些试题具有下述特点: l 恪守竞赛大纲的要求,题意描述清晰,无二异性。难度区 分与选拔目标紧扣,既与选手的知识基础和接受能力相适应, 又鼓励选手在力所能及的范围内“跳一跳”,探索未知; l 模式化的试题愈来愈少,益智性试题愈来愈多,试题的数 学味愈来愈浓,对选手的智力和数学功底的要求愈来愈高; l 要求选手娴熟基本的数据结构和算法,能够面对不同的问 题情景,独立地设计数据结构、构造算法,展开生动活泼的策 略创造; l 多种算法和多种数据结构的要求有时交织在一题,考察选 手的综合能力。既要求选手有归纳能力,通过求同思维找出试 题中蕴含的规律,设计解析式,更鼓励选手有创造能力,不拘 泥一个模式,能够依据问题线索、数学分析和程序设计知识, 发散求异思维,从不同角度寻求解决问题的各种可能途径。 “创造能力=知识量+发散思维”。这些鼓励“一题多解”的 试题拓宽了选手的思维空间,为发散思维和创造能力的培养注 入了活力。

虽然2002年全国奥林匹克信息学复赛中含许多可 “一题多解” 的试题,但如果按照较优算法标准分 类的话,大致可分为
算法
几何计算(点和矩 形的关系)

分区联赛
矩形覆盖

算法知识分布
字符串处理
回溯法 构造法

字符近似查找

选数、字串变换 级数求和、 均分纸牌、 自由落体

题一 字符近似查找 题二 级数求和 题三 选数
题四 过河卒

题五 均分纸牌
题六 字串变换 题七 自由落体

题八 矩形覆盖

第一题:字符近似查找
设有n个单词的字典表(1≤n≤100)。计算某单词在字典表中的四种匹 配情况(字典表中的单词和待匹配单词的长度上限为255): i:该单词在字典表中的序号;

Ei:在字典表中仅有一个字符不匹配的单词序号;
Fi:在字典表中多或少一个字符(其余字符匹配)的单词序号; N:其他情况

当查找时有多个单词符合条件,仅要求第一个单词的序号即可。
输入文件 输入文件名为a.in,文件的格式如下: n(字典表的单词数) n行,每行一个单词 待匹配单词

输出文件

输出文件名a.out,格式如下:
i Ei Fi 其中i为字典表中符合条件的单词序号(1≤i≤n),若字典表中不存在符合条件的单词, 则对应的i=0。若上述三种情况不存在,则输出N。
输入输出样例 输入1: 5 abcde abc asdfasfd abcd aacd abcd
输出1: 4 E5 F1 输入2: 1

a
b 输出2: 0 E0 F0 N

我们将字典表中的单词分成3类:
第1类:单词与待匹配单词多或少一个字符,其余字符匹配; 第2类:单词仅有一个字符与待匹配单词不匹配;

第3类:单词与待匹配单词完全匹配;
设 const

note :array[1..3] of string=('F','E','');

{匹配情况的标志}

var

want
list

:string;
:array[1..100] of string;
?1 ? ?2 ? ?3 ?0 ?

{待匹配单词}
{字典表。其中list[i]为字典i}
在want中添加或删除一个字符得到list[i ] want与list[i ]有一个字符不同 want与list[i]相同 其他情况

ans :array[1..100] of integer;{单词的类别序列。其中

ans[i]=

}

? ?

?
?

?
? ? ? ?

1、匹配情况的计算 ⑴计算两个等长字串中不同字符的个数 function find(a,b:string):integer;{输入两个 等长字串a,b,计算和返回不同字符的个数} var i,tot:integer; begin tot←0; for i←1 to length(a) do if a[i]<>b[i] then inc(tot); find←tot; end;{ find }

?

?

?

? ? ?

?
? ? ? ? ?

?
?

⑵判别一个字串是否比另一个字串多一个字符(其余字符匹配) 我们不知道长度大1的字串究竟在哪个位置上多出一个字符,无 奈,只能将该字串的每一个字符试插在另一个字串的对应位置上。 如果插入后使得两串相同,则说明猜想成立。否则猜想不成立。 function check(a,b:string):integer;{输入字串a,b。若b能 够在a的基础上添加一个字符得到的话,则返回1;否则返回0} var i:integer; begin check←0; for i←0 to length(a) do a←copy(a,1,i)+b[i+1]+copy(a,i+1,255);{ 在 a[i] 后 插 入 b[i+1]} if a=b {若插入后两串相同,则成功退出} then begin check←1;exit;end;{then} delete(a,i+1,1); {删去a中的插入字符} end;{for} end;{check}

2、计算字典表中的每一类单词

首先,我们依次计算每一个单词的类别序号

? 在单词i与待匹配单词等长的情况下,若两串相同,则单词i的类别记为3; 若两串仅有一个字符不同,则单词i的类别记为2; ? 若单词i比待匹配单词多或少一个字符(其余字符匹配),则单词i的类别 记为1;否则单词i的类别记为0; 然后根据ans序列在字典表中依次搜索类别3‥类别1的单词,输出对应的单词序 号。如果在字典表中不存在上述3种类别的单词,则输出‘N’。

fillchar(ans,sizeof(ans),0);
for i←1 to n do begin

{ 单词的类别序列初始化}
{对字典中的每个单词进行分类}

if length(list[i])=length(want) {若单词i与待匹配单词等长}

then begin
k←find(list[i],want);{计算单词i与待匹配单词的不同字符个数} if k=0 then ans[i] ←3; {记下类别序号}

if k=1 then ans[i] ←2;

第二题:级数求和
已知:Sn=1+1/2+1/3+….+1/n。显然当n.非常大的时候, Sn可大于任何一个整数K。现给出一个整数K (1≤K≤15),要求计算出一个最小的n,使得Sn>K。 输入 键盘输入 k 输出 屏幕输出

n

输入输出样例 输入: 1 输出: 2

算法分析
?

? ? ? ? ? ? ? ? ? ? ?

该题考核选手的并不是编程能力,而是选择变量类型的能力。由于该 数列是递减的,而k的上限为15,因此项数很大,即便是longint也容纳 不下。但未必非高精度运算不可。只要启动浮点数运算({$n+}),将 项数设为extended类型,便可以得出正确解。 {$n+} {启动浮点数运算} var s,b,k:extended;{ 数列的和、项数、最接近sn(大于sn)的整数值} begin s←0; {数列的和初始化} b←0; {项数初始化} readln(k); {读最接近sn(大于sn)的整数值k} while s<=k do {若目前数列的和小于k,则项数b+1,计算sb} begin b←b+1; s←s+1/b; end;{while} 输出项数round(b); end.{main}

第三题:选数
?

已知n个整数 x1,x2,…..xn, 以及一个整数k (k<n)。从 n 个整数中任选k个整数组合相加, 可分别得到一系列的和。例如当 n=4, k=3, 4个整数分别为3,7,12,19 时,可得全部 的组合为: ? 3+7+12=22 3+7+19=29 7+12+19=38 3+12+19=34。 ? 现在,要求你计算出和为素数的组合数有 多少种。例如上例,只有一种组合的和为 素数:(3+7+19=29)。

? ? ? ? ? ?

输入: 输入文件名为c.in。文件格式 n, k(1≤n≤20,k<n) x1,x2,…xn(1≤xi≤5000000)
输出: 输出文件名为c.out。文件格式 一个整数(满足条件的种数)。 输入输出样例: 输入: 4 3 7 12 19 输出: 1

?
? ?

?
? ?

?
?

?
?

1、判别一个数是否为素数
由于整数xi的上限为5000000,k的上限为19,这就使得判别k个整数的和是 否为素数的问题变得似乎有点困难。为了保证在该范围内能正确出解,我 们首先通过筛选法,将1―10000间的素数存入素数表prime。设 var map:array[1..10000] of boolean;{筛} prime:array[1..5000] of longint;素数表。其中第i个素数为prime[i]} list:array[1..20] of longint;{待选数字集合。其中list[i]为xi} tot,ans:longint;{tot为素数表的长度;和为素数的组合的个数为ans} 构造素数表prime的过程如下: tot←0; { 素数表的长度初始化} fillchar(map,sizeof(map),true);{初始时所有数在筛中} for i←2 to 10000 do {顺序搜索筛中的最小数i} if map[i] then begin for j←2 to 10000 div i do map[i*j] ←false; {将i的倍数从 筛中删去} inc(tot);prime[tot] ←i; {i进入素数表} end;{then}

?

?
? ? ?

?
? ? ?

?
? ?

?
?

?

? ? ? ? ? ? ? ? ? ?

我们在素数表prime的基础上判别某数a是否为素数。任何数都可以分 解成素因子的乘积形式。按照递增方向将prime表中的每一个素数去试 除 a。 若 某 个 素 数 能 被 a 整 除 , 则 说 明 a 为 合 数 ; 若 prime[i]*prime[i]>a,则说明a不可能分解出比prime[i]大的素数了, a本身为素数。由于prime[i]表的最大素数接近10000,其平方远大于 xi的上限5000000,因此是一个比较可行的方法: function check(a:longint):boolean; {判断a是否是素数} begin check←true; {素数标志初始化} for i←1 to tot do begin {搜索素数表} if prime[i]*prime[i]>a then exit;{若超出搜索范围的上限, 则说明a是素数,返回true} if a mod prime[i]=0 then begin check←false;exit;end;{then} end;{for} end;{ check }

?

?
? ? ?

?

?
? ?

2、递归搜索方案数 由于数列是随机和无序的,因此只能通过搜索的办法 求解。设 状态(left,now,all):目前组合为all,还需要从 xnow‥xn中选出left个数; 约束条件(left≤n-now+1):xnow‥xn中数的个数大于 等于left; 边界条件( ( left=0) and (now=n+1))和目标状态 (check(all)=true):从x1‥xn中选出k个数为边界。 在这种情况下,若k个数的和为素数,则满足条件的种 数+1。到达边界后,应回溯; 搜索范围为两种选择: 当前组合不选xnow,递归计算子状态(left,now+1,all); 在还有数需要选的情况下(left>0),xnow 选入组合, 递归计算子状态(left-1,now+1,all+list[now]); 由此得出子程序

? ? ? ? ? ? ? ? ? ? ?

?
?

Procedure solve(left,now,all:longint);{递归计算选数情 况} begin if (left>n-now+1) then exit;{ 若xnow‥xn 中不足left个数, 则回溯} if (left=0) and (now=n+1) {若从x1‥xn中选出了k个数} then begin if check(all) then inc(ans);{若k个数的和为素数, 则满足条件的种数+1} exit; {回溯} end;{then} solve(left,now+1,all);{当前组合不选xnow,递归计算子状态} if left>0 {在还有数需要选的情况下,xnow 选入组合,递 归计算子状态} then solve(left-1,now+1,all+list[now]); end;{ solve} 显然,递归调用solve(k,1,0)后得出的ans即为问题的解。

过河卒
? ?

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

同时在棋盘上的任一点有一个对方的马(如上图的C 点),该马所在的点和所有跳跃一步可达的点称为对方 马的控制点。例如上图C点上的马可以控制8个点(图中 的P1,P2….P8)。卒不能通过对方马的控制点。 ? 棋盘用坐标表示,A点(0,0)、B点(n,m)(n,m为 不超过20的整数,并由键盘输入),同样马的位置坐标是 需要给出的(约定:C≠A,同时C≠B)。现在要求你计 算出卒从A 点能够到达B点的路径的条数。 ? 输 入: ? 键盘输入B点的坐标(n,m)以及对方马的坐标(X,Y) 输 出: ? 屏幕输出一个整数(路径的条数)。 输入输出样例: ? 输入:3 3 2 2 ? 输出:0
?

?

?

1、计算对方马的控制点 按照题意,对方的马所在的点和所有跳跃一步可达的点称为对方马的控制点, 卒不能通过对方马的控制点。在卒出发之前,必须计算对方马的所有控制点。 显然,若(0,0)或(n,m)为控制点,则输出路径数为0。设
const move:array[1..8,1..2]ofinteger=((1,-2),(1,2),(2,1),(2,-1),(-1,2),(-1,-2),(-2,1),(2,-1));{ move[k,1..2]为马沿k方向跳跃一步的水平增量和垂直增量} var list:array[-1..20,-1..20] of comp;{路径数序列,其中list[i,j]为卒从(0,0)到(i,j)的路 径数} can:array[0..20,0..20] of boolean; {点(i,j)允许卒通行的标志} 马的初始位置为(x,y)。我们按照下述方式计算can序列: can[x,y] ←false; { 对方马所在的点为控制点} for i←1 to 8 do begin{从(x,y)出发,沿8个跳马方向计算控制点} j←x+move[i,1]; {计算i方向的跳马位置(j,k)} k←y+move[i,2]; if (j>=0) and (k>=0) and (j<=n) and (k<=m) {若(j,k)在界内,则为控制点} then can[j,k] ←false; end;{for} if (not can[0,0])or(not can[n,m]) {若卒的起点和终点为控制点,则输出路径数0} then writeln(0) else begin 计算和输出卒从(0,0)走到(n,m)点的路径数list[n,m]; end;{else}

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

?
? ?

2、 计算和输出卒从(0,0)走到(n,m)点的路径条 数
我们按照由上而下、由左而右的顺序,将卒可能到达的每一个位置(i,j) (0≤i≤n,0≤j≤m)设为阶段,显然这样做,可以取消对状态的枚举。 首先,将卒的出发点(0,0)的路径数设为1(list[0,0]←1),并将该位 置设为控制点(can[0,0] ←fals)。然后从(0,0)出发,按照由上而下、 由左而右的顺序计算卒经过每一个可行点的路径数。若(i,j)为可行点, 则卒可由上侧的(i-1,j)和左侧的(i,j-1)进入该点。将这两点的路径数 加起来,即为从(0,0)走到(i,j )的路径数,即 list[i,j]=list[i-1,j]+list[i,j-1]∣(i,j)非控制点 依次类推,最后得出的list[n,m]即为问题的解。由此得出算法: fillchar(list,sizeof(list),0); {路径数序列初始化} list[0,0]←1;{卒从(0,0)出发的路径数为1,该位置不再允许卒通行} can[0,0] ←false; for i←0 to n do{对于每个可行点,小兵要么从左侧、要么从上方走到,由 此计算从(0,0)到(i,j)的路径数} for j←0 to m do if can[i,j]then list[i,j]←list[i-1,j]+list[i,j1]; 输出卒从(0,0)走到(n,m)点的路径条数list[n,m];

?
? ? ?

?
? ? ?

题一 均分纸牌
[问题描述] 有N堆纸牌,编号分别为1,2,….N。每堆上有若干张, 但纸 牌总数必为N的倍数。可以在任一堆上取若干张纸牌,然后移动。移牌规则 为:在编号为1堆上取的纸牌,只能移到编号为2的堆上;在编号为N的堆上 取的纸牌,只能移到编号为N-1的堆上;其他堆上取的纸牌,可以移到相邻 左边或右边的堆上。现在要求找出一种移动方法,用最少的移动次数使每 堆上纸牌数都一样多。例如N=4,4堆纸牌数分别为: ① 9 ② 8 ③ 17 ④ 6

移动3次可达到目的:从③取4张牌放到④(9 8 13 10)→从③取3张牌放 到②(9 11 10 10)→从②取1张牌放到①(10 10 10 10)。 [ 输 入 ]: N ( N 堆纸牌,1≤N≤100)

A1,A2,….An (N 堆纸牌,每堆纸牌初始数,1≤Ai≤10000)
[ 输 出 ]:所有堆均达到相等时的最少移动次数。 [输入输出样例]

输入: 4 9 8 17 6

输出: 3

设list为纸牌序列,其中list[i]为第i堆纸牌的张数(1≤i≤n), ? list[i] ave为均分后每堆纸牌的张数,即 ;ans为最少移动次 n 数。
n i ?1

我们按照由左而右的顺序移动纸牌。若第i堆纸牌的张数list[i] 超出平均值,则移动一次(ans+1),将超出部分留给下一堆,既 第i+1堆纸牌的张数增加list[i]-ave;若第i堆纸牌的张数list[i]少 于平均值,则移动一次(ans+1),由下一堆补充不足部分,既第 i+1堆纸牌的张数减少ave-list[i];

右邻堆取的牌

问题是,在从第i+1堆中取出纸牌补充第i堆的过程中,可能会 出现第i+1堆的纸牌数小于零(list[i+1]-(ave-list[i])<0 )的情况, 这时可以理解为一个“先出后进”的栈。由于纸牌的总数是n 的倍数,因此后面的堆会补充第i+1堆ave-list[i]-list[i+1]+ ave 张纸牌,使其达到均分的要求。
第二堆补充第一堆

第三堆补充第二堆

第四堆补充第三堆

在枚举分牌方案时,是否可以 利用上述计数方法呢?

题二 字串变换
[问题描述]:已知有两个字串A$,B$及一组字串变换的规则: A1$→B1$

A2$→B2$
……… 规则的含义为:在A$中的子串A1$可以变换为B1$、A2$可以变换为B2$…..。 例如: A$ =‘abcd’ B$=‘xyz’ 变换规则为: ‘abc’→‘xu’ ‘ud’→‘y’ ‘y’→‘yz’ 则此时,A$可以经过一系列的变换变为B$,其变换的过程为: ‘abcd’→‘xud’→‘xy’→‘xyz’ 共进行了三次变换,使得A$变换为B$。

[输入]:输入文件名为A.in。文件格式如下:

A$,B$
A1$ → B1$ A2$ → B2$ 变换规则

………
所有字符串长度的上限为255。 [输 出]:输出文件名为A.out。若在30步(包含30步)以内能将A$变换为 B$,则向A.out输出最少的变换步数;否则向A.out输出‘ERROR!’。 [输入输出样例] A.in文件: abcd,xyz abc->xu ud->y A.out文件:

3

y->yz

1、分析变换规则

规则序列为rule,其中第i条规则为rule[i,1]→rule[i,2]; 当前串为now,其中tmp为now的一个待匹配子串。由于匹配过程的由左而 右进行的,因此设j为now的指针,即从now的第j个字符开始匹配rule[i,1]。 now适用第i条规则的条件是 ?now中的子串被第i条规则替换后的长度小于255,即 length(now)+length(rule[i,2])-length(rule[i,1])≤255

?rule[i,1]是now的一个子串(k=pos(rule[i,1],tmp)≠0)
在使用了第i条规则后,now变换为 now= copy(now,1,j+k-1)+rule[i,2]+copy(now,j+k+length(rule[i,1]),255) 由于now中可能有多个子串被第i条规则替换,因此每替换一次后,为了方便地 找出下一个替换位置,我们将当前被替换串前(包括被替换串)的子串删除。

2、使用回溯法计算最少替换次数
由于原串a、目标串b和规则rule是随机输入的,因此不可能找出 直接计算最少替换次数best的数学规律,只能采用回溯搜索的办 法。设 ? 状态(need,now):替换次数为need,替换结果为now; ? 边界条件(need≥best)和目标状态(now=b):替换次数达 到或超过目前得出的最小值为边界;已经替换出目标串为目标 状态; ? 搜索范围i:尝试每一条规则,即1≤i≤规则数n;

?约束条件(length(now)+length(rule[i,2])-length(rule[i,1])≤255): now中的子串被第i条规则替换后的长度小于255;
由此得出计算过程:

procedure solve(need;now);{从当前串now出发,递归第need 次替换} var i,k,j:integer; tmp:string; begin

if need>=best then exit;
best←need; exit; end;{then} for i←1 to n do

{若到达边界,则回溯}

if now=b then begin{若达到目标状态,则记下替换次数,并回溯}

{搜索每一条规则}

if length(now)+length(rule[i,2])-length(rule[i,1])<=255

then begin

{若使用了第i条规则后,串长不会超过上限}

j←0; tmp←now;{匹配指针初始化和待匹配子串初始化} k←pos(rule[i,1],tmp); {尝试第i条规则}

while k>0 do
begin

{反复在tmp 中寻找子串rule[i,1]}

solve(need+1,copy(now,1,j+k-1)+rule[i,2]+copy(now, j+k+length(rule[i,1]),255)); {递归下一次替换} delete(tmp,1,k);{将当前被替换串前(包括被替换串)的子串删除} j←j+k; {右移匹配指针}

k←pos(rule[i,1],tmp);
end;{while} end;{then}

{继续尝试第i条规则}

end;{ solve }

由此得出主程序: 读入初始串a和目标串;

读入替换规则rule;
best←31; solve(0,a); if best<=30 then writeln(best) {设定替换次数的上限} {回溯搜索最少的替换次数} {输出最少替换次数}

else writeln('ERROR!');


题三 自由落体
[问题描述]: 在高为H 的天花板上有n个小球,体积不计,位置分别为0,1, 2,…n-1。在地面上有一个小车(长为L,高为K,距原点距离为S1)。已知小 球下落距离计算公式为 S=1/2*g*t2,其中 g=10, t为下落时间。地面上的小 车以速度 V 前进。如下图:

小车与所有小球同时开始运动,当小球距小车的距离≤0.00001时,即认为 小球被小车接受(小球落到地面后不能被接受)。请你计算出小车能接受到 多少个小球。
[输入]:H,S1,v,L,k,n (1≤H,S1,v,L,k,n≤100000) [输出]:小车能接受到的小球个数。

这是分区联赛最容易失 误的一道试题,关键是 弄清小车行程的物理意 义和计算的精度误差!

为什么在n1的公式中加上L?为什么 算法分析 由题意可知,车顶与天花板的距离为h-k,小球由天花板落至车顶 在n2的公式中加上0.5?为什么n1取 所花费的时间为t1= ,由天花板落至地面的时间为t2= 。 小车与所有小球同时开始运动,当小球距小车的距离≤0.00001时, 下整、n2取上整?
2 * (h ? k ) 10 2*h 10

即认为小球被小车接受(小球落到地面后不能被接受)。 小车在行驶了t1*v-0.00001路程后 接受了第一个小球,其编号为 n1=min{n-1, ?s ? t1* v ? l ? 0.00001 } ? 小车在行驶了t2*v+0.00001路程后 小球落地,小车接受最后一个小球 的编号为n2=max{0, }。
?s ? t 2 * v ? 0.00001? 0.5?

显然,若n1≥n2,则小车接受的小球数为n1-n2+1;否则小车未接受 任何一个小球。

矩形覆盖
[问题描述]:在平面上有n个点 (n≤100),每个点用一对整数坐标表示。例 如:当n=4 时,4 个点的坐标分别为: p1(1,1), p2(2,2), p3 (6,3), p4(7,0)

本试题是高中组复赛中最难 的一道试题,对选手的几何 基础和编程能力是一个比较 这些点可以用 k 个矩形( k<4) 全部覆盖,矩形的边平行于坐标轴。如图 严峻的考验。 一,当 k=2时,可用如图二的两个矩形s1,s2覆盖, s1,s2面积和为4。问
题是当 n个点坐标和 k 给出后,怎样才能使得覆盖所有点的k个矩形的面积 之和为最小呢。约定: ? 覆盖一个点的矩形面积为0;

?覆盖平行于坐标轴直线上点的矩形面积也为0;
?各个矩形间必须完全分开(边线也不能重合);

算法分析
1、点和矩形的描述和关系
平面上的点由坐标(x,y)表示。由于计算过程是按照由下而上、由左而右进 行的,因此我们按照x坐标递增的顺序和y坐标递增的顺序将n个点存入a序列。

矩形由2条平行于x轴的边界线和2条平行于y轴的边界线围成。为了计算最 小矩形的方便,我们将空矩形的左边界设为∞、右边界为设-∞、下边界设 为∞、上边界设为-∞。

2、计算覆盖所有点的一个最小矩形 设目前最小矩形的四条边界为maxx,maxy,minx,miny。如 何按照面积最小的要求将a点加入矩形呢?显然需要调整边界 线,使a点位于对应的边界线上。

初始时,我们设最小矩形为空,即左边界left为∞、右边界right为∞、下边界top为∞、上边界bottom为-∞。然后由左而右,依次往矩 形放入n个点,调整对应的边界线。最后得出的矩形为最小矩形, 其面积为(右边界-左边界)*(上边界-下边界)

3、计算覆盖所有点的两个面积和最小的独立矩形
我们称彼此完全分开的矩形是独立的。两个覆盖所有点 的独立矩形有两种形态:
Tac[1,j-1] Tdc[2,j] Tdc[1,j]

Tac[2,j-1]

我们将覆盖x轴左方点集a[1,1..j]的最小独立矩形存入tac[1,j];将 覆盖x轴右方点集a[1,j..n]的最小独立矩形存入tdc[1,j];将覆盖y轴 下方点集a[2,1..j]的最小独立矩形存入tac[2,j];将覆盖y轴上方点集 a[2,j..n]的最小独立矩形存入tdc[2,j](注意:当k=3时,对应的点集 不包括被矩形1覆盖的点(1≤j ≤n )。

为什么一定要考虑两个轴向, 如果仅考虑一个轴向的话, 有什么反例?

问题是面积和最小的两个独立矩形究竟取哪一个形态,区分两个矩形的分界 线j为何值,我们无法确定。不得已,只能将所有可能的情况枚举出来。设 var best,now:longint;{两个独立矩形的最小面积和、当前方案中两个独立矩形 的面积和} 枚举过程如下: 计算tac和tdc序列; best←maxlongint; for i←1 to 2 do begin {最小矩形面积初始化} {依次分析x轴向和y轴向}

k=3时顺序寻找i轴向上第一个未被矩形1覆盖的点j; while j≤n do{枚举i轴向上所有可能的两个独立矩形,从中找出最佳方案} begin 记下i轴向上点j的坐标h;

顺序寻找i轴向上最接近h点(k=3时,该点未被矩形1覆盖)的点j;

if 点j存在并且k=2,或者k=3时以点j为分界线的左矩形和右矩形与矩形1没 有交集
then begin now←(tac[i,j-1,1]-tac[i,j-1,3])*(tac[i,j-1,2]-tac[i,j-1, 4])+(tdc[i,j,1]-tdc[i,j,3])*(tdc[i,j,2]-tdc[i,j,4]);{则计算两个独立 矩形的面积和} if now<best then best←now; end;{then} end;{while} end;{for} if best=maxlongint then返回失败标志-1 else返回两个矩形的最小面积和best; {若找不到的两个独立矩形} {若面积和为目前最小,则记下}

end;{getans}

4、计算覆盖所有点的三个面积和最小的独立矩形
我们先枚举第一个矩形,该矩形覆盖x轴向上的点1、点i、点j、点h (1≤i≤n, i≤j≤n, j≤h≤n),求出覆盖它们的最小矩形。该矩形的上边界、下边 界、左边界和右边界分别记为bottom、top、left、right。显然其面积为 (bottom-top)*(right-left)。我们将该矩形称为矩形1。那么,平面上还有哪些 点未在矩形1内,这些点将被另外两个独立的矩形所覆盖。 ?判断(x,y)是否在矩形1内的条件

(x≥left) and (x≤right) and (y≤bottom) and (y≥top)
?判断矩形是否与矩形1相交的条件

(min(x1,right) ≥max(x2,left)) and (min(y1,bottom) ≥max(y2,top))

我们在得出矩形1的基础上,直接调用上述算法计算与矩形1分开的另外两个独立 矩形的面积和,加上矩形1的面积便是三个独立矩形的面积和。问题是矩形1究竟 覆盖了哪些点才能得出最优解呢?我们无法得知。无奈之下,只能通过枚举法搜 索所有的可能情况 for i←1 to n do {枚举x轴向上三个点(点i、点j、点h)的所有可能组合} for j←i to n do for h←j to n do begin 计算覆盖点 1、点i、点j、点h的最小矩形 (矩形1)的四条边界right、 bottom、left、top; now←(bottom-top)*(right-left); 计算未被矩形1覆盖的点集u; 计算覆盖u且与矩形1不相交的两个独立矩形的最小面积和g; if (g≥0) and (g+now<best) then best←g+now;{若三个独立矩形的面积和为目 前最小,则记下} {计算矩形1的面积}

end;{for}
输出最小面积和best;

由此得出主程序: 读点数n和矩形数k; 读平面上的n个点; 分别沿x轴和y轴对n个点进行排序; case k of 1: 计算和输出覆盖所有点的一个最小矩形面积; 2: 计算和输出覆盖所有点的两个最小独立矩形的面积和;

3: 计算和输出覆盖所有点的三个最小独立矩形的面积和;
end;{case}

如果k≥4,则算 法将如何修改?

改善高精度运算的效率
用一个整型数组来表示一个很大的数,数组中的每 一个数表示一位十进制数字。这种方法的缺点是,如 果十进制数的位数很多,则对应数组的长度会很长, 并增加了高精度计算的时间。改善高精度运算效率的 两种方法 ⑴扩大进制数 ⑵建立因子表

一、扩大进制数
用一个Longint记录4位数字是最佳的方案。那么这个数组就相当于一个10000进制的 数,其中每一个元素都是10000进制下的一位数。 1、数据类型 type numtype=array[0..9999] of longint; {整数数组类型,可存储40000位十进制数} var a,n: numtype; {a和n为10000进制的整数数组} st:string; {数串} la,ln integer; {整数数组a和n的长度}

2、整数数组的建立和输出
当输入数串st后,我们从左而右扫描数串st,以四个数码为一组, 将之对应的10000进制数存入n数组中。具体方法如下: readln(st); {输入数串st} k←length(st); {取得数串st的长度} for i←0 to k-1 do begin {把st对应的整数保存到数组n中} j←(k-i+3) div 4-1; n[j]←n[j]*10+ord(st[i+1])-48; end;{for} ln←(k+3) div 4; 当得出最后结果a后,必须按照由次高位(a[la-2])到最底位(a[0]) 的顺序,将每一位元素由10000进制数转换成10进制数,即必须保证 每个元素对应四位10进制数。例如a[i]=0015(0≤i≤la-2),对应的10进制 数不能为15,否则会导致错误结果。我们按照如下方法输出a对应的 10进制数: write(a[la-1]); {输出结果} for i←la-2 downto 0 do write(a[i] div 1000,(a[i]div 100)mod 10,(a[i]div 10)mod 10, a[i]mod 10);

3、介绍几个基本运算
⑴整数数组-1(n←n-1,n为整数数组)
我们从n[0]出发往左扫描,寻找第一个非零的元素(n[j]≠0,n[j-1]=n[j2]=…=n[0]=0)。由于该位接受了底位的借位,因此减1,其后缀全为 9 9 9 9 ( n[j]= n[j]-1,n[j-1]=n[j-2]=…=n[0]=9999)。 如 果 最 高 位 为 0 (n[ln]=0),则n的长度减1。 j←0; {从n[0]出发往左扫描,寻找第一个非零的元素} while (n[j]=0) do inc(j); dec(n[j]); {由于该位接受了底位的借位,因此减1} for k←=0 to j-1 do n[k]←9999; {其后缀全为9999} if ((j=ln-1)and(n[j]=0)) then dec(ln); {如果最高位为0,则n的长度减1}

⑵整数数组除以整数(a←a/i,a为整 数数组,i为整数)
我们按照由高位到底位的顺序,逐位相除。在除到第j位时,该 位在接受了来自j+1位的余数(a[j]←a[j]+(j+1位相除的余数)*10000) 后与i相除。如果最高位为0(n[ln]=0),则n的长度减1。 l←0; {余数初始化} for j←la-1 downto 0 do begin{按照由高位到底位的顺序,逐位相除} inc(a[j],l*10000); {接受了来自第j+1位的余数} l←a[j] mod i; {计算第j位的余数} a[j] ←a[j] div i; {计算商的第j位} end;{for} while (a[la-1]=0) do dec(la); {计算商的有效位数}

⑶两个整数数组相乘(a←a*n, a和n为为整数数 组)
我们按照由高位到底位的顺序,将a数组的每一个元素与n相乘。当计算到a[j]*n时, 根据乘法规则,a[j-1], …,a[0]不变,a[j]为a[j]为a[j]与n[0]的乘积,a[j+k]加上 a[j]*n[k]的乘积(k=ln-1,ln-2, …,1),然后按照由底位到高位的顺序处理进位。 最后,如果a[la-1]*n有进位,则乘积a的有效位数为la+ln;否则a的有效位数为la+ln-1。 for j←la-1 downto 0 do begin {a←a*n} for k←ln-1 downto 1 do inc(a[j+k],a[j]*n[k]); a[j] ←a[j]*n[0]; end;{for} l←0; {进位初始化} for j←0 to la+ln-1 do begin {按照由底位到高位的顺序处理进位} inc(l,a[j]); {计算经过进位后的第j位} a[j] ←l mod 10000; {将第j位规整为10000进制数} l←l div 10000; {计算进位} end;{for} if (a[la+ln-1]<>0) {修改有效位数} then inc(la,ln) else inc(la,ln-1);

二、建立因子表
?

? ? ?
?

任何自然数都可以表示为n=p1k1*p2k2*……*ptkt 的形式,p1, p2,……,pt为质因子。设num数组为自然数n,其中num[i]为 因 子 i 的 次 幂 数 ( 1 ≤ i≤k)。 显 然 , num[k], num[k-1]……, num[2]构成了一个自然数,该自然数可以用十进制整数数组 ans存储。ans的计算过程如下 ans[0] ← 1; {将num转换为ans} for i←2 to k do {枚举每一个因子} for j←1 to num[i] do multiply (ans,i);{连乘num[i]个因子i}
multiply的过程为高精度十进制运算中的乘法运算(ans ans*I)

?

有了自然数n的因子表num,可以十分方便地进行乘法或除 法运算。例如整数x含有k个因子i,经过乘法或除法后, num[i]=

我们按照上述方法依次处理x的每一个因子,得出的num即为积或商 procedure add(x, ob:longint);{ob=1,num←num*x;ob=-1,num←num/x} var i:longint; Begin for i←2 to x do {搜索x的每一个因子i} while (x mod i =0) do {计算x含因子i的个数k。num[i]= } begin inc(num[i], ob);x ← x div i; end;{while} end;{add} 显然,如果n1=x1*x2*…*xk,则可以通过连续调用 add(x1,1);add(x2,1);…;add(xk,1); 得出n1对应的因子表num。如果n2=1/(x1,x2…xk),则可以通过连续调用 add(x1,-1);add(x2,-1);…;add(xk,-1); 得出n2对应的因子表num。注意,初始时num数组清零。

对一些不能套用简单的条条框框和现成模式、需要独立思考、 见解独创和有所创新的非标准题,通过构造数学模型解决问 题。数学模型的功能: ⑴解释功能:就是用数学模型说明事物发生的原因; ⑵判断功能:用数学模型判断原来的知识和认识的可靠性。 ⑶预见功能:利用数学模型揭示事物的发展规律,为人们的行 为提供指导或参考。 构造法解题的思路或步骤可以归纳为:

构造法解题的类型
⑴数学建模:通过沿用经典的数学思想建立起模型;或者提取 现实世界中的有效信息,用简明的方式表达其规律,这种规律 可以是一条代数公式、一幅几何图形,一个物理原理、一个化 学方程式,等等。 ⑵直接构造问题解答:只是构造法运用的一种简单类型。它只 能针对问题本身,探索其独有性质,不具备可推广性。 通常考虑的因素 ⑴选择的模型必须尽量多地体现问题的本质特征。但这并不意 味着模型越复杂越好,累赘的信息会影响算法的效率。⑵模型 的建立不是一个一蹴而就的过程,而是要经过反复地检验、修 改,在实践中不断完善。⑶数学模型通常有严格的格式,但程 序编写形式可不拘一格。

在建模过程中经常使用的策略有 ⑴对应策略:将问题a对应另一个便于思考或有求解方法的问题b,化繁为简,
变未知为已知。

⑵分治策略:将问题的规模逐渐减少,可明显降低解决问题复杂程度。算法设
计的这种策略称之为分治策略,即对问题分而治之。 ⑴递推的分治策略 ⑵递归的分治策略

⑶归纳策略:归纳策略则是通过列举试题本身的特殊情况,经过深入分析,最
后概括出事物内在的一般规律,并得到一种高度抽象的解题模型。 ⑴递推式 ⑵递归式 ⑶制定目标 ⑷贪心方案

⑷模拟策略:模拟某个过程,通过改变数学模型的各种参数,进而观
察变更这些参数所引起过程状态的变化,由此展开算法设计。模拟题没有 固定的模式,一般形式有两种: ⑴随机模拟:题目给定或者隐含某一概率。设计者利用随机函数和取整函 数设定某一范围的随机值,将符合概率的随机值作为参数。然后根据这一 模拟的数学模型展开算法设计。由于解题过程借助了计算机的伪随机数发 生数,其随机的意义要比实际问题中真实的随机变量稍差一些,因此模拟 效果有不确定的因素; ⑵过程模拟:题目不给出概率,要求编程者按照题意设计数学模型的各种 参数,观察变更这些参数所引起过程状态的变化,由此展开算法设计。模 拟效果完全取决于过程模拟的真实性和算法的正确性,不含任何不确定因 素。由于过程模拟的结果无二义性,因此竞赛大都采用过程模拟。 模拟的解题方法一般有三种类型 ⑴直叙式模拟 ⑵筛选法模拟 ⑶构造法模拟

一般方法: ⑴机理分析法 ⑵统计分析法

1、机理分析法
根据客观事物的特性,分析其内部的机理,弄清关系,在适当 抽象的条件下,得到可以描述事物属性的数学工具。

我们在联赛中可以用这种方法建立数学模型,然后根据所对应 的算法求出解。如下图所示:

空中都市
在一个未来的空中都市中,有很多个小岛(城区)。现在要求在这些岛之间架一些桥梁 (桥是架在两个岛之间的)。要求,首先,如果A与B之间有桥,B与C之间有桥,则A与 C之间就不能再架桥了。即对于城市中的任意三个岛,不能在其中两两都架上桥。在这 样的前提下,要求架的桥数最多(不考虑具体的空间结构问题),并计算其中的一个可 行方案。 输入文件只包含一行,该行为一个非负整数n(0≤n≤1000),即城市中有n个小岛。 输出文件 桥数的最大值k

以下为k行,每行为一座桥相邻的两个小岛序号(a,b)
输入示例: 6 输出示例:

9
(1,2) (2,3) (3,4) (4,5)

(5,6) (6,1) (1,4) (2,5) (3,6)

按照题意,如果小岛A与小岛B之间、小岛B与小岛C之间和小岛A 与小岛C之间都有桥的话,则说明A、B、C三个小岛之间存在传递 性。试题要求构造一个含n个顶点且满足下述条件的图
①任三个顶点间不含传递性

②图中所含边数最多。
我们通过下述方法将空中都市问题对应一个简单问题: 把n个小岛分为尽量平均的两部分,第一组为(或)个顶点,第二组 为(或)个顶点。然后第一组的每一个顶点分别向第二组的所有顶 点引出边。

下面,我们来证明这个构造方法的正确性。

由于两组的任一对顶点之间都有边相连,因此如果再架桥的话,只能在同 组的一对顶点之间进行。如果在某一组的顶点i和顶点j间架桥,则由于顶点 i和顶点j与另一组的任一个顶点k相连,使得顶点i、顶点j和顶点k之间存在 传递关系,这是不允许的。而一个数拆分成两个数的积,两个数的值愈接 近,积愈大。由此可见,按照上述方法得出的图所含边数最多。下面给出 解法:
Readln(n); k←ord(odd(n)); if k=1 then writeln((n-1)*(n+1)div 4) else writeln((n*n) div 4); for i←1 to (n-k)div 2 do for j←(n-k)div 2+1 to n do {枚举第一组的每一个小岛} {枚举第二组的每一个小岛} {n为偶数时,k=0;n为奇数时,k=1} {输出桥数的最大值}

writeln(‘(‘,i,’,’,j,’)’);

{输出架桥方案}

国际象棋(knight)
国际象棋是我们休息娱乐时所常玩的游戏。在各个棋子中,马的行进方式最为特 殊,也为人们所津津乐道。我们都知道:马走的是“日”字,也就是说每次都是向 水平或竖直方向移动1格,而向另一个方向移动2格,所以也可称作是1*2的马(走法 如下图所示)。在图中我们看到一个马由8种跳的方向。 小明是一个数学爱好者,他将马的走法重新定义了一下,重新定义后的广义马成为n*m 的马。为了研究广义马,小明让马从(0,0)出发,随意的在一张足够大的棋盘上 跳。他发现,有时候广义马总是无法跳入某些格子中,比如从2*2的马永远不可能跳 到(1,1),这令他非常感兴趣。他希望知道对于给定的n,m,n*m的广义马是否能 够跳到所有的格子。由于n,m可以非常大,这令小明花了许多功夫在尝试上,但仍 不能得出肯定的结论。于是他就来找你这个计算机专家了帮忙。

【输入】 在输入文件knIGHT.In中包含了多组测试数据,每个测试数据占一行。 每组测试数据由2个数n,m(1≤n,m≤108)组成,表示广义马的类型。文件最后一行 由2个0表示文件结束。 【输出】 将答案输出到文件knIGHT.OUT中,每组测试数据占一行。如果马能跳到指定的位置输出 YES,否则输出ImPOSSIbLE。

从最简单的1*n的广义马开始分析
⑴当n为奇数时,将棋盘染色成黑 白相间。自(0,0)出发的马始终在 白格子上跳跃,黑色的格子是马永远 到不了的。

⑵当n为偶数时,我们有这样的移动方 案( 如 上 图( b) 所 示), 使得马从 (0,0)开始经过一系列的跳步后, 到(1,0)的位置,也就是说可是让 马到达相邻的格子,所以马可以遍历 整个棋盘。

将n*m的广义马对应1*n的广义马
第1种情况:若n,m有最大公约数p(p>1),则马只能跳到形似(p*s,p*t)的 格子上,其他的格子都到达到不了。 第2种情况:若n+m是偶数,类似于1*n马的情况,马只能在同色的格子内跳动, 不能遍历棋盘。 第3种情况:若n+m为奇数且n,m互质。不妨设n为奇数,那么m为偶数。因为1*n马 的问题已经被彻底解决,所以很自然的想将n*m经过一系列变换转化成1*n马的问题。 我们可以看到马的跳法本质上是4种(另4种可以看成是以下4种跳法反跳一步): ①(m,n) ②(m,-n) ③(n,m) ④(n,-m) 马经过跳p次①、q次②、r次③、s次④后 水平方向的位移为(p+q)*m+(r+s)*n 竖直方向的位移为(p-q)*n+(r-s)*m 为了利用1*n马的结论,解不定方程(p+q)*m+(r+s)*n=1。 ∵n,m互质。∴该方程一定有解(p0,q0,r0,s0)。 又∵m是偶数n是奇数。∴(p0+q0)是偶数,(r0+s0)是奇数。 ∵(p0+q0)与(p0-q0)同奇偶,而(r0+s0)与(r0-s0)同奇偶。 ∴(p0-q0)是偶数,(r0-s0)是奇数。 ∴(p0-q0)*n+(r0-s0)*m是偶数。 也就是马通过一系列的跳动所得到的效果相当于1*len的马跳一步的效果(len=(p0-q0) *n+(r0-s0)*m)。根据前面的结论,1*len的马可以遍历整个棋盘,所以当n+m为奇 数且n,m互质时,n*m的马可以遍历整个棋盘。算法的时间复杂度为W(1),空间需求 为W(1)。

var

n,m,temp:longint;{ n,m 为 广 义 马 的 类型}
function gcd(a,b:longint):longint; {计算n和m的最大公约数}

if n<m then begin {由于gcd(n, m)要求n>m,若不满足,则交换n,m} temp←n;n←m; m←temp; end;{then} if gcd(n,m)=1{若n,m互质,则输出 成功信息;否则输出失败信息} then writeln('YES')

begin
if b=0 then gcd←a else gcd←gcd(b,a mod b);

end;{ gcd }
begin readln(n,m); if(n+m)mod2=0 {读广义马的类型} {若n+m偶数,则无解}

else writeln('ImPOSSIbLE');
end;{else} end.{main}

then writeln('ImPOSSIbLE') else begin

X数列的和(Sum of X-Sequence)
Dr. Steven最近在研究一种叫作X数列的整数数列。X数列有两个独特的 性质:它的首项是0,任意相邻两项的差是1或者-1。 Dr. Steven正在研究X数列的长度与它的各项之和之间的关系。你是他的 一名学生,也参加了这个课题。为了研究的方便,他希望你能够编一个 程序:从输入文件中读入X数列的长度、X数列中所有项的和,找一个满 足要求的X数列,并把结果写到输出文件中。 输入: 输入文件Sum.in的第一行是一个整数n(1≤n≤10 000),表示X数列中的 项数。第二行是一个整数S(|S| ≤ 50 000 000),表示X数列中所有项 的和。

输出:
把找到的满足要求的X数列输出到文件Sum.out中,每一项占一行, 第k项输出在第k行,共n行。如果不存在这样的X数列,则输出“nO”。

长度为n的X数列共有2n-1个,要全部枚举一遍是不现实的。所以,一定有更好的方 法。这就需要我们对题目作进一步的研究。只要做适当的变换,其中的奥秘就会浮 出水面。

我们假设存在这样的一个数列{ai}满足题目要求,讨论S应满足的条件。
令 bi=ai+1-ai, 则 由 题 目 知 , bi=1 或 - 1 。 且 a1=0,a2=b1,a3=b1+b2,……, an=b1+b2+……+bn-1。 所 以 S=a1+a2+…+an=0+b1+(b1+b2)+…+(b1+b2+…+bn-1)=(n1)b1+(n-2)b2+…+2*bn-2+bn-1 (1)

易知|S|?(n-1)+(n-2)+……+1=(n-1)*n/2。1+2+……+(n-1)=(n-1)*n/2 (2)
由(2)式-(1)式得:(n-1)*n/2-S=(n-1)*(1- b1)+(n-2)*(1- b2)+……+2*(1- bn2)+(1- bn-1) 因为1-bk=0或2,所以上式右端为偶数。要使等式成立,则其左端也为偶数,即S与 (n-1)*n/2同奇偶。 再把等式两边同除以2,令ci=(1-bi)/2(易知ci=0或1),得[(n-1)*n/2-S]/2=(n-1) c1+(n-2) c2+……+ 2*cn-2+ cn-1 令T=[(n-1)*n/2-S]/2 所以原问题转化为一个简单的数学问题 :T能否表示成1,2,??,(n-1)中

若干个不重复的数之和。

这个问题不难解决。当0?T?(n-1)*n/2时,T能够表示成1,2,……,(n-1)中若干个不重复的 数之和。问题转化的必要性是显然的。接着用数学归纳法来证明它的充分性。证: (1)当n=1时,0?T?0,0=0。 当n=2时,0?T?1,0=0,1=1。 当n=3时,0?T?3,0=0,1=1,2=2,3=1+2。

均成立。
(2)当n=k(k?3)时,归纳假设成立。则当n=k+1时: ①若0?T<k,则易知k≤(k-1)*k/2。由归纳假设T可以表示成1,2,……,(k-1)中若干个不重复 的数之和。此时c1= 0。

②若k?T?k*(k+1)/2,则先取出一个k,易知k*(k+1)/2 - k=(k-1)*k/2。归纳假设T-k可以表示 成1,2,……,(k-1)中若干个不重复的数之和。此时c1= 1。
由此可证,对于满足0?T?k*(k+1)/2的T,一定能够表示成1,2,……,k中若干个不重复的数之 和。即n=k+1时,归纳假设亦成立。证毕。

由上面的分析证明过程可以得出,T的取值范围是[0, (n-1)*n/2],且T为整数。S的取值范围 是[-(n-1)*n/2, (n-1)*n/2],且S为整数,S与(n-1)*n/2同奇偶。有了这个基础,我们便可以 将原问题对应一个简单问题: 首先判断S是否在[-(n-1)*n/2, (n-1)*n/2]的范围内,且S是否与(n-1)*n/2同奇偶。如果这两 个条件不成立,则所求的数列不存在。如果满足这两个条件,则令T=[(n-1)*n/2-S]/2,然后就 按照上文中证明里的方法求ci,而ai=ai-1+bi-1= ai-1+1-2*ci-1,所以ai 的值也就迎刃而解了

var

a,i,n,s,t:longint;{n为数列的项 数;s为各项的和;a为数列中的一项}
begin readln(n);{输入x数列的项数和所有项 的和} readln(s); t←n*(n-1) div 2;

for i←n-1 downto 1 do begin {逐项计算} if t>=i {c=1,即aj=aj-1-1} then begin dec(t,i);dec(a) end{then} else inc(a);{c=0,即aj=aj-1+1} writeln(a) {输出数列中的一项} end;{for} end;{else} end.{main}

if odd(s-t) or(abs(s)>t){ 判断S是否 在[-(n-1)*n/2, (n-1)*n/2]的范围内,且 S是否与(n-1)*n/2同奇偶}
then writeln('nO')

else begin
t←(t-s)div2;{ 1)*n/2-S]/2} a←0;{首项为0} writeln(a); 令 T=[(n-

2、统计分析法: 我们在一时得不到事物的特征机理的情况下,通过某种方法 测试得到一些数据(即问题的部分解),再利用数理统计知 识对数据进行处理,从而得到最终的数学模型

极值问题
m,n 为整数,且满足下列两个条件: ① m,n ∈1, 2, 3, ……,k (1≤k≤109);

② (n2-mn-m2)2=1。
由键盘输入k,求一组满足上述两个条件的m,n 并且使m2+n2 的值最大。
K 2 3 4 8 16 32 64

N

2

3

3

8

13

21

55

M

1

2

2

5

8

13

34

如果我们的猜想正确,那么当(n,m)是方程(n2-mn-m2)2=1的一组解时,根据 斐波拉契数列关系,(n+m,n)也一定是方程的一组解。 若((n+m)2-(m+n)n-n2)2=1成立,则 =>(n2+(m+n)n-(n+m)2)2=1=>(n2+mn+n2-n2-2mn-m2)2=1=>(n2-mn-m2)2=1成立

以上各步可逆,所以当(n,m)是方程(n2-mn-m2)2=1的一组解时,(n+m,n) 一定是方程的另一组解。
var m,n,next,k :longint; begin

write('k= '); readln(k);
if (k<1) or (k>1000000000) then halt; m←1; n←1; next←m+n; while next<=k do begin m←n; n←next;next←m+n; end;{while} writeln('m= ',m); end.{main} writeln('n= ',n);

{读入n和m的上限k}
{如果k不在要求范围内,就终止} {确定斐波拉契数列的头三项} {顺推,求出m,n的最大值}

{输出可使m2+n2的值最大的m和n}

取石子问题 有两堆石子,数量可能不同。有两个人轮流取。 每次有两种不同的取法。一是在任意一堆中取走任 意多的石子。二是在两堆中同时取走相同数量的石 子。最后把石子全部取完的是胜者。现在给出初始 的两堆石子的数目,现在如果轮到你来取,又假设 双方都采取最好的策略,问最后你是胜者还是败者。 输入文件只有一行,其中包含两个非负整数a和b,表 示两堆石子的数目。(a,b≤1,000,000,000)。 输出文件也只有一行,包含一个数字。如果最后你是 胜者,则输出1。反之,则输出0。 输入示例:6 10 输出示例:0

1、分析失败的情况

测试结果有两种可能 ①失败的情况:(1,2) (3,5) (4,7) (6,10) (8,13) (9,15) (11,18) (12,20) (14,23) (16,26) (17,28)(19,31) (21,34)…。 ②胜利的情况:(1,1)(1,3)(1,4)…。 胜利的情况比失 败的情况多得多。 在上述两种情况中,我们选择相对容易得出的失败情况展开分析, 寻找规律; ① 从1开始的每一个数字,在这些数字对中都会出现一次且仅 会出现一次; ②数对的差成等差数列1,2,3,4…; ③有些数对的数字排列来自斐波那契数列 ④有些数对虽然不是标准斐波那契数列中的数字,但还是符合斐 波那契数列的规则; ⑤如果数对(a,b)出现在其中,则(a+b,a+2b)也必然出现在数对中 (相反的结论是不对的); ⑥数对中两个数之比都非常接近于=0.618,即著名的黄金分割数。

2 、判别a、b的输赢 由于从1开始的每一个自然数,按照斐波那契数列 的规则不重复地出现在失败的数对中,因此,可 以得出如下结论: 在失败的数对中如果一个数为x,则取(x*0.618) 的小数部分k。 若数对按照递增顺序排列成(a,b),且满足a=, 则确定(a,b)失败。由此得出算法: readln(x,y); if x>y then begin c←y;y←x;x←c;end; {按照递增顺序排列x和y} if x=y div 1.618 then writeln(0) {若x和y接近黄金分割数,则失败;否则胜利} else writeln(1);

祝同学们考出好成绩

谢谢!


推荐相关:

2008年杭州第十四中学风帆杯化学竞赛试题

烃的分子式 n(CO) n(CO2 ) 2008 年杭州第十四中学风帆杯化学竞赛试题答卷一、选择题(每小题 3 分,共 30 分。每小题只有一个正确答案) 1 2 3 4 5 6...


2015年浙江省中小学生艺术节获奖名单

2015年浙江省中小学生艺术节获奖名单_学科竞赛_小学教育_教育专区。2015年浙江省...杭州第四中学 宁波效实中学 温州市实验中学 浙江省温州中学 绍兴市柯桥区实验...


杭州第四中学学校工作总结

杭州第四中学学校工作总结_职业规划_求职/职场_实用文档。杭州第四中学学校工作...校生物学科在第四届全国中学生生物学联赛(浙 江赛区)中取得优异成绩(一等奖 2 ...


第四届杭州市中小学美术教师基本功比赛

第四杭州市中小学美术教师基本功比赛 小学组试卷姓名 编号 一、 填充 (内容依据 《九年义务教育小学 (初中) 美术教学大纲》 (试用修订版) 、 《美术课程标准...


竞赛试题集锦

初中数学竞赛辅导资料(12) 61.--1228 古楼中学八...浙江省第四届高中生物学竞赛初赛试卷及参考答案 77....年杭州市高中数学竞赛第二试试题 81.--1987 中国...


多角度解读杭州前八所重点高中

实力不如杭高, 但理科竞赛成绩一定是比杭高好的, 而且几门理科的竞赛辅导老师...杭州第四中学杭州第四中学是一所具有百年历史、师资精良、学风严谨、设施完备的...


杭州四中下沙校区2013年暑假教师值班安排表

杭州四中下沙校区2013年暑假教师值班安排表_其它技巧_PPT制作技巧_PPT专区。杭州四中...(5) 每天其余时间和双休日由保安人员值班。 浙江省杭州第四中学 2013-7-1 ...


2014年杭州市第十四中学保送生考试数学试卷

2014年杭州市第十四中学保送生考试数学试卷_初三数学_数学_初中教育_教育专区。杭州...? x ? 4 上是否存在点 P, 使∠ OPC=90° , 若存在,请求出点 P 的...


浙江省杭州第十四中学2014-2015学年高三年级三月月考英语试卷(无答案)

浙江省杭州第十四中学2014-2015学年高三年级三月月考英语试卷(无答案)_英语_高中...(共 20 小题;每题 0.5 分,满分 10 分) 从 A、B、C、D 四个选项中,...


杭州第四中学高一年级2014学年第一学期期中考试数学试题卷及参考答案

杭州第四中学高一年级2014学年第一学期期中考试数学试题卷及参考答案_高一数学_数学_高中教育_教育专区。杭州第四中学高一年级2014学年第一学期期中考试数学试题卷及...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com