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

信息学竞赛辅导交流会


信息学竞赛辅导交流会

梁一锋

新昌县城关中学 新昌县人民政府信息网络管理中心 2010-06-21

何林同学给吴文虎教授的一封信——摘录

如果有人问我,这五年的信息学生涯教会了我什么,我不会说“我会 用平衡二叉树”、也不会说“我学懂了动态规划”。我不管学到多少,总 还有很多没学到;即便是学会

了的东西,长时间不用也会遗忘。我认为我 真正学到的是习惯、态度和方法。我学会了批判性的看问题、我学会了用 开阔的胸怀去接受所有不同的想法、我学会了分析问题、总结问题、乃至 提出问题的一系列方法和经验。这些才是无价之宝,是一辈子在任何地方 任何时候都不会丢的宝贝。

NOIP简介
全国青少年信息学奥林匹克联赛(National Olympiad in Informatics in Provinces简称NOIP)自1995年至今已举办15次。每年由中国计算机学会 统一组织。 NOIP在同一时间、不同地点以各省市为单位由特派员组织。 全国统一大纲、统一试卷。初、高中或其他中等专业学校的学生可报名参 加联赛。联赛分初赛和复赛两个阶段。初赛考察通用和实用的计算机科学 知识,以笔试为主。复赛为程序设计,须在计算机上调试完成。参加初赛 者须达到一定分数线后才有资格参加复赛。联赛分普及组和提高组两个组 别,难度不同,分别面向初中和高中阶段的学生。获得提高组复赛一等奖 的选手即可免试由大学直接录取。

竞赛形式和成绩评定
联赛分两个年龄组:初中组和高中组。每组竞赛分两轮:初试和复试。 .初试形式为笔试,侧重考察学生的计算机基础知识和编程的基本能力,并对 知识面的广度进行测试。程序设计的描述语言采用Basic(2005年被取消)、 C/C++或Pascal。各省市初试成绩在本赛区前百分之十五的学生进入复赛,其分 数不计入复赛的成绩。初赛时间为10月的最后第二个星期六下午 2:30 - 16:30举行。 .复试形式为上机,侧重考察学生对问题的分析理解能力,数学抽象能力,驾 驭编程语言的能力和编程技巧、想象力和创造性等。程序设计语言可采用Basic (2005年后被取消)、Pascal、C或C++。各省市竞赛的等第奖在复试的优胜者 中产生。时间为 3小时。只进行一试,约在当年的11 月的第三个周六进行。 试题形式 每次联赛的试题分四组:初中组初试赛题;初中组复试赛题;高中组初试赛 题;高中组复试赛题。其中,初中组初试赛题和高中组初试赛题类型相同,初中 组复试赛题和高中组复试赛题类型相同,但初中组和高中组的题目不完全相同, 高中组难度略高;以体现年龄特点和层次要求。

竞赛形式和成绩评定
初试:初试全部为笔试,满分100分。试题由四部分组成: 1、选择题:共20题,每题1.5分,共30分。每题有4个备选方案。试题内容包括 计算机基本组成与原理、计算机基本操作、信息科技与人类社会发展的关系等等。 2、问题求解题:共2题,每题5分,共10分。试题给出一个叙述较为简单的问题, 要求学生对问题进行分析,找到一个合适的算法,并推算出问题的解。答案以字符 串方式给出,考生给出的答案与标准答案的字符串相同,则得分;否则不得分。

3、程序阅读理解题:共4题,每题8分,共32分。题目给出一段程序(没有关于 程序功能的说明),有时也会给出程序的输入,要求考生通过阅读理解该段程序给 出程序的输出。输出以字符串的形式给出,如果与标准答案一致,则得分;否则不 得分。 4、程序完善题:共 2题,第一题10分,共4空,每空2.5分;第二题18分,共6空, 每空3分。两题共28分。题目给出一段关于程序功能的文字说明,然后给出一段程序 代码,在代码中略去了若干个语句并在这些位置给出空格,要求考生根据程序的功 能说明和代码的上下文,填出被略去的语句。填对的,则得分;否则不得分。
(2009年普及组试题为第一题5空,每空3分,第二题前三空每空3分,后两空每空2 分)

竞赛形式和成绩评定
*复试:复试的题型和形式向全国信息学奥赛(NOI)靠拢,全部为上机编 程题,但难度略低。复试为决出竞赛成绩的最后一个环节。题目包括 4道题, 每题100分,共计400分。难度有易有难,既考虑普及面,又考虑选拔的梯 度要求。每一道试题包括:题目、问题描述、样例说明(输入、输出及必 要的说明)、数据范围(数据限制条件)。测试时,测试程序为每道题提 供了十组测试数据,考生程序每答对一组得10 分;累计分即为该道题的得 分。

