信息学竞赛辅导交流会

1、信息学竞赛辅导交流会新昌县城关中学新昌县人民政府信息网络管理中心梁一锋梁一锋2010-06-21何林同学给吴文虎教授的一封信何林同学给吴文虎教授的一封信摘录摘录 如果有人问我，这五年的信息学生涯教会了我什么，我不会说“我会用平衡二叉树”、也不会说“我学懂了动态规划”。我不管学到多少，总还有很多没学到；即便是学会了的东西，长时间不用也会遗忘。我认为我真正学到的是习惯、态度和方法。我学会了批判性的看问题、我学会了用开阔的胸怀去接受所有不同的想法、我学会了分析问题、总结问题、乃至提出问题的一系列方法和经验。这些才是无价之宝，是一辈子在任何地方任何时候都不会丢的宝贝。 全国青少年信息学奥林匹克联赛(N

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

3、竞赛形式和成绩评定联赛分两个年龄组：初中组和高中组。每组竞赛分两轮：初试和复试。 初试形式为笔试，侧重考察学生的计算机基础知识和编程的基本能力，并对知识面的广度进行测试。程序设计的描述语言采用Basic（2005年被取消）、C/C+或Pascal。各省市初试成绩在本赛区前百分之十五的学生进入复赛，其分数不计入复赛的成绩。初赛时间为10月的最后第二个星期六下午 2:30 - 16:30举行。 复试形式为上机，侧重考察学生对问题的分析理解能力，数学抽象能力，驾驭编程语言的能力和编程技巧、想象力和创造性等。程序设计语言可采用Basic（2005年后被取消）、Pascal、C或C+。各省市竞赛的等第奖

4、在复试的优胜者中产生。时间为 3小时。只进行一试，约在当年的11 月的第三个周六进行。 试题形式试题形式 每次联赛的试题分四组：初中组初试赛题；初中组复试赛题；高中组初试赛题；高中组复试赛题。其中，初中组初试赛题和高中组初试赛题类型相同，初中组复试赛题和高中组复试赛题类型相同，但初中组和高中组的题目不完全相同，高中组难度略高；以体现年龄特点和层次要求。 初试：初试全部为笔试，满分100分。试题由四部分组成：1、选择题：共20题，每题15分，共30分。每题有4个备选方案。试题内容包括计算机基本组成与原理、计算机基本操作、信息科技与人类社会发展的关系等等。2、问题求解题：共2题，每题5分，共10分

5、。试题给出一个叙述较为简单的问题，要求学生对问题进行分析，找到一个合适的算法，并推算出问题的解。答案以字符串方式给出，考生给出的答案与标准答案的字符串相同，则得分；否则不得分。3、程序阅读理解题：共4题，每题8分，共32分。题目给出一段程序（没有关于程序功能的说明），有时也会给出程序的输入，要求考生通过阅读理解该段程序给出程序的输出。输出以字符串的形式给出，如果与标准答案一致，则得分；否则不得分。4、程序完善题：共 2题，第一题10分，共4空，每空2.5分；第二题18分，共6空，每空3分。两题共28分。题目给出一段关于程序功能的文字说明，然后给出一段程序代码，在代码中略去了若干个语句并在这些位

6、置给出空格，要求考生根据程序的功能说明和代码的上下文，填出被略去的语句。填对的，则得分；否则不得分。（2009年普及组试题为第一题5空，每空3分，第二题前三空每空3分，后两空每空2分） 竞赛形式和成绩评定竞赛形式和成绩评定*复试：复试的题型和形式向全国信息学奥赛（NOI）靠拢，全部为上机编程题，但难度略低。复试为决出竞赛成绩的最后一个环节。题目包括 4道题，每题100分，共计400分。难度有易有难，既考虑普及面，又考虑选拔的梯度要求。每一道试题包括：题目、问题描述、样例说明（输入、输出及必要的说明）、数据范围（数据限制条件）。测试时，测试程序为每道题提供了十组测试数据，考生程序每答对一组得10

7、 分；累计分即为该道题的得分。竞赛形式和成绩评定竞赛形式和成绩评定讨论与交流：应该侧重于初赛还是复赛？讨论与交流：应该侧重于初赛还是复赛？试题的知识范围具体如下：试题的知识范围具体如下： 初赛内容与要求：初赛内容与要求：复赛内容与要求：复赛内容与要求：A计算机的基本常识：B计算机的基本操作： C数据结构：1程序语言中基本数据类型(字符、整数、长整数、浮点) 2. 浮点运算中的精度和数值比较 3一维数组（串）与线性表 4记录类型（PASCAL）/ 结构类型（C） C数据结构：1指针类型 2多维数组3单链表及循环链表 4二叉树5文件操作（从文本文件中读入数据，并输出到文本文件中） 在初赛的内容上增

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

9、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 Wi

10、ndows版、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、其他算法讲解复赛辅导：以历年复赛试

11、题的解题为主。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、标识

12、符以字母开头的字母、数字组合。自己定义，例如：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, tru

13、nc过程：get, new, pack, page, put, read, readln, reset, rewrite, unpack, write, writeln程序结构例1 ：已知半径，求圆周长和面积的程序 数学公式：l=2r s=r2PROGRAM 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、常量定义：CONST pi:=3.1415926;定义一个常量pi， 值为3.14159262

14、、变量定义：r,l,s:real;定义了半径r,周长l,面积s,三个变量，类型为实型数据。3、表达式： 2r 2*pi*r r2 pi*r*r b2-4ac b*b-4*a*c a+b (a+b)/2 24、输入输出语句：read(r) 从键盘输入一个数，赋给变量rwrite(r, l, s) 把r,l,s,的值输出到屏幕。5、标点符号的写法：整个程序一个句号，在最后 END.每句语句后一个分号；逗号用来分隔分量等:= 是一个赋值号6、整个程序的书写格式：保留字大写；缩进格式。选用的习题：1、输入三个数，计算并输出它们的平均值及三个数的乘积。2、已知地球半径为6371km，计算并输出地球的表面

15、积和体积。3、已知匀加速运动的初速度为10m/s,加速度为2m/s2,求20s以后的速度，20s内走过的路程及平均速度。4、已知物体的质量为m，求其在地球和月球受到的重力。1、顺序结构、顺序结构一、用计算机解题的基本方法-“自顶而下，逐步求精”上节的简单程序已体现出处理问题步骤、思路的顺序关系，这就是顺序结构程序。解题时，对问题有一清楚了解，再仔细构造解题步骤算法。算法可以“自顶而下，逐步求精”。对大问题先构造大致轮廓，再逐步分解成小问题，直到可以用PASCAL语言描述出来。二、基本标准数据类型 （一）实型（real）1、简介：包括正实数、负实数和实数零，其实就是常说的小数，pascal中表示

16、实型数的形式有两种。十进制表示法：这是人们日常使用的带小数点的表示方法，如0.0、-0.0、+5.61、-8.0、-6.050等都是实型常量，而0.、.37都不是合法的实数形式科学记数法：采用指数形式的表示方法，如1.25105可表示成1.25E+05。在科学记数法中，字母E表示10这个底数，而E之前为一个十进制表示的小数，称为尾数，E之后必须为一个整数，称为指数。如-1234.56E+26、+0.268E-5 、1E5是合法形式，而.34E12、2.E5、E5、E、1.2E+0.5都不是合法形式的实数。 无论实数是用十进制表示法还是科学表示法，它们在计算机内的表示形式是一样的，总是用浮点方式

17、存储。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 02、整型量的运算： (加) (减) (乘) DIV (整除) MOD（取余）例：8 DIV 3=2 8

18、 MOD 3=2 7 DIV 3=2 7 MOD 3=13、整型量的标准函数：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字符集中，按每个字符在字符集中的位置，将每个字符编号为0255，编号称为对应字符的序号

19、，因此字符也存在大小，如：Aa2、字符量的标准函数 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

20、之一为true时，a or b就为真，否则为假。 Not为非运算，取反值：not(true)=false 4、关系运算：, , =(大于等于),(不等于)例： 3=b 值为false (12) or (32) 值为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

21、:=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，则在环内)习题：1、已知ABC中的三边长分别为a,b,c，求ABC的面积。s=p(p-a)(p-b)(p-c) 其中p=(a+b+c)/22、求一元二次方程ax2+bx+c=0的两个实数根。（保证有实数根）3、输入三位字符，将其反向输出。例输入abc，输出cba。4、输入一个三位整数，将其

