![高中信息技术 信息学奥赛PASCAL语言 信息学辅导-上海课件_第1页](http://file3.renrendoc.com/fileroot_temp3/2021-12/31/5fd5fc86-ba4a-490c-98db-21c4a922e2cc/5fd5fc86-ba4a-490c-98db-21c4a922e2cc1.gif)
![高中信息技术 信息学奥赛PASCAL语言 信息学辅导-上海课件_第2页](http://file3.renrendoc.com/fileroot_temp3/2021-12/31/5fd5fc86-ba4a-490c-98db-21c4a922e2cc/5fd5fc86-ba4a-490c-98db-21c4a922e2cc2.gif)
![高中信息技术 信息学奥赛PASCAL语言 信息学辅导-上海课件_第3页](http://file3.renrendoc.com/fileroot_temp3/2021-12/31/5fd5fc86-ba4a-490c-98db-21c4a922e2cc/5fd5fc86-ba4a-490c-98db-21c4a922e2cc3.gif)
![高中信息技术 信息学奥赛PASCAL语言 信息学辅导-上海课件_第4页](http://file3.renrendoc.com/fileroot_temp3/2021-12/31/5fd5fc86-ba4a-490c-98db-21c4a922e2cc/5fd5fc86-ba4a-490c-98db-21c4a922e2cc4.gif)
![高中信息技术 信息学奥赛PASCAL语言 信息学辅导-上海课件_第5页](http://file3.renrendoc.com/fileroot_temp3/2021-12/31/5fd5fc86-ba4a-490c-98db-21c4a922e2cc/5fd5fc86-ba4a-490c-98db-21c4a922e2cc5.gif)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、2 2、20022002年年分区联赛高中分区联赛高中组试题解析组试题解析1 1、计算机基础知识、计算机基础知识3 3、改善高精度运算的效率、改善高精度运算的效率4 4、构造法、构造法一、一、 计算机的发展与应用计算机的发展与应用二、计算机组成与工作原理二、计算机组成与工作原理 和信息的表示与存储和信息的表示与存储 三、多媒体应用三、多媒体应用 四、计算机网络使用基础四、计算机网络使用基础 五、程序设计语言基础五、程序设计语言基础 六、程序的阅读分析六、程序的阅读分析计算机的发展历经了哪几个阶段;计算机的发展历经了哪几个阶段;按照功能和规模,可将计算机分成哪几大按照功能和规模,可将计算机分成哪几
2、大类,它们各自的分工是什么;类,它们各自的分工是什么;武装计算机的软件系统包括了哪些东西;武装计算机的软件系统包括了哪些东西;计算机的发展怎样促使人类走向丰富多彩计算机的发展怎样促使人类走向丰富多彩的信息社会;的信息社会;用户在使用计算机时应该遵守哪些道德规用户在使用计算机时应该遵守哪些道德规范;范; 计算机发展史上的里程碑计算机发展史上的里程碑计算机存储程计算机存储程序的工作原理序的工作原理美籍匈牙利数学家冯诺依曼(von Neumaml)在1946年提出的,其思想是,在计算机中设置存储器,将符号化的计算步骤存放在存储器中,然在计算机中设置存储器,将符号化的计算步骤存放在存储器中,然后依次取
3、出存储的内容,由一个被称之为控制器的部件进行译码,译码后依次取出存储的内容,由一个被称之为控制器的部件进行译码,译码结果在一个被称为运算器的部件中进行计算,从而实现计算机工作的自结果在一个被称为运算器的部件中进行计算,从而实现计算机工作的自动化(运算器和控制器统称为动化(运算器和控制器统称为CPU)。)。冯诺依曼依据此原理设计出一个完整的计算机雏形,并确定了计算机的五大组成部分和基本的工作方法。操作系统是计算机系统中的一种系统软件,它能对操作系统是计算机系统中的一种系统软件,它能对计算机系统中的软件和硬件资源进行有效地管理和计算机系统中的软件和硬件资源进行有效地管理和控制,合理地组织计算机的工
4、作流程,为用户提供控制,合理地组织计算机的工作流程,为用户提供一个使用计算机的工作环境。一个使用计算机的工作环境。 DOS单用户的唯一任务占用计算机上所有的硬件和软件资源,所能访问的主存地址空间太小。Windows多作业、大内存管理、统一的图形用户界面 ,并且发展到网络环境使用UNIX操作系统 、Linux操作系统 、Macintosh OS 数据库技术的特性数据库技术的特性最小冗余最小冗余 数据共享数据共享数据独立性数据独立性安全性安全性 完整性完整性 数据库管理系统的类型数据库管理系统的类型OLTP(联机事务处理)DSS(决策支持系统)EIS(行政信息系统)OA(办公室自动化)按其系统结构
5、分为单机、Unix多用户、网络多用户、客户机服务器、集中式、分布式、集中分布式等。目前,世界上比较流行的数据库管目前,世界上比较流行的数据库管理系统(理系统(DMSDMS)有有高档数据库产品,如Informix,Oracle,Sybase,Progress,Unify等中、低档数据库产品,如DBASE,Paradox,SuperBase,Foxpro,Clipper,SQL Base,Focus等;数据库开发工具,如Access,Visual Basic,Uniface,Power Builder,QEDatabase Editor等。计算机病毒的特征计算机病毒的特征能够将自身复制到其他程序中
6、。 不独立以文件形式存在,仅附加在别的程序上。当调用该程序运行时,此病毒则首先运行。防治病毒的步骤:防治病毒的步骤: 不要用软盘启动机器 不要运行来路不明的软件 定期备份重要系统数据 重要的数据盘,程序盘应写保护 使用杀毒软件检查和清除病毒进位计数制之间的转换问题。1、R进制转换为十进制进制转换为十进制 基数为R的数字,只要将各位数字与它的权相乘,其积相加,和数就是十进制数(xpx0.x-1x-k)R=( )10例: 1101101.01012=12021122+123十024125126+02-1+12-202-3+12-4=109.3125当从R进制转换到十进制时,可以把小数点作为起点,分
7、别向左右两边进行,即对其整数部分和小数部分分别转换。对于二进制来说,只要把数位是1的那些位的权值相加,其和就是等效的十进制数。 pkiiiRx)(2、十进制转换为、十进制转换为R进制进制 将此数分成整数与小数两部分分别转换,然后再拼接起来。 进制整数转换成R进制的整数,可用十进制数连续地除以R,其余数即为R系统的各位系数。此方法称之除R取余法。例如:将5710转换为二进制数十进制小数转换成R进制时,可连续地乘以R,直到小数部分为0,或达到所要求的精度为止(小数部分可能永不为零),得到的整数即组成R进制的小数部分,此法称为“乘R取整”例:将0.312510转换成二进制数 0.31252 =0.6
8、25 0.6252 =1.25 0.252=0.5 0.52 =1.03、二、八、十六进制的相互转换、二、八、十六进制的相互转换即每位八进制数相当于三位二进制数,每位十六进制数相当于四位二进制数。在转换时,位组划分是以小数点为中心向左右两边延伸,中间的0不能省略,两头不够时可以补0。例如:将1011010.10-2转换成八进制和十六进制数 001 011 010. 100 1011010.102132.481 3 2. 40101 1010. 1000 1011010.102=5A.816 5 A . 8将十六进制数F7.28变为二进制数F 7 . 2 8 F7.2816=11110111.0
9、010121111 0111.0010 1000 将八进制数25.63转换为二进制数2 5 6 3 25.63810101.110011210 101 . 110 011 三、在计算机中带符号数的表示法三、在计算机中带符号数的表示法1、机器数与真值、机器数与真值规定在数的前面增设一位符号位,正数符号位用“0”表示,负数符号位用“1”表示。 为了区别原来的数与它在计算机中的表示形式,我们将已经数码化了的带符号数称为机器数,而把原来的数称为机器数的真值。例如N1=+1001100、N2=-1001100为真值,其在计算机中的表示01001100和11001100为机器数。 2、原码、原码true
10、form 在用二进制原码表示的数中,符号位为0表示正数,符号位为1表示负数,其余各位表示数值部分。这种表示法称为原码表示法。字长为n的数(包括符号位)的原码表示法可定义为x原=若真值丨x丨1,其原码表示法可定义为x原=例如对于8位二进制原码+0原=00000000,-0原=10000000-1101001原=10000000-(-1101001)=111010013、补码(、补码(twos complement)即x补模+x 对于正数, x补=x,正数的补码就是该正数本身。 对于负数, x补=2n+x(mod 2n)。 +0补-0补000 -2n-1补=2n-2n-1=2n-1 4、反码、反码
11、0nes Complement 对于正数,它的反码表示与原码相同。即x反=x原对于负数,则除符号位仍为“1”外,其余各位“1”换成”0”,”0”换成1”,即得到反码X反。例如-1101001 反=10010110。对于0,它的反码有两种表示:+0 反=000 -0 反=111当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、补码的加减法运算、补码的加减
12、法运算 补码的加法运算补码的加法运算 在计算机中进行两个带符号数的加法运算时,只要将给定的真值用补码表示,就可以直接进行加法运算。在运算过程中不必判断加数和被加数的正负,一律做加法,最后将结果转换为真值即可。补码的减法运算补码的减法运算 对于补码的减法运算,由于存在x-y=x+(-y),因此x-y补=x+(-y) 补=x补+-y补 (mod2n)其中-y补=y补补。 信息存储单位信息存储单位位(位(bit,缩写为缩写为b):度量数据的最小单位,表示一位二进制信息。字节字节(byte,缩写为缩写为B):一个字节由八位二进制数字组成(l byte8bit)。字节是信息存储中最常用的基本单位。 计算
13、机存储器(包括内存与外存)通常也是以多少字节来表示它的容量。常用的单位有:KB 1K=1024,MB 1M=1024K,GB 1G=1024M字(字(word):):字是位的组合,并作为一个独立的信息单位处理。字又称为计算机字,它的含意取决于机器的类型、字长以及使用者的要求。常用的固定字长有8位、16位、32位等。信息单位用来描述机器内部数据格式,即数据(包括指令)在机器内的排列形式,如单字节数据,可变长数据(以字节为单位组成几种不同长度的数据格式)等。机器字长:机器字长:在讨论信息单位时,还有一个与机器硬件指标有关的单位,这就是机器字长。机器字长一般是指参加运算的寄存器所含有的二进制数的位数
14、,它代表了机器的精度。机器的功能设计决定了机器的字长。一般大型机用于数值计算,为保证足够的精度,需要较长的字长,如32位、64位等。而小型机、微型机、微机一般字长为16位、32位等。非数值信息的表示非数值信息的表示西文字符编码西文字符编码ASCII码 “美国信息交换标准代码”的简称。ASCII码包括09十个数字,大小写英文字母及专用符号等95种可打印字符,还有33种控制字符(如回车、换行等)。一个字符的ASCII码通常占一个字节,用七位二进制数编码组成,所以ASCII码最多可表示128个不同的符号。最高位作为校验码,以便提高字符信息传输的可靠性。数字和字母的ASCII码按照数字递增顺序或字典顺
15、序排列排列,大写字母和小写字母的ASCII码是不同的。EBCDIC码美国IBM公司在它的各类机器上广泛使用的一种信息代码。一个字符的EBCDIC码占用一个字符,用八位二进制码表示信息,最多可以表示出256个不同代码。 中文信息编码中文信息编码目前的汉字编码方案有二字节、三字节甚至四字节的。下面我们主要介绍“国家标准信息交换用汉字编码”(CB2312-80标淮),以下简称国标码。 国际码是二字节码,用二个七位二进制数编码表示一个汉字。目前国标码收人6763个汉字,其中一级汉字(最常用)3755个,二级汉字3008个,另外还包括682个西文字符、图符。 在计算机内部,汉字编码和西文编码是共存的。区
16、分的方法之一是对于二字节的国标码,将二个字节的最高位都置成1,而ASCIl码所用字节最高位保持0,然后由软件(或硬件)根据字节最高位来作出判断。 “多媒体技术多媒体技术”就是用计算机交互地综合处理文就是用计算机交互地综合处理文本、图形、图象、动画、音频及视频影象等多种本、图形、图象、动画、音频及视频影象等多种信息,并使这些信息建立逻辑连接。信息,并使这些信息建立逻辑连接。 色彩数目色彩数目 分辨率分辨率特点16640*480Windows的最低配置、显示速度最快256800*600性能虽好一些,但易产生调色板的冲突655361024*768全彩的显示模式,色彩逼真,不会再有调色板的冲突。16M
17、1284*1024高等级的3D绘图软件和专业级的视频录制人员使用的真彩色模式,要求更多的RAM在显示卡和主机板上,CPU最好也是顶级的。 显示卡显示卡 水平分辨率垂直分辨率色彩数目显示存储空间显示加速:VRAM、EDO RAM,Windows RAM,Ramlbus DRAM 显示模式显示模式 数据压缩和解压缩技术数据压缩和解压缩技术 静止图像压缩标准静止图像压缩标准JPEG(Joint Photographic ExpertsCroup)动态图像压缩标准动态图像压缩标准MPEG(Moving Picture Experts Croup) 多通道的动态图像压缩标准多通道的动态图像压缩标准MP6
18、4 相关名词相关名词 位图:位图:由一点一点的像素点排成矩阵组成的,其中每一个像素点都可以是任意颜色。 向量图:向量图:用向量代表图中所表现的元素。 像素像素 :图形的最小组成单位 真彩色:真彩色:人的眼睛能够分辨出的颜色大约有1万6千多种,为了能表现出这么多种色彩,我们得用24bit(224=16M)来描述一个像素的颜色,这种显示模式就称为真彩色。 RGB模式:模式:分别代表红、绿、蓝三种颜色,计算机以RGB模式来定义计算机屏幕上的颜色。通过混色原理,不同比例的RGB色彩可调和出无穷多种颜色。HSB模式:模式:分别表示色调(hue)、饱和度(saturation)、亮度(bright)。不同
19、的色调代表不同的颜色;饱和度指的是某区域中,该颜色量的多少,饱和度越低,该区域看起来就越灰暗;亮度则是指颜色的亮、暗,极亮成白色,极暗则成黑色。相对于RGB模式,HSB模式设定颜色的方式可产生更好的视觉效果。多媒体信息处理工具 图形制作平台FreeHand 图像处理平台Photoshop动画制作平台 Animation Pro 数字动画的类型:数字动画的类型:基于模型的动画 帧动画 动画中加人声音的方法动画中加人声音的方法嵌人式嵌人式将声音文件经过转换合并到影片文件中去。流式流式声音与文件分开,在影片播放的各个时机启动声音文件音乐音乐 波形音频文件波形音频文件 :通过现场录制和模数转化产生,存
20、储量大MIDI文件:文件:使用键盘合成器和一个音序器 制作和编辑,存储量小广域网(广域网( WAN ):):实现远距离的计算机之间的数据传输和信息共享的计算机网络。通信线路一般租用电话线路或铺设专用电缆。局域网络(局域网络(LIN):):为一个单位,或一个相对独立的局部范围内大量存在的微机能够相互通信、共享昂贵的外部设备(如大容量磁盘、激光打印机、绘图议等)、共享数据信息和应用程序而建立的计算机网络。通信线路一般不租用电话线路,使用专门铺设的线路。互联网(互联网(Internet):):将遍布全球的子网通过连网协议集成到一个共享的、开放的、易于管理的主干网。 计算机网络的物理组成计算机网络的物
21、理组成 网络中心主干机网络中心主干机 、服务器服务器 、网络工作站网络工作站 共享的外部设备共享的外部设备 网卡网卡 通信线路通信线路(双绞线、同轴电缆和光缆、无线传输介质(如微波、红(双绞线、同轴电缆和光缆、无线传输介质(如微波、红外线和激光等)外线和激光等) 局部网络通信设备局部网络通信设备(中继器、集线器(中继器、集线器 ) 网络互连设备网络互连设备 (网桥(网桥、路由器和网关路由器和网关 ) 网络软件网络软件 (对等式网络操作系统(对等式网络操作系统 、服务器上的网络操作系统)、服务器上的网络操作系统) 计算机网络的拓扑结构计算机网络的拓扑结构 总线拓扑总线拓扑 星型拓扑星型拓扑 环型
22、拓扑环型拓扑 树型拓扑树型拓扑 计算机网络的体系结构计算机网络的体系结构 所谓网络体系结构就是对构成计算机网络的各组成部分之间的关系及所要所谓网络体系结构就是对构成计算机网络的各组成部分之间的关系及所要实现功能的一组精确定义。国际标准化组织(实现功能的一组精确定义。国际标准化组织(ISO)提出的开放系统互联提出的开放系统互联参考模型(参考模型(OSI)已成为网络体系结构的标准已成为网络体系结构的标准 Internet使用使用TCP/IP网络体系结构网络体系结构TCP/IP的层号的层号TCP/IP的层次的层次名名对应对应OSI模型的层模型的层次次3应用层(ftp和telnet等协议)应用层、表示
23、层、会话层2传输控制协议TCP传输层1网际协议IP网络层计算机网络应用模式计算机网络应用模式 客户机客户机/服务器模型:服务器模型:将应用分成客户机和服务器两大部分,并将它分配到整个网络上。由服务器提供资源,通常执行后台功能;而客户机使用服务器,通常执行前台功能。 文件服务器:文件服务器:提供操作系统中文件管理的各种功能(网络文件的访问方式:文件传输和文件访问 ) 打印服务器:打印服务器:将一台或几台打印机物理地连接到打印服务器上,可为多个客户机用户轮流使用 数据库服务器:数据库服务器:侧重于传统数据库管理系统的功能(如数据的定义及存取、数据的安全性与完整性、并发控制及事务处理等)的服务器 远
24、程登录:远程登录:通过用户帐号访问远地系统的资源Internet 网络地址网络地址 IPIP地址地址: : 网络数网络数网络主机数网络主机数 主机数主机数A类网络126163870642064770064B类网络16256645161048872096C类网络2064512254524386048总计20848943638028208域名(或称主机名称)域名(或称主机名称): :计算机主机名.子域名.子域名.最高层域名 Internet应用应用 文件传输文件传输 (使用匿名文件传输服务(匿名FTP)网上软件分类:公公共软件共软件 、免费软件免费软件 、共享软件共享软件 ) 远程登录远程登录(T
25、elnet 命令) 电子邮政服务电子邮政服务 (电子邮箱地址:用户名计算机域名) 网络新闻与公告牌服务网络新闻与公告牌服务 (网络新闻是由USENET在Internet中的新闻服务器节点之间进行传递的,阅读新闻组的软件有Outlook Express) 信息查询服务信息查询服务 (最为流行的信息查询服务系统是万维网(World Wide Web),简称WWW。 注意超文本和超媒体的概念 )程序设计语言的组成程序设计语言的组成 程序设计语言的基础是一组记号和规则。根据规程序设计语言的基础是一组记号和规则。根据规则由记号构成的记号串的总体就是语言。则由记号构成的记号串的总体就是语言。 包括包括语法
26、语法:程序的结构或形式。编译系统会自动进行语法检验; 语义语义:程序的含义,亦即表示按照各种方法所表示的各个记号的特定含义,但不涉及使用者。语义的错误是在源程序编译通过后的运行过程中出现的,属于算法类的错误。 语用语用:程序和使用者的关系; 语言的成分语言的成分数据成分数据成分,用以描述程序中所涉及的数据;运算成分,运算成分,用以描述程序中所包含的运算;控制成分,控制成分,用以描述程序中的控制构造;传输成分,传输成分,用以表达程序中数据的传输。 语言和程序设计的发展语言和程序设计的发展 第一代语言第一代语言机器语言机器语言 第二代语言第二代语言汇编语言汇编语言 第三代语言第三代语言高级语言、算
27、法语言(高级语言、算法语言(BASIC、FORTRAN、COBOL、Pascal、C ) 第四代语言第四代语言非过程化语言(非过程化语言(SQL语言)语言) 第五代语言第五代语言智能性语言(智能性语言(PROLOG语言语言 、LISP语言语言 ) 面向对象方法的主要概念面向对象方法的主要概念 对象对象系统中用来描述客观事物的一个实体,是构成系统的一个基本单位,对象由两个主要因素组成: 属性属性:描述对象静态特征的一个数据项; 服务服务:描述对象动态特征的一个操作序列; 消息消息对象之间通过服务请求发生联系,这种向对象发出的服务请求称为消息。 类类为了很好地控制软件的复杂度,将具有相同属性和服务
28、的一组对象组成类。 面向对象语言分为两大阵营面向对象语言分为两大阵营 Smalltalk和Eiffel为代表的纯粹型面向对象语言,主要强调软件开发的探索性和原型化开发方法; 以C+、Object Pascal为代表的混合型面向对象语言,主要扩充现有语言,强调运行时的时空效率;程序设计的特点程序设计的特点 构造性构造性 :不同的人为解决同一问题编制的程序,其面貌颇不相同,然而,程序的功效却是等价的。 严谨性严谨性:以上下文无关的形式语言实现。无法补充缺损信息、去掉冗余信息、将暂时不懂的信息暂时搁置起来,待下文或经过推理予以补充和理解 叠加性叠加性: 一般是将自己设计的子程序尽量分割成独立的、功能
29、明确单一的小模块,以便充分利用;甚至还会利用系统内的库函数。 抽象性抽象性:把客观事物的描述抽象为数据和算法,并且利用抽象使得程序能够正确的映射客观事物 。抽象是有层次的 ,不同层次上的抽象是相互独立和互相作用的 。计算程序的运行结果计算程序的运行结果 一、直接推理一、直接推理 $n+ varm,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= ,即i=1时,t=n;i=2时,t=n*
30、(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个连续的自然数乘起来,再依次除以1M就是一种不太明智的选择。上述程序先乘N除1,然后乘(N-1)除2,再乘(N-2)除3,最后乘(N-M+1)除M。因为连续的K个自然数的积一定能被K!整除,所以在这一过程中不会出现除不尽的情况。同时也使得中间结果比较小,从而提高了运算速
31、度。告诫读者的是,对于上述算法来说,n和m不能超过102。如果超过了这个上限,t就会溢出,尽管它采用了extended类型。miiin11label 10,20,30;var s,p:string; i,k,n,j,m:integer;begin readln(s); n:=length(s); readln(p); m:=length(p); i:=0; 10: i:=i+1; j:=i; k:=1; 20: if sjpk then begin if in-m+1 then goto 10; i:=0; goto 30; end else if k 0) then begin for j:
32、=i downto 0 do write(ansj); writeln;break; end;thenEnd.输入输入 输出输出 5 update(var a)是将数组a规整为高精度的十进制数组 mult(var a,b)是将高精度的十进制数组a乘以整数b,积存储在a中。 add(x, ob)计算因子表,ob=1,numnum*x;ob=-1,numnum/x。其中numi为因子i的个数 主程序计算catalan数1/(n+1)*c(2*n,n) 。显然n=5,则程序输出42(1/6*c(10,5)完善程序完善程序 填空内容:填空内容: 1、变量方面的填空、变量方面的填空 2、循环方面的填空、
33、循环方面的填空 3、分支转移方面的填空、分支转移方面的填空 4、主程序和子程序关系方面的填空、主程序和子程序关系方面的填空 5、输入输出方面的填空、输入输出方面的填空 填空方法:填空方法: 按照自顶向下的思维方法阅读程序按照自顶向下的思维方法阅读程序从主程序开始,从主程序开始,沿控制层次向下阅读。在查到某一个子程序沿控制层次向下阅读。在查到某一个子程序(子模块子模块)时,比时,比照题目给出的说明和调用它的照题目给出的说明和调用它的“父程序父程序(父模块父模块)”,弄清该,弄清该子程序子程序(子模块子模块)究竟要达到什么样的子目标,然后查程序,究竟要达到什么样的子目标,然后查程序,看它是如何实现
34、这个子目标的。如果该子程序看它是如何实现这个子目标的。如果该子程序(子模块子模块)有空有空格,则按照算法的逻辑进行填空。依次类推,直至最底层的格,则按照算法的逻辑进行填空。依次类推,直至最底层的子程序(子模块)中的空格全部填完为止。子程序(子模块)中的空格全部填完为止。1、完善不含子程序的程序、完善不含子程序的程序 首先划分各个子模块的层次结构,并确定每个子模块的子首先划分各个子模块的层次结构,并确定每个子模块的子目标。然后自顶向下,根据子目标和上层子模块给出的线索,目标。然后自顶向下,根据子目标和上层子模块给出的线索,对当前层次的各个模块进行填空。依次类推,直至最底层的子对当前层次的各个模块
35、进行填空。依次类推,直至最底层的子模块中的空格全部填完为止。模块中的空格全部填完为止。求元素之和最大的子方阵:在mn(m,n20)的正整数数字方阵中,找出一个pq的子阵(1pm,1qn)使其元素之和最大。例如,下面54的数字阵中,元素之和最大的一个23子阵。 54数字阵 元素之和最大的23子阵为384221117952162103892712352161038var a:array1.20,1.20 of integer; 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 ai,j:
36、=0; readln(m,n); for i:=1 to m do begin for j:=1 to n do read(ai,j); readln end; readln(p,q); max:=0; for i:=1 to m-p+1 do for j:=1 to n-q+1 do begin ; for i1:=i to p+i-1 do for j1:=j to q+j-1 do ; if smax then begin ; p1:=i; q1:=j end; end; for i:=p1 to do begin for j:=q1 to do write(ai,j:3); write
37、ln end; readln end. 模块模块1(初始化,白色白色):方阵清零;读方阵规模;读方阵;读子阵规模;子阵的最大数和初始化模块模块2(湖蓝)(湖蓝)通过枚举所有可能子阵,求数和最大的子阵 。其中子模块1(深蓝)(深蓝):累计(i,j)为左上角的子阵的数和 子模块2(淡绿)(淡绿):调整子阵的最大数和 模块3(红色)(红色)输出最大数和的子阵。 由此得出解 s:=0 s:=s+ai1,j1 max:=s p1+p-1 q1+q-1以下程序完成对数组每个元素向后移动n个单位。数组元素的下标依次为0到m-1,对任意一个数组元素ai而言,它的值移动后将存储在数组元素a(i+n) mod m
38、中。例如,m=10,n=3,移动前数组中存储的数据如下前一行所示,则程序运行后数组中存储的数据如下后一行所示。 0 3 86 20 27 67 31 16 37 42 16 37 42 0 3 86 20 27 67 31const maxm=10000;var i,k,m,n,rest,start,temp:longint; a:array 0.maxm of longint;beginwrite(input m,n:);readln(m,n);f o r i : = 0 t o m - 1 d o ai:=random(100);writeln(before move);for i:=0
39、to m-1 do write(ai:5);writeln;rest:=m; start:=0;while do begin k:=start;repeat k:=(k+n) mod m until k0 或 rest0 k=start rest:=rest-1 a(k+n) mod m:=temp 或 a(start+n) mod m:=temp start:=start+1完善含子程序结构的程序完善含子程序结构的程序 如果子模块采用过程或函数,则通常以子程序为单位划分层次结构,这样可以使得其层次性相对不含子程序的程序来说要清晰一些。 程序的任务是用09中的n个数字填入如下乘法运算的*处,数
40、字可重复使用,且所用的数字至少有一个是素数,要求输出满足下列算式的方案数。 * * * * * - * * * * * * - * * * 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; t:byte; begin readln(n); s:=; for i:=1 to n do begin read(t); s:=s+t; end; close(f); end; function ok(x,l:integer):boolean
41、; 此函数判断此函数判断x是否符合条件是否符合条件 var t:byte; begin ok:=false; if _l then exit; while x0 do begin t:=x mod 10; if not (t in s) then exit; x:=x div 10; end; ok:=true; end; function inset(x:integer):boolean; 此函数判断此函数判断x中是否包含素数字中是否包含素数字 var t:byte; begin inset:=false; while _ do begin t:=x mod 10; if t in p th
42、en begin inset:=true; exit; end; _ end; end; procedure work; var i,i1,i2,i3,j1,j2:integer; begin ans:=0; for i1:=1 to 9 do if i1 in s then for i2:=1 to 9 do if i2 in s then for i3:=1 to 9 do if i3 in s then begin _ 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
43、 ok(j2*i,3) and _ then begin 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) then inc(ans);end; end; writeln(ans); end; begin init; work; end.模块模块1初始化。读入数字个数n和n个整数,并将它们送入集合s(init过程)。 模块模块2计算和输出方案数ans(work过程) 在s集合中枚举所有可能的被乘数i1 i2 i3和所有可能的乘数j1 j2,被乘数和乘数必须
44、满足如下条件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 x0 x:=x div 10 i:=i1*100+i2*10+i3 ok(j1*i*10+j2*i,4)菲波拉契数列为菲波拉契数列为1,1,2,3,5,8,13,21,
45、其元素产生的其元素产生的规则是前两个数为规则是前两个数为1,第三个数开始每个数等于它前,第三个数开始每个数等于它前面两个数之和。已知任意一个正整数可以表示为若面两个数之和。已知任意一个正整数可以表示为若干个互不相同的菲波拉契数之和。干个互不相同的菲波拉契数之和。 例如:例如:36=21+13+2 下面的程序是由键盘输入一个正整数下面的程序是由键盘输入一个正整数n,输出组成输出组成n的互不相同的菲波拉契数的互不相同的菲波拉契数寻找小于等于寻找小于等于n的最大菲波拉契数的最大菲波拉契数a,并以并以a作为组作为组成成n的一个数;的一个数;若若na,则以则以na作为作为n的新值,重复步骤的新值,重复步
46、骤(1)。若。若an,则结束:则结束: var n:integer; first:boolean; function find(n:integer):integer; var a,b,c:integer; begin a:=1;b:=1; repeat c:= ; a:=b;b:=c; until b=n; if b=n then find:= else find:= end; procedure p(n:integer); var a:integer; begin a:=find(n); if first then begin write(a:4); first:=false end els
47、e write(+,a:4); if an then p ; end; begin 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) 虽然2002年全国奥林匹克信息学复赛中含许多可“一题多解” 的试题,但如果按照较优算法标准分类的话,大致可分为 算法算法分区联赛分区联赛 几何计算(点和矩形的关系)矩形覆盖字符
48、串处理字符近似查找 回溯法选数、字串变换 构造法级数求和、 均分纸牌、自由落体1、凸现信息学知识和学科知识整合的趋势凸现信息学知识和学科知识整合的趋势。为了考核学生运用学科知识的能力,激发学生为了考核学生运用学科知识的能力,激发学生的创造力,的创造力,2002年全国奥林匹克信息联赛年全国奥林匹克信息联赛(NOIP)中学科类的试题增加,并且首次出现了计算几中学科类的试题增加,并且首次出现了计算几何类的试题何类的试题。这说明信息学与学科的依赖。这说明信息学与学科的依赖关系日益凸现,学科基础好、尤其是数学素质关系日益凸现,学科基础好、尤其是数学素质好的人虽然不一定会编程,但希望学习编程的好的人虽然不
49、一定会编程,但希望学习编程的人愈来愈多;编程解题能力强的人势必有数学人愈来愈多;编程解题能力强的人势必有数学的潜质和爱好,他们中愈来愈多的人也希望深的潜质和爱好,他们中愈来愈多的人也希望深造数学。各门学科的交融和整合是奥林匹克信造数学。各门学科的交融和整合是奥林匹克信息学联赛活动发展的一个大趋势息学联赛活动发展的一个大趋势(有专家提议,数学教材(有专家提议,数学教材讲算法,信息科技教材讲语言,上海的信息科技教材出现真值表(初中)和讲算法,信息科技教材讲语言,上海的信息科技教材出现真值表(初中)和c语言(高中)。语言(高中)。2、“构造法构造法” 或贪心策略类试题的引或贪心策略类试题的引入,使得
50、入,使得算法知识的不确定性和不稳定算法知识的不确定性和不稳定性增加。性增加。这正体现了科学的本质这正体现了科学的本质知识知识是不断推陈出新的。是不断推陈出新的。3、试题的综合性增加试题的综合性增加,并不一定随知,并不一定随知识的分类而发生变化,有时几乎找不识的分类而发生变化,有时几乎找不到一个单一的经典算法到一个单一的经典算法,也找不到一个纯粹的数据结也找不到一个纯粹的数据结构问题构问题,关键是你从哪个角度去分析,关键是你从哪个角度去分析,也就是说能不能综合所学的知识,应也就是说能不能综合所学的知识,应用自如地解决问题。选手的综合素质用自如地解决问题。选手的综合素质愈高,得胜的机率愈大;愈高,
51、得胜的机率愈大; 4、经常面对着不知道算法的试题,经常面对着不知道算法的试题,面对着谁都不知如何处置的情境面对着谁都不知如何处置的情境,因此必须使学生正确地理解问因此必须使学生正确地理解问题、深入问题的空间并形成解决问题、深入问题的空间并形成解决问题的意识、习惯和能力。能不能题的意识、习惯和能力。能不能创创造性地应答没有遇到过的挑战造性地应答没有遇到过的挑战,成成为培训的基本要求和目标。为培训的基本要求和目标。 1 1、培养问题意识和问题能力。培养问题意识和问题能力。创造始创造始于问题。于问题。“有了问题才会思考,有了思有了问题才会思考,有了思考才有解决问题的方法,才有找到独立考才有解决问题的
52、方法,才有找到独立思路的可能(陶行知)思路的可能(陶行知)”。有问题虽然。有问题虽然不一定有创造,但没有问题一定没有创不一定有创造,但没有问题一定没有创造造; 2 2、处理好前沿性与基础性、直线培训和处理好前沿性与基础性、直线培训和散点培训、循序渐进与跳跃式的矛盾。散点培训、循序渐进与跳跃式的矛盾。如果恪守按部就班的培训程序,不谋求跳跃式如果恪守按部就班的培训程序,不谋求跳跃式学习,将离全国和国际奥林匹克信息学活动的学习,将离全国和国际奥林匹克信息学活动的前沿、离世界程序设计知识的前沿愈来愈远。前沿、离世界程序设计知识的前沿愈来愈远。因此在进行基础课程学习的同时,必须有追逐因此在进行基础课程学
53、习的同时,必须有追逐前沿的选择性学习。这里,有时候心理的障碍前沿的选择性学习。这里,有时候心理的障碍比科学上的障碍更难跨越,敢不敢的问题比能比科学上的障碍更难跨越,敢不敢的问题比能不能的问题更突出。其实在学习中或多或少地不能的问题更突出。其实在学习中或多或少地都有必要的跳跃,不少人还能够实现比较大的都有必要的跳跃,不少人还能够实现比较大的跳跃跳跃v学生必须学会从浩如烟海的信息中选择最有价值的知识,构建个性化(符合自己能力结构和兴趣结构)和竞争需要的知识结构v培训内容要有选择性,因为除了出题者,谁也说不清楚在未来竞赛中究竟什么知识是必要的,因此不可能把所有重要的东西都选择好了给学生,而是应该将直
54、线培训与散点培训相结合,选择部分重要的东西交给学生,让他们自己去探索若干知识点之间的联系,补充自己认为需要补充的知识。参与活动的学生应由竞参与活动的学生应由竞争关系和独立关系争关系和独立关系转向合作学习的关系转向合作学习的关系学生的心理调适:学生的心理调适:v我掌握的知识仅不过是沧海一粟我掌握的知识仅不过是沧海一粟(进取心进取心);v固守错误的概念比一无所知更可怕固守错误的概念比一无所知更可怕(明智)(明智);v三人之行必有我师三人之行必有我师(谦虚)(谦虚);v知识生产社会化条件下人的基本素质之一知识生产社会化条件下人的基本素质之一是合作精神(现在的重大科学发明需要成百是合作精神(现在的重大
55、科学发明需要成百上千科学家进行长期甚至跨国的合作,例如上千科学家进行长期甚至跨国的合作,例如制作制作windows,人类基因工程)人类基因工程)(现代意识)(现代意识);前提条件:前提条件:水平相当的同质成员水平相当的同质成员或各有所长(包括数学知识、编或各有所长(包括数学知识、编程能力和思维方式等解题所需的程能力和思维方式等解题所需的各种因素)的异质成员是开展合各种因素)的异质成员是开展合作学习的组织基础;作学习的组织基础;合作学习的效应:合作学习的效应:v集思广益容易出好的算法;集思广益容易出好的算法;v群体设计的测试数据相对全面;群体设计的测试数据相对全面;v在群体活动中能比较客观的反映
56、自己在群体活动中能比较客观的反映自己能力情况;能力情况;v每个学生在付出与给予中可提高合作每个学生在付出与给予中可提高合作精神和编程能力,成功者往往是那些相精神和编程能力,成功者往往是那些相容性好、容性好、 乐于帮助他人,并且善于取乐于帮助他人,并且善于取他人之长的学生他人之长的学生(符文杰、张一飞等)。(符文杰、张一飞等)。4、选手面对从未遇到过的、选手面对从未遇到过的挑战应调整好心态,挑战应调整好心态,不要急不要急功近利,要只管耕耘、不问收获、功近利,要只管耕耘、不问收获、潜心钻研、其乐无穷。那怕是一两潜心钻研、其乐无穷。那怕是一两次失误,也是砥砺之石,可从中汲次失误,也是砥砺之石,可从中
57、汲取有益的经验和教训。取有益的经验和教训。“不是一番不是一番寒彻骨,哪得梅花扑鼻香寒彻骨,哪得梅花扑鼻香”。问题描述问题描述 有N堆纸牌,编号分别为1,2,.N。每堆上有若干张, 但纸牌总数必为N的倍数。可以在任一堆上取若干张纸牌,然后移动。移牌规则为:在编号为:在编号为1 1堆上取的纸牌,只能移到编号为堆上取的纸牌,只能移到编号为2 2的堆上;在编号为的堆上;在编号为N N的堆上的堆上取的纸牌,只能移到编号为取的纸牌,只能移到编号为N-1N-1的堆上;其他堆上取的纸牌,可以移到相邻的堆上;其他堆上取的纸牌,可以移到相邻左边或右边的堆上。左边或右边的堆上。现在要求找出一种移动方法,用最少的移动
58、次数使每用最少的移动次数使每堆上纸牌数都一样多堆上纸牌数都一样多。例如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 堆纸牌,1N100) A1,A2,.An (N 堆纸牌,每堆纸牌初始数,1Ai10000) 输输 出出 :所有堆均达到相等时的最少移动次数。输入输出样例输入输出样例输入:输入: 4 9 8 17 6 输出:输出: 3设list为纸牌序列,其中listi为第i堆纸牌的张数(1in),ave为均分后每堆纸牌的张数,即 ;a
59、ns为最少移动次数。nilistni1我们按照由左而右的顺序移动纸牌。若第i堆纸牌的张数listi超出平均值,则移动一次(ans+1),将超出部分留给下一堆,既第i+1堆纸牌的张数增加listi-ave;若第i堆纸牌的张数listi少于平均值,则移动一次(ans+1),由下一堆补充不足部分,既第i+1堆纸牌的张数减少ave-listi; 右邻堆取的牌问题是,在从第i+1堆中取出纸牌补充第i堆的过程中,可能会出现第i+1堆的纸牌数小于零(listi+1-(ave-listi)xu ud-yy-yzA.out文件:文件: 3设规则序列为rule,其中第i条规则为rulei,1rulei,2;当前串
60、为now,其中tmp为now的一个待匹配子串。由于匹配过程的由左而右进行的,因此设j为now的指针,即从now的第j个字符开始匹配rulei,1。now适用第i条规则的条件是vnow中的子串被第i条规则替换后的长度小于255,即 length(now)+length(rulei,2)-length(rulei,1)255vrulei,1是now的一个子串(k=pos(rulei,1,tmp)0)在使用了第i条规则后,now变换为now= copy(now,1,j+k-1)+rulei,2+copy(now,j+k+length(rulei,1),255)由于now中可能有多个子串被第i条规则替
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 结构力学优化算法:模拟退火(SA):结构力学基础知识回顾
- 英语练与测﹒课课通(基础模块2)-答案
- 2021自身免疫性肝炎诊断和治疗指南(2021版)解读
- (沪教版)三年级上语文 32 葡萄是酸的
- 开学第一课-一年级开学第一课
- 电动套丝机作业安全技术操作规程
- 爱护身体 课件-2024-2025学年统编版道德与法治七年级上册
- 黄金卷08(考试版)-【赢在高考·黄金8卷】备战2024年高考地理模拟卷(湖北专用)
- 黄金卷07(参考答案)-【赢在高考·黄金8卷】备战2024年高考地理模拟卷(山东专用)
- 适用于新高考新教材备战2025届高考历史一轮总复习第5单元晚清时期的内忧外患与救亡图存第16讲挽救民族危亡的斗争课件
- 【课程思政优秀教学案例】《大学物理》课程
- 人美2011版六年级美术上册《电脑美术-照片美容》教案及教学反思
- 工程建设法规与案例分析(本科)PPT全套完整课件
- 《植树问题》 全国公开课一等奖
- “汽车营销策划”课程标准
- 2020年迪士尼SCAN反恐验厂审核程序文件
- 2023年安徽省初中学业水平考试英语试卷(含答案)-4608
- 车辆转让合同协议书电子版
- 医用耗材购销合同合同范本
- 布地奈德与特布他林的联合优势
- 66个ChatGPT副业赚钱技巧
评论
0/150
提交评论