讨论与交流:应该侧重于初赛还是复赛?

试题的知识范围具体如下: 初赛内容与要求: A.计算机的基本常识: B.计算机的基本操作: C.数据结构: 1.指针类型 2.多维数组 3.单链表及循环链表 4.二叉树 5.文件操作(从文本文件中读入 数据,并输出到文本文件中) 复赛内容与要求: 在初赛的内容上增加以下内容:

C.数据结构:
1.程序语言中基本数据类型(字符、整 数、长整数、浮点) 2. 浮点运算中的精度和数值比较 3.一维数组(串)与线性表 4.记录类型(PASCAL)/ 结构类型 (C)

试题的知识范围具体如下: 初赛内容与要求: D.程序设计: 1.结构化程序设计的基本概念 2.阅读理解程序的基本能力 3.具有将简单问题抽象成适合计算 机解决的模型的基本能力 4.具有针对模型设计简单算法的基 本能力 5.程序流程描述 6.程序设计语言(PASCAL/C/C++) E.基本算法处理: 1.初等算法(计数、统计、数学运 算等) 2.排序算法(冒泡法、插入排序、 合并排序、快速排序) 3.查找(顺序查找、二分法) 4.回溯算法 复赛内容与要求: D.程序设计 1.算法的实现能力 2.程序调试基本能力 3.设计测试数据的基本能力 4.程序的时间复杂度和空间复杂度 的估计

E.算法处理 1.离散数学知识的应用(如排列组 合、简单图论、数理逻辑) 2.分治思想 3.模拟法 4.贪心法 5.简单搜索算法(深度优先 广度优 先)搜索中的剪枝 6.动态规划的思想及基本算法

评测环境
1、使用Windows操作系统平台: (1)Windows操作系统必须使用Windows 2000、Windows XP及更新的 Windows版本; (2)Pascal语言,必须使用Free Pascal 1.0.10及以上版本作为编译器; (3)C语言,必须使用gcc 3.4.2作为编译器;

(4)C++语言,必须使用g++ 3.4.2作为编译器;
(5)Pascal语言,可以使用Freepascal IDE Windows版、Lazarus Windows 版、Dev-Pascal作为集成开发环境,推荐使用Lazarus Windows版; (6)C和C++语言,可以使用Dev-C++、RHIDE Windows版作为集成开发环 境,推荐使用Dev-C++; 2、使用Linux操作系统平台:

讨论与交流:关于语言的选择?

我选用的教学顺序:
0、体验程序设计 1、顺序结构 2、选择结构(判断) 3、循环结构 4、数组(一维) 5、函数与过程 6、数组(多维) 7、集合与记录、子界与枚举(自学为主,简单介绍) 8、指针、文件操作 9、基本算法归纳总结 10、其他算法讲解

复赛辅导: 以历年复赛试题的解题为主。

0、体验程序设计
Pascal语言介绍 1、基本符号: A-Z a-z 0-9 + - * / = <> <= >= < > ( ) [ ] { } := , . : .. ‘ ^ 2、保留字 AND, ARRAY, BEGIN, CASE, CONST, DIV, DO, DOWNTO , ELSE, END,FILE, FOR, FUNCTION, GOTO, IF, IN, LABEL, MOD, NIL, NOT, OF, OR, PACKED, PROCEDURE, PROGRAM, RECORD, REPEAT, SET, THEN, TO, TYPE, UNTIL , VAR, WHILE, WITH 3、标识符 以字母开头的字母、数字组合。自己定义,例如: x, y, max, min, sum, a15, a3b7, ……是合法的。 5x, x-y, ex10.5 ,α,β,η,π……不是标识符,非法的。 用途:表示各种常量、变量、类型、文件、函数、过程、或程序的名字。 特殊标识符:(标准标识符) 常量:false, true, maxint 类型:integer, real, char, Boolean, text 文件:input,output 函数:abs, arctan, chr, cos, eof, eoln, exp, ln, odd, ord, pred, round, sin, sqr, sqrt, succ, trunc 过程:get, new, pack, page, put, read, readln, reset, rewrite, unpack, write, writeln

程序结构 例1 :已知半径,求圆周长和面积的程序 数学公式:l=2πr s=πr2 PROGRAM circle(input,output); CONST pi=3.1415926; VAR r, l ,s : real; BEGIN read (r); l:=2*pi*r; s:=pi*r*r; write (r, l, s) END.