22、反向输出。例输入321，输出123。5、输入经纬度（西经与南纬用负数表示），若在东北半球输出true,否则输出false。0 1 2 xy2、选择结构（判断，分支）、选择结构（判断，分支）限于篇幅，以下不再整理讲义。限于篇幅，以下不再整理讲义。if语句语句IF语句是由一个布尔表达式和两个供选择的操作序列组成。运行时根据布尔表达式求值结果，选取其中之一的操作序列执行。有两种形式的IF语句：ifthen ；ifthen else ； 当if 语句嵌套嵌套时，Pascal约定else总是和最近的一个if配对。 case语句语句case语句是由一个表达式和众多可选择的操作序列组成。运行时，根据表达式的

23、求值结果，在众多的分支中选取一个分支执行。其形式为：case表达式of常量1：语句1；常量2：语句2；常量n：语句n；else语句 n+1 可选项 end;复合语句复合语句 语句要用多个语句描述时，就必须用begin和 end括来，写成复合语句，当做一条语句用。 典型例题与习题：典型例题与习题：例：求y=f(x),当x0时，y=1，当x=0时，y=0，当x0 then y:=1;if x=0 then y:=0;if x0时候，计算x*x，并且输出x和x*x，program lianxie3;var x,x1:real;beginreadln(x=,x);if x= then beginx1:

24、=x*x;writeln(x*x=,x1);writeln(x=,x);end;end.例：根据学生的成绩给予相应的等低，对应关系如下：以下program chengji;var s:real;ch:char;beginwrite(input the score: );readln(s);if(s=0)and(s=100)thencase s div 10 of10,9:ch:=B;8:ch:=B;7,6:=C;else ch:=D;end;writeln(s,-,ch);end. 习题：习题：1、输入经纬度（西经与南纬用负数表示），输出所在半球。2、判断某年是否闰年。3、根据身高体重，判断体

25、型。3、循环结构、循环结构while 布尔表达式do语句；Repeat语句; until布尔表达式；for 控制变量：初值to终值do语句；for 控制变量：初值downto终值do语句；goto标号； （不要让学生用）典型例题与习题：典型例题与习题：计算从到某个数之间所有奇数的和。 计算1+2+3+99+100 计算阶乘，N！判断素数、验证歌德巴赫猜想输出各种数列求公约数，公倍数1、计算下列式子的值：（1）1+3+99 （2）1+2+4+8+128+2562、输入一个整数，计算它各位上数字的和。（是任意位的整数）3、输入一整数A，判断它是否质数。（提示：若从2到A的平方根的范围内，没有一个数

26、能整除A，则A是质数。）4、求两个数的最小公倍数和最大公约数。（提示：公约数一定小于等于两数中的小数，且能整除两数中的大数。公倍数一定大于等于两数中的大数，且是大数的倍数，又能给两数中的小数整除。）5、编写一个译码程序，把一个英语句子译成数字代码。译码规则是以数字1代替字母A，数字2代替字母B，26代替字母Z，如遇空格则打印一个星号*，英文句子以.结束。6、求水仙花数。所谓水仙花数，是指一个三位数abc，如果满足a3+b3+c3=abc，则abc是水仙花数。 7、“百钱买百鸡”是我国古代的著名数学题。题目这样描述：3文钱可以买1只公鸡，2文钱可以买一只母鸡，1文钱可以买3只小鸡。用100文钱买

27、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、宰相的麦子 ：第一格一粒，第二格两粒， 4、数组（一维）、数组（一维）数组的定义形式：array ， of E基本算法处理：基本算法处理：1初等算法（计数、统计、数学运算等）2排序算法（冒泡法、插入排序、合并排序） 3查找（顺序查找、二分法）4 排列与组合5 高

28、精度计算循环结构、数组综合练习题循环结构、数组综合练习题1、 数学黑洞6174已知：一个任意的四位正整数。将数字重新组合成一个最大的数和最小的数相减，重复这个过程，最多七步，必得6174。即：7641-1467=6174。将永远出不来。求证：所有四位数数字（全相同的除外），均能得到6174。输出掉进黑洞的步数。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