选用的习题: 1、输入三个数,计算并输出它们的平均值及三个数的乘积。 2、已知地球半径为6371km,计算并输出地球的表面积和体 积。 3、已知匀加速运动的初速度为10m/s,加速度为2m/s2,求20s 以后的速度,20s内走过的路程及平均速度。 4、已知物体的质量为m,求其在地球和月球受到的重力。

程序说明: 1、常量定义: CONST pi:=3.1415926; 定义一个常量pi, 值为3.1415926 2、变量定义: r,l,s:real; 定义了半径r,周长l,面积s,三个变量,类型为实型数据。 3、表达式: 2πr 2*pi*r πr2 pi*r*r b2-4ac b*b-4*a*c a+b (a+b)/2 2 4、输入输出语句: read(r) 从键盘输入一个数,赋给变量r write(r, l, s) 把r,l,s,的值输出到屏幕。 5、标点符号的写法: 整个程序一个句号,在最后 END. 每句语句后一个分号; 逗号用来分隔分量等 := 是一个赋值号 6、整个程序的书写格式: 保留字大写; 缩进格式。

1、顺序结构
一、用计算机解题的基本方法---“自顶而下,逐步求精” 上节的简单程序已体现出处理问题步骤、思路的顺序关系,这就是顺序结构程序。解题时,对问题 有一清楚了解,再仔细构造解题步骤——算法。算法可以“自顶而下,逐步求精”。对大问题先构 造大致轮廓,再逐步分解成小问题,直到可以用PASCAL语言描述出来。 二、基本标准数据类型 (一)实型(real) 1、简介:包括正实数、负实数和实数零,其实就是常说的小数,pascal中表示实型数的形式有两种。 ⑴十进制表示法:这是人们日常使用的带小数点的表示方法,如0.0、-0.0、+5.61、-8.0、6.050等都是实型常量,而0.、.37都不是合法的实数形式 ⑵科学记数法:采用指数形式的表示方法,如1.25×105可表示成1.25E+05。在科学记数法中, 字母"E"表示10这个"底数",而E之前为一个十进制表示的小数,称为尾数,E之后必须为一个整数, 称为"指数"。如-1234.56E+26、+0.268E-5 、1E5是合法形式,而.34E12、2.E5、E5、E、1.2E+0.5 都不是合法形式的实数。 无论实数是用十进制表示法还是科学表示法,它们在计算机内的表示形式是一样的,总是用浮 点方式存储。 2、实型量的运算: + (加 ) - (减) * (乘) / (实数除) 3、实型量的标准函数: abs-绝对值 sqr-平方 sqrt-开方 sin-正弦 cos-余弦 arctan反正切 exp-以e为底的指数 ln-自然对数 trunc-取整 round-舍入取整 例:|-3| 写为abs(-3) e2.5 写为exp(2.5) x y 写为exp(y*ln(x)) trunc(1.7)=1

(二)整型(integer)
1、整型量,包括正整数、负整数和零,即-32768至+32767。 例如:25 -32 0 2、整型量的运算: + (加) - (减) * (乘) DIV (整除) MOD(取余)

例:8 DIV 3=2 8 MOD 3=2 7 DIV 3=2 7 MOD 3=1 3、整型量的标准函数: abs-绝对值 sqr-平方 pred-前导 succ-后继 odd-奇函数 chr-取字符 例:pred(5)=4 odd(7)=true chr(65)=’A’ chr(97)=’a’

(三)字符型(char)

1、在Pascal语言中,字符量是由单个字符组成,所有字符来自ASCII字符集,共有256个字符。在程序中,通常用一 对单引号将单个字符括起来表示一个字符常量 ,如:'a','A','0'等 ;特殊地,对于单引号字符,则要表示成''''。对于 ASCII字符集中,按每个字符在字符集中的位置,将每个字符编号为0-255,编号称为对应字符的序号,因此字符也 存在大小,如:'A'<'a'、'b'>'a'
2、字符量的标准函数 Ord-取序号(与chr为反函数) pred-前导 succ-后继

例:ord(‘A’)=65 ord(‘a’)=97 pred(‘b’)=’a’ succ(‘a’)=’b’

(四)布尔型或逻辑型(boolean) 1、布尔型量仅有两个值,真和假,分别用标准常量名true和false表示 ,它们的序号分别为1和0。 2、布尔量的标准函数:Ord-取序号 pred-前导 succ-后继 3、布尔量的布尔运算(逻辑运算):and-与 or-或 not-非 说明:and 有并且之意, 只有当a与b都为true时,a and b 才为真,否则为假。 or 有或者之意, 当a与b之一为true时,a or b就为真,否则为假。 Not为非运算,取反值:not(true)=false 4、关系运算:<, <=(小于等于), =, >, >=(大于等于),<>(不等于) 例: 3<5值为true ‘a’>=’b’ 值为false (1>2) or (3>2) 值为true 三、基本语句 1、read / readln语句 ,强调区别。 格式:read(<变量表>) readln(<变量表>); 例:read(a,b,c); 2、write / writeln 语句 ;单双域宽输出格式。 格式:write(<输出表>) writeln(<输出表>) 例:writeln(‘s=’, s , ’v=’ , v :6:1); 3、表达式与赋值语句 形式:<变量>:=<表达式> 例:x:=sqrt(b*b-4*b*c); i:=i+1;

四、例题: 1、已知△ABC中的二边长a,b及夹角alfa,求第三边c和△ABC的面积。

2、输入二个数x , y,交换x与y的值。
3、输入一个字符,输出字符的序号、前导、后继。 4、输入x, y ,判断点(x,y)是否在圆环内。 若在环内,输出true;否则输出false。 (若1<=x2+y2<=4,则在环内)
0 1 2 x y

习题: 1、已知△ABC中的三边长分别为a,b,c,求△ABC的面积。 s=√p(p-a)(p-b)(p-c) 其中p=(a+b+c)/2 2、求一元二次方程ax2+bx+c=0的两个实数根。(保证有实数根)

3、输入三位字符,将其反向输出。例输入abc,输出cba。
4、输入一个三位整数,将其反向输出。例输入321,输出123。 5、输入经纬度(西经与南纬用负数表示),若在东北半球输出true,否则输出false。

2、选择结构(判断,分支) 限于篇幅,以下不再整理讲义。
if语句 IF语句是由一个布尔表达式和两个供选择的操作序列组成。运行时根据布尔表达式求值结果,选取其中之一的操作 序列执行。有两种形式的IF语句: if if <布尔表达式> <布尔表达式> then <语句>; then <语句1>

else <语句2>; 当if 语句嵌套时,Pascal约定else总是和最近的一个if配对。 case语句 case语句是由一个表达式和众多可选择的操作序列组成。运行时,根据表达式的求值结果,在众多的分支中选取一 个分支执行。其形式为: case 表达式 of 常量1:语句1; 常量2:语句2; …… 常量n:语句n; else 语句 n+1 {可选项} end; 复合语句 语句要用多个语句描述时,就必须用begin和 end括来,写成复合语句,当做一条语句用。

典型例题与习题:
例:求y=f(x),当x>0时, y=1,当x=0时,y=0,当 x<0时,y=-1 program lianxi; var x,y:real; begin if x>0 then y:=1; if x=0 then y:=0; if x<0 then y:=-1; writeln('y=',y);

例:当x>0时候,计算x*x, 并且输出x和x*x, program lianxie3; var x,x1:real; begin readln('x=',x); if x>= then begin x1:=x*x; writeln('x*x=',x1); writeln('x=',x); end; end.

例:根据学生的成绩给予相应的等低,对应关系 如下: 90——100 80——89 60——79 60以下 program chengji; var s:real;ch:char; begin write('input the score: '); readln(s); if(s>=0)and(s<=100)then case s div 10 of 10,9:ch:='B'; A B C D

end.

习题:
1、输入经纬度(西经与南纬用负数表示),输出所在半球。 2、判断某年是否闰年。 3、根据身高体重,判断体型。

8:ch:='B'; 7,6:='C'; else ch:='D'; end; writeln(s,'--',ch); end.

3、循环结构
while 布尔表达式 do 语句; Repeat 语句; until 布尔表达式; to 终值 do 语句; downto 终值 do 语句;

1、计算下列式子的值: (1)1+3+……+99 (2)1+2+4+8+……+128+256 2、输入一个整数,计算它各位上数字的和。(是任意位的整数) 3、输入一整数A,判断它是否质数。(提示:若从2到A的平方根的 范围内,没有一个数能整除A,则A是质数。) 4、求两个数的最小公倍数和最大公约数。(提示:公约数一定小 于等于两数中的小数,且能整除两数中的大数。公倍数一定大于等 于两数中的大数,且是大数的倍数,又能给两数中的小数整除。) 5、编写一个译码程序,把一个英语句子译成数字代码。译码规则 是以数字1代替字母A,数字2代替字母B,……,26代替字母Z,如 遇空格则打印一个星号‘*’,英文句子以‘.‘结束。 6、求水仙花数。所谓水仙花数,是指一个三位数abc,如果满足 a^3+b^3+c^3=abc,则abc是水仙花数。 7、“百钱买百鸡”是我国古代的著名数学题。题目这样描述:3文 钱可以买1只公鸡,2文钱可以买一只母鸡,1文钱可以买3只小鸡。 用100文钱买100只鸡,那么各有公鸡、母鸡、小鸡多少只?与之相 似,有"鸡兔同笼"问题。 8、输入一个正整数N,把它分解成质因子相乘的形式。 如:36=1 X 2 X 2 X 3 X 3; 19=1 X 19 (提示:设因子为I,从2开始到N,让N重复被I除,如果能整除, 则用商取代N,I为一个因子;如果不能整除,再将I增大,继续以上 操作,直到I等于N。) 9、宰相的麦子 :第一格一粒,第二格两粒,……,

for 控制变量:=初值 for 控制变量:=初值

goto 标号; (不要让学生用)

典型例题与习题:
计算从0到某个数之间所有奇数的和。 计算1+2+3+……+99+100 计算阶乘,N! 判断素数、验证歌德巴赫猜想 输出各种数列 求公约数,公倍数 ……

4、数组(一维)
数组的定义形式: array [<下标类型1>,……<下标类型n>] of <元素类型>

循环结构、数组综合练习题 1、 数学黑洞6174 已知:一个任意的四位正整数。将数字重新组合成一个最大的 数和最小的数相减,重复这个过程,最多七步,必得6174。 即:7641-1467=6174。将永远出不来。 求证:所有四位数数字(全相同的除外),均能得到6174。 输出掉进黑洞的步数。

E.基本算法处理: 1.初等算法(计数、统计、数学运算等) 2.排序算法(冒泡法、插入排序、合并排序) 3.查找(顺序查找、二分法) 4 .排列与组合 5 .高精度计算 有趣的题目: 约瑟夫环 :猴子选大王:一群(M)猴子排成一 列,数到N的退出,直到剩下一个。 狡兔三窟:狼捉兔,有10个洞。 神奇魔方:N*N奇数方。

2、 随机产生20个三位数,将这20个数按从小到大的顺序排列, 要求在排列中,用尽可能少的交换次数。

3、 输入10个学生的姓名,编一程序将它们按字母的顺序排列。

4、有一组数,其排列形式如下:11,19,9,12,5,20,1, 18,4,16,6,10,15,2,17,3,14,7,13,8,且尾部 8和头部11首尾相连,构成环形的一组数,编程找出相邻的4个 数,其相加之和最大,并给出它们的起始位置。

各种数字矩阵的填充。
八皇后问题的非递归解法。

5、 有一组数其排列顺序如下:(设有N个)3,6,11,45, 23,70,67,34,26,89,90,15,56,50,20,10。编 一程序交换这组数中任意指定的两段。

6、 输入一个十进制数,将其转换成二进制数。

5、函数与过程
function 函数名(形式参数表):函数类型; 说明部分; begin 语句1; …… 语句n end procedure 过程名(形式参数表); 说明部分; begin 执行语句; …… end; 形参和实参 值参数、变量参数 、无类型变量参数、子程序参数 标识符的作用域 1.全局变量和它的作用域 全局变量是指在程序开头的说明部分定义和说明的量。 它的作用域分为两种情况: (1)在全局变量和局部变量不同名时,其作用域是整个程序。 (2)在全局变量和局部变量同名时,全局变量的作用域不包 含同名局部变量的作用域。

2.局部变量和它的作用域
凡是在子程序内部使用的变量,必须在子程序中加入 说明。这种在子程序内部说明的变量称为局部变量。局部 变量的作用域是其所在的子程序。形式参数也只能在子程 序中有效。因此也属于局部变量。局部变量的作用域分为 两种情况: (1)当外层过程序的局部变量名和嵌套过程中的局部变量不 同名时,外层过程的局部变量作用域包含嵌套过琛。 (2)当外层过程的局部变量名和嵌套过程内的局部变量名同 名时,外层局部变量名的作用域不包含此过程。

标识符的作用域 1.全局变量和它的作用域 2.局部变量和它的作用域

到此,可解的题目将极度丰富。碰到具体问题时,插入下节的多维数组。
改进前面的题目解法:改为递归解法。如: 公约数与公倍数 阶乘 菲波那契 数列 典型的递归类题目: 汉诺塔:有三根塔,第一根塔上从小到大摆有n片铜 片,要求把这些铜片摆到第三根塔上.但大铜片不能 压在小铜片上面. 八皇后问题:在一个8*8的国际象棋棋盘上放置八个 皇后,使他们不互相攻击,求解的数量. 迷宫 跳马 一笔画、城市交通及最短线路选择 背包问题、装箱问题 快速排序 树的编历 都是些递归定义的 函数。 [递归的应用] 1.经典递归 例如hanoi塔问题:经典的递归,原问题包含子问题。有些 问题或者数据结构本来就是递归描述的,用递归做很自然。 2.递归与递推 利用递归的思想建立递推关系,如由兔子生崽而来的 fibonacci数列。但递推由于没有返回段,因此更为简单,有时 可以直接用循环实现。 3.分治 不少分治方法是源于递归思想,或是递归分解+合并处理。 4.回溯 规模较小的问题用回溯解决比较自然。注意递归前后要保 证现场的保存和恢复,即正确的转化问题。 5.动态规划 动态规划的子问题重叠性质与递归有某种相似之处。递归+ 动态修改查表是一种不错的建立动态规划模型的方法。 6.其他 其他么,就是不好归类。例如表达式处理,排列组合等。 附带说一下,用递归来处理打印方案的问题还是很方便的。

6、数组(多维)
数组的定义形式:
array [<下标类型1>,……<下标类型n>] of <元素类型> sample2=arrayp[1..5,1..5]of real;

通过前面的学习,引入多维数组将很自然,不多讲了。

用递归法的基本解题框架
体现的思想:化归,即把一个问题转化成另一个的方法。递归,它是转化成性质相似,但规模更小的问题。 [递归算法] Procedure try( 本步状态,深度等参量); 例:递归回溯法算法框架 procedure search(k:integer); begin if k=n+1 then begin 输出解 exit (如果只求一个解,改为halt; ) end; 保存:使用新状态之前的状态

Var 局部变量; Begin If 终止条件 then 跳出本过程; else If 找到目标 then 输出解;else For i:=1 to 本步可扩展的可能性 或者 本步的步骤 do Begin <保存现场。> 计算i步的初始状态; try(下步状态,深度+1); <恢复现场。> End;

for i:=1 to 状态数 do begin 计算状态i (应该去掉不能导致解的状态,也就是剪枝)
search(k+1); 恢复:使用本状态之前的状态 end; end;

End;

用递归法解题举例
八皇后问题:在一个8*8的国际象棋棋盘上放置八个皇 后,使他们不互相攻击,求解的数量. [递归算法] Procedure try( 本步状态,深度等参量);

Var 局部变量; Begin If 终止条件 then 跳出本过程; else If i=8 (找到目标) then 输出解;else For i:=1 to 8(共8个位置可放 )do Begin <保存现场。> 计算i步的初始状态; try(下步状态,深度+1); <恢复现场。> End;

End;

program eightqueens; var x:array[1..8] of integer; a,b,c:array[-7..16] of boolean; i:integer; procedure print; var k:integer; begin for k:=1 to 8 do write(x[k]:4); writeln; end; procedure try(i:integer); var j:integer; begin for j:=1 to 8 do if a[j] and b[i+j] and c[i-j] then begin x[i]:=j; a[j]:=false; b[i+j]:=false; c[i-j]:=false; if i<8 then try(i+1) else print; a[j]:=true; b[i+j]:=true; c[i-j]:=true end end; begin for i:=-7 to 16 do begin a[i]:=true; b[i]:=true; c[i]:=true try(1); end.

end;

用递归法解题举例
汉诺塔:有三根塔,第一根塔上从小到大摆有n片铜片, 要求把这些铜片摆到第三根塔上.但大铜片不能压在小 铜片上面. [递归算法] Procedure try( 本步状态,深度等参量);

program hanoi(input,output); var total:integer; procedure move(n,a,b,c:integer); begin if n=1 then write(a,'->',c,' else begin move(n-1,a,c,b); write(a,'->',c,' '); ')

Var 局部变量; Begin <If n=0 终止条件 then 跳出本过程; else>此处略。 If n=1 (最小规模) then 直接输出;else < For i:=1 to 3 do >(本步可分3步走,不用for )

Begin
<保存现场。> <计算i步的初始状态;> try(降规模,n-1);本步分3步: <恢复现场。> end; begin

move(n-1,b,a,c) end

read(total); writeln('move disk:',total); move(total,1,2,3) end.

End;
End;

program jump; var 用递归法解题举例 h:array[-1..7,-1..7] of integer; a,b:array[1..8] of integer; 跳马问题: 在5*5格的棋盘上,有一个国家象棋的马, i,j,num:integer; 它可以朝8个方向跳,但不允许出界或跳到已跳过的 procedure print;(输出过程略) 格子上,要求在跳遍整个棋盘后再条回出发点。 procedure try(x,y,i:integer); var j,u,v:integer; [递归算法] begin Procedure try( 本步状态,深度等参量); for j:=1 to 8 do begin Var 局部变量; u:=x+a[j]; v:=y+b[j]; Begin if h[u,v]=0 then begin If 终止条件 then 跳出本过程; else h[u,v]:=i; If i=25 (找到目标) then 输出解;else if i<25 then try(u,v,i+1) else print; h[u,v]:=0 For i:=1 to 8(8个方向 )do end; Begin end; end; <保存现场。> begin 这种边界处理方法, 计算i步的初始状态; for i:=-1 to 7 do 要学生掌握。 for j:=-1 to 7 do try(下步状态,深度+1); if (i>=1)and(i<=5)and(j>=1)and(j<=5) then h[i,j]:=0 <恢复现场。> else h[i,j]:=1; a[1]:=2;b[1]:=1; a[2]:=1;b[2]:=2; a[3]:=-1;b[3]:=2; End; 这种状态处理方法, a[4]:=-2;b[4]:=1; a[5]:=-2;b[5]:=-1; a[6]:=-1;b[6]:=-2; 要学生掌握。 a[7]:=1;b[7]:=-2; a[8]:=2;b[8]:=-1; num:=0; h[1,1]:=1; End; try(1,1,2); writeln('num=',num); end.

用递归法解题举例
迷宫问题: 类似于跳马问题。

[递归算法] Procedure try( 本步状态,深度等参量);

Var 局部变量; Begin If 终止条件 then 跳出本过程; else

If 出口 (找到目标) then 输出解;else
For i:=1 to 4(4个方向 )do Begin <保存现场。> 计算i步的初始状态;

try(下步状态,深度+1);
<恢复现场。> End;

End;

program p7t20(input,output); var a:array[1..25,1..80] of integer; b:array[1..4,1..2] of integer; i,j,m,n,m1,n1,m2,n2:integer; procedure print; ;(输出过程略) procedure try(x,y,k:integer); var u,v,i:integer; begin for i:=1 to 4 do begin u:=x+b[i,1]; v:=y+b[i,2]; if (u>0) and (u<=m) and (v>0) and (v<=n) and (a[u,v]=0) then begin a[u,v]:=k; if (u=m2) and (v=n2) then print else try(u,v,k+1); a[u,v]:=0; end; end; end; begin assign(input,'p7t20.txt'); reset(input); readln(m,n,m1,n1,m2,n2); for i:=1 to m do for j:=1 to n do read(a[i,j]); b[1,1]:=-1; b[1,2]:=0; b[2,1]:=1; b[2,2]:=0; b[3,1]:=0; b[3,2]:=-1; b[4,1]:=0; b[4,2]:=1; a[m1,n1]:=2; try(m1,n1,3); end.

用递归法解题举例
爬楼梯问题: 共m步楼梯,每步可走1-3步,多少走法?

[递归算法] Procedure try( 本步状态,深度等参量);

Var 局部变量; Begin If p+i>m终止条件 then 跳出本过程; else

If p+i=m (找到目标) then 输出解;else
For i:=1 to 3(3种走法 )do Begin <保存现场。> 计算i步的初始状态;

try(下步状态,深度+1);
<恢复现场。> End;

End;

program p7tlt(input,output); var a:array[1..20] of integer; m,i,s:integer; procedure print(k:integer); var i:integer; begin s:=s+1; for i:=1 to k do write(a[i]:3); writeln; end; procedure try(p,k:integer); var i:integer; begin for i:=1 to 3 do begin if (p+i=m) then begin a[k]:=i; print(k); a[k]:=0; end; if (p+i<m) then begin a[k]:=i; try(p+i,k+1); a[k]:=0; end; end; end; begin read(m); s:=0; for i:=1 to 20 do a[i]:=0; try(0,1); writeln('total:',s); end.

一笔画、城市交通及最短线路选择
主要是数据模型的建立 a [递归算法] Procedure try( 本步状态,深度等参量);

Var 局部变量; Begin If 终止条件 then 跳出本过程; else

b

f

e

If 找到目标 then 输出解;else For i:=1 to 本步可扩展的可能性 或者 本步的步骤 do Begin

c 010001 101101 010100 011011 000101

d

<保存现场。> 计算i步的初始状态; try(下步状态,深度+1); <恢复现场。> End;

End;

110110

背包问题、装箱问题
[递归算法] function max( 本步状态,深度等参量); Var 局部变量; Begin If 终止条件 then 跳出本过程; else If 找到目标 then 输出解;else For i:=1 to 本步可扩展的可能性 或者 本步的步骤 do

Begin
<保存现场。> 计算i步的初始状态; try(下步状态,深度+1); <恢复现场。>

End;

End;

记忆化可以把重量记录,用一个二维数组:f[i,j],代表到第i个物品为止, j个重量的最小价值://30个物品,最大10000重量 var f:array[0..30,0..10000] of longint; w,v:array[1..30] of longint; n,m,i,j:longint; function max(a,b:longint):longint; begin if a>b then exit(a) else exit(b); end; function get(i,j:longint):longint; var t:longint; begin if (i<1) then exit(0); if f[i,j]<0 then begin if j<w[i] then t:=get(i-1,j) else t:=max(get(i-1,j),get(i-1,j-w[i])+v[i]); f[i,j]:=t; end; exit(f[i,j]); end; begin assign(input,'package.in'); assign(output,'package.out'); reset(input);rewrite(output); readln(m,n); for i:=1 to n do readln(w[i],v[i]); fillchar(f,sizeof(f),255); writeln(get(n,m)); close(input);close(output); end.

8、指针、文件操作
program iotest(input,output); var i:integer; a:array [1..10] of integer; begin assign(input,'input1.in'); assign(output,'output1.out'); reset(input); reset(output); rewrite(output); for i:=1 to 10 do read(a[i]); for i:=1 to 10 do writeln(a[i]); close(input); close(output); end.


推荐相关:

学习经验交流会活动策划-

学习经验交流会活动策划-_营销/活动策划_计划/解决方案_实用文档。信息科学与...5、由白楠学长讲解大学生活中存在的各种活动,各类科技 竞赛及学生会活动,并...


教学信息员交流会笔记

教​学​信​息​员​交​流​会​笔​记 暂无评价|0人阅读|0次下载|举报文档教学信息交流会笔记小站方面一、信息收集的方法(建议) 1. 走访...


信息系学习经验交流会

让他们能尽快熟悉大 学校园的生活和学习,我们特邀请了信息系中优秀的学生代表,...3、通过举办此次经验交流会,调动新生学习的积极性和自觉 性,提高课堂的出勤率。...


教学信息员交流会策划书12月

广西师范大学教育科学学院教学信息交流会策划书一、活动背景 教学信息员从事教学第一信息与反馈,他们能够深入学生群体,帮助教师了解他们的教 学情况,为学校提供真实的...


学习交流会策划书

四川工商职业技术学院信息工程系 学习交流会 策划书 ...锻炼同 学们的学习能力;活跃学院人文气氛,提高同学...? 各位参加程序设计大赛, 计算机作品大赛获奖的选手...


学习经验交流会简报

从而使他们更好的适应大学的学习和生活,信息学院 学习部组织了“学海撷英”学习经验交流会,本次交流会计划召开 三次,分别面向 07 级信管专业,07 级电子通信专业...


信息交流会

信息交流会_其它_总结/汇报_实用文档。互学互进,努力使经管系信息宣传工作再上新台阶——经管系举行团学信息宣传工作交流会 为进一步深入学习贯彻落实经管系“践行...


学习经验交流会策划书

学习经验交流会策划书_营销/活动策划_计划/解决方案_实用文档。策划书 信息工程...介绍到场的学长; 2.由学长学姐按顺序介绍自己的学习心得, 并指出哪些地方时...


学习经验交流会策划书

学习经验交流会策划书_营销/活动策划_计划/解决方案_实用文档。学习经验交流会 ...山西农业大学信息学院人文系学生会 承办单位:山西农业大学信息学院人文系学生会...


榜样交流学习会圆满结束

苗园莉和张俊 成同学, 2015 级电子信息学院辅导员陈林老师以及部分 2015 级同学...此次交流会群贤毕集,大家面对面交流,心与心沟通,思想与思 想碰撞。 学长学姐...

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