29、，且尾部8和头部11首尾相连，构成环形的一组数，编程找出相邻的4个数，其相加之和最大，并给出它们的起始位置。5、 有一组数其排列顺序如下：（设有N个）3，6，11，45，23，70，67，34，26，89，90，15，56，50，20，10。编一程序交换这组数中任意指定的两段。6、 输入一个十进制数，将其转换成二进制数。有趣的题目：有趣的题目：约瑟夫环 ：猴子选大王:一群(M)猴子排成一列,数到N的退出,直到剩下一个。狡兔三窟：狼捉兔，有10个洞。神奇魔方：N*N奇数方。各种数字矩阵的填充。八皇后问题的非递归解法。5、函数与过程、函数与过程function函数名(形式参数表):函数类型；说明部

30、分；begin语句1;语句nendprocedure 过程名(形式参数表); 说明部分; begin 执行语句; end;形参和实参 值参数、变量参数 、无类型变量参数、子程序参数 标识符的作用域1.全局变量和它的作用域2.局部变量和它的作用域 标识符的作用域1.全局变量和它的作用域全局变量是指在程序开头的说明部分定义和说明的量。它的作用域分为两种情况：(1)在全局变量和局部变量不同名时，其作用域是整个程序。(2)在全局变量和局部变量同名时，全局变量的作用域不包含同名局部变量的作用域。2.局部变量和它的作用域凡是在子程序内部使用的变量，必须在子程序中加入说明。这种在子程序内部说明的变量称为局部

31、变量。局部变量的作用域是其所在的子程序。形式参数也只能在子程序中有效。因此也属于局部变量。局部变量的作用域分为两种情况：(1)当外层过程序的局部变量名和嵌套过程中的局部变量不同名时，外层过程的局部变量作用域包含嵌套过琛。(2)当外层过程的局部变量名和嵌套过程内的局部变量名同名时，外层局部变量名的作用域不包含此过程。 到此，可解的题目将极度丰富。碰到具体问题时，插入下节的多维数组。到此，可解的题目将极度丰富。碰到具体问题时，插入下节的多维数组。典型的递归类题目：典型的递归类题目：汉诺塔：有三根塔,第一根塔上从小到大摆有n片铜片,要求把这些铜片摆到第三根塔上.但大铜片不能压在小铜片上面. 八皇后问

32、题:在一个8*8的国际象棋棋盘上放置八个皇后,使他们不互相攻击,求解的数量. 迷宫跳马一笔画、城市交通及最短线路选择背包问题、装箱问题快速排序树的编历改进前面的题目解法：改为递归解法。如：改进前面的题目解法：改为递归解法。如：公约数与公倍数阶乘菲波那契 数列递归的应用递归的应用1.经典递归例如hanoi塔问题：经典的递归，原问题包含子问题。有些问题或者数据结构本来就是递归描述的，用递归做很自然。2.递归与递推利用递归的思想建立递推关系，如由兔子生崽而来的fibonacci数列。但递推由于没有返回段，因此更为简单，有时可以直接用循环实现。3.分治不少分治方法是源于递归思想，或是递归分解+合并处理

33、。4.回溯规模较小的问题用回溯解决比较自然。注意递归前后要保证现场的保存和恢复，即正确的转化问题。5.动态规划动态规划的子问题重叠性质与递归有某种相似之处。递归+动态修改查表是一种不错的建立动态规划模型的方法。6.其他其他么，就是不好归类。例如表达式处理，排列组合等。附带说一下，用递归来处理打印方案的问题还是很方便的。都是些递归定义的函数。6、数组（多维）、数组（多维）数组的定义形式：array ， of sample2=arrayp1.5,1.5of real；通过前面的学习，引入多维数组将很自然，不多讲了。通过前面的学习，引入多维数组将很自然，不多讲了。用递归法的基本解题框架用递归法的基本

34、解题框架例：递归回溯法算法框架procedure search(k:integer);begin if k=n+1 then begin 输出解 exit (如果只求一个解，改为halt; ) end; 保存：使用新状态之前的状态for i:=1 to 状态数 do begin 计算状态i (应该去掉不能导致解的状态,也就是剪枝) search(k+1); 恢复：使用本状态之前的状态 end;end;递归算法Procedure try( 本步状态，深度等参量);Var 局部变量；Begin If 终止条件 then 跳出本过程; else If 找到目标 then 输出解;else For i

35、:=1 to 本步可扩展的可能性 或者 本步的步骤 do Begin 计算i步的初始状态； try(下步状态,深度+1); End;End;体现的思想：化归，即把一个问题转化成另一个的方法。递归，它是转化成性质相似，但规模更小的问题。用递归法解题举例用递归法解题举例八皇后问题八皇后问题:在一个8*8的国际象棋棋盘上放置八个皇后,使他们不互相攻击,求解的数量. program eightqueens;varx:array1.8 of integer;a,b,c:array-7.16 of boolean;i:integer;procedure print;var k:integer;beginf

36、or k:=1 to 8 do write(xk:4);writeln;end;procedure try(i:integer);var j:integer;beginfor j:=1 to 8 doif aj and bi+j and ci-j then beginxi:=j;aj:=false;bi+j:=false;ci-j:=false;if i8 then try(i+1)else print;aj:=true;bi+j:=true;ci-j:=trueendend;beginfor i:=-7 to 16 dobeginai:=true;bi:=true;ci:=trueend;t

37、ry(1);end. 递归算法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;用递归法解题举例用递归法解题举例汉诺塔：汉诺塔：有三根塔,第一根塔上从小到大摆有n片铜片,要求把这些铜片摆到第三根塔上.但大铜片不能压在小铜片上面. program hanoi(input,output);var total:integer;pr

38、ocedure 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, ); move(n-1,b,a,c) end end;begin read(total); writeln(move disk:,total); move(total,1,2,3) end.递归算法Procedure try( 本步状态，深度等参量);Var 局部变量；Begin 此处略。 If n=1 (最小规模) then 直接输出;else （本步可分3步走，不用for ） Beg

39、in try(降规模,n-1);本步分3步: End;End;用递归法解题举例用递归法解题举例跳马问题跳马问题: 在5*5格的棋盘上，有一个国家象棋的马，它可以朝8个方向跳，但不允许出界或跳到已跳过的格子上，要求在跳遍整个棋盘后再条回出发点。 program jump;varh:array-1.7,-1.7 of integer; a,b:array1.8 of integer; i,j,num:integer; procedure print;(输出过程略) procedure try(x,y,i:integer); var j,u,v:integer; begin for j:=1 to

40、8 do begin u:=x+aj; v:=y+bj; if hu,v=0 then begin hu,v:=i; if i=1)and(i=1)and(j=5) then hi,j:=0 else hi,j:=1; a1:=2;b1:=1; a2:=1;b2:=2; a3:=-1;b3:=2; a4:=-2;b4:=1; a5:=-2;b5:=-1; a6:=-1;b6:=-2; a7:=1;b7:=-2; a8:=2;b8:=-1; num:=0; h1,1:=1; try(1,1,2); writeln(num=,num);end. 递归算法Procedure try( 本步状态，深度

41、等参量);Var 局部变量；Begin If 终止条件 then 跳出本过程; else If i=25 (找到目标) then 输出解;else For i:=1 to 8（8个方向 ）do Begin 计算i步的初始状态； try(下步状态,深度+1); End;End;这种边界处理方法，要学生掌握。这种状态处理方法，要学生掌握。用递归法解题举例用递归法解题举例迷宫问题迷宫问题: 类似于跳马问题。 program p7t20(input,output); var a:array1.25,1.80 of integer; b:array1.4,1.2 of integer; i,j,m,n,

42、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+bi,1; v:=y+bi,2; if (u0) and (u0) and (v=n) and (au,v=0) then begin au,v:=k; if (u=m2) and (v=n2) then print else try(u,v,k+1); au,v:=0; end; end; end;begin assign(input,

43、p7t20.txt); reset(input); readln(m,n,m1,n1,m2,n2); for i:=1 to m do for j:=1 to n do read(ai,j); b1,1:=-1; b1,2:=0; b2,1:=1; b2,2:=0; b3,1:=0; b3,2:=-1; b4,1:=0; b4,2:=1; am1,n1:=2; try(m1,n1,3); end.递归算法Procedure try( 本步状态，深度等参量);Var 局部变量；Begin If 终止条件 then 跳出本过程; else If 出口 (找到目标) then 输出解;else Fo

44、r i:=1 to 4（4个方向 ）do Begin 计算i步的初始状态； try(下步状态,深度+1); End;End;用递归法解题举例用递归法解题举例爬楼梯问题爬楼梯问题: 共m步楼梯，每步可走1-3步，多少走法？ program p7tlt(input,output); var a:array1.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(ai: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 ak:=i; print(k); ak:=0; end; if (