1、一、棋盘类题目1.马拦过河卒 中学高级本（紫皮）P2、奥赛精解练习题P266 页棋盘上 A（0,0）点有一个过河卒，需要走到目标 B（n，m）点。卒街的规则：可以向下、或者向右。同时在棋盘上 C 点有一个对方的马，该马所在点及所有跳跃一步可达点称为马的控制点。因此称之为“马拦过河卒”。输入：一行四个数据，表示 B 点和 C 点马的坐标，n、m 均为不超过 15 的整数。输出：一个数据，表示所有的路径数。【分析】遍历每个点的路径，A 点所在行及列上点的路径均为 1，马的 9 个控制点的路径均为 0，其余每个点的路径为 ax,y:=ax,y-1+ax-1,y。2.设有一个 n*m 方格的棋盘（1m
2、,n100）。求出该棋盘中包含多少个正方形、多少个长方形（不包括正方形）。(Noip97-1)例如：当 n=2，m=3 时，正方形的个数有 8 个；即边长为 1 的正方形有 6个； 边长为 2 的正方形有 2 个。长方形的个数有 10 个；即 2*1 的长方形有4 个；1*2 的长方形有 3 个；3*1 的长方形有 2 个； 3*2 的长方形有 1 个。程序要求：输入：n 和 m 输出：正方形的个数与长方形的个数如上例：输入：2 3 输出：8，10【分析】二、贪心算法 中学高级本（紫皮）P221.排队接水有 n 个人在一个水龙头前排队接水，假如每个人接水的时间为 Ti，请编程找出这 n 个人排
3、队的一种顺序，使得 n 个人的平均等待时间最小。输入：输入文件共 2 行，第一行为 n；第二行为每个人的接水等待时间输出：文件为 2 行，第一行为排队顺序，第二行为平均等待时间。2.智力大冲浪智力大冲浪节目，奖励每个参赛者 m 元，首先比赛时间为 n 个时段(n0 do BeginI:=1;While (i1) and (n1=0) do delete(n,1,1)输出 n;2.合并果子奥赛经典金钥匙P58 页在一个果园里，所有果子已经打下来，分成不同数目的堆，多多决定把所有果子合并为一堆。每一次可以合并两堆，消耗体力等于两堆果子重量之和。经过 n-1 次合并后，就剩下一堆，还要再搬回家，所以
4、要尽量的节省体力，设计出合并的方案，使消耗体力最少，并输出最小的体力耗费值。例如:有 3 种果子，数目依次为 1，2，9。可以先 1、2 堆合并，新堆数目为 3，耗费体力 3，再将新堆与 3 堆合并，新堆数目为 12，耗费体力为12，总共耗费体力=3+12=15。输入：两行，第一行整数 n（1b+a 则 abA: array1.10000 of string;X：integer;Readln(f,n);For i:=1 to n doBegin Read(f,x); str(x,ai); End;For i:=1 to n-1 doFor j:=i+1 do n doIf ai+ajAj+1，
5、完成插入；否则，将 Aj后移一个位置：Aj-Aj+1；j=j-1；继续执行；Procedure insertsort(n:integer);VAR i,j:integer;BeginFor i:=2 to n do Begin a0:=ai; J:=i-1;While aja0 do begin aj+1:=aj; j:=j-1; end;aj+1:=a0;end;end;2.交换排序冒泡排序 奥赛精解练习题 P166 页Program bubble(n:integer);Var temp,i,j:integer;Change:boolean;BeginFor i:=1 to n-1 doBe
6、gin change:=false;For j:=n-1 downto i doIf ajaj+1 then Begin change:=true;temp:=aj; aj:=aj+1; aj+1:=temp;end;if not(change) then exit;end;end;3.交换排序快速排序 奥赛精解练习题 P167 页在 a1.n中任取一个数据元素作为比较的“基准” （记为 x）,将数据区划分为左右两个部分：a1.i-1和 ai+1,n，且 a1.i-1 xai+1.n(1in)，当 a1.i-1和 ai+1.n非空时，分别对它们进行上述的划分过程，直至所有数据元素均已排序为止。
7、设要排序的数组是 A0AN-1，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。 一趟快速排序的算法是： 1）设置两个变量 I、J，排序开始的时候：I=0，J=N-1； 2）以第一个数组元素作为关键数据，赋值给 key，即 key=A0； 3）从 J 开始向前搜索，即由后开始向前搜索（J=J-1 即 J-） ，找到第一个小于 key 的值 Aj，Aj与 Ai交换； 4）从 I 开始向后搜索，即由
8、前开始向后搜索（I=I+1 即 I+） ，找到第一个大于 key 的 Ai，Ai与 Aj交换； 5）重复第 3、4、5 步，直到 I=J； (3,4 步是在程序中没找到时候 j=j-1，i=i+1，直至找到为止。找到并交换的时候 i， j 指针位置不变。另外当i=j 这过程一定正好是 i+或 j-完成的最后令循环结束。 ） 示例：待排序的数组 A 的值分别是：（初始关键数据：key=49） 注意关键 key 永远不变，永远是和 key 进行比较，无论在什么位置，最后的目的就是把 key 放在中间，小的放前面大的放后面。 A0 A1 A2 A3 A4 A5 A649 38 65 97 76 13
9、 27进行第一次交换后：27 38 65 97 76 13 49 ( 按照算法的第三步从后面开始找，此时:J=6） 进行第二次交换后：27 38 49 97 76 13 65 ( 按照算法的第四步从前面开始找key 的值，6549,两者交换，此时：I=2 ) 进行第三次交换后：27 38 13 97 76 49 65 ( 按照算法的第五步将又一次执行算法的第三步从后开始找 进行第四次交换后：27 38 13 49 76 97 65 ( 按照算法的第四步从前面开始找大于 key 的值，9749，两者交换，此时：I=3,J=5 ) 此时再执行第三步的时候就发现 I=J=3，从而结束一趟快速排序，那
10、么经过一趟快速排序之后的结果是：27 38 13 49 76 97 65，即所有大于key49 的数全部在 49 的后面，所有小于 key（49）的数全部在 key（49）的前面。四、穷举法奥赛精解练习题 P180 页例 1完全数。因子的和等于它本身的数是完全数（自身因子除外） 。例 2在 A、B 两个城市之间设有 N 个路站（N100） ，城市与路站之间、路站与路站之间各有若干条路段（各路段数20，且每条路段上的距离均为一个整数） 。A，B 的一条通路是指：从 A 出发，可经过任一路段到达 S1，再从 S1 出发经过任一路段最后到达 B。通路上路段距离之和称为通路距离（最大距离1000） 。
11、当所有的路段距离给出之后，求出所有不同距离的通路个数（相同距离仅记一次） 。例如下图 N=1 时的情况：5 6A 7 S1 B4 5从 A 到 B 的通路条数为 6，但因其中通路 5+5=4+6，所以满足条件的不同距离的通路数为 5。例 3尺子刻度问题。一条 29 厘米长的尺子，只允许在上面刻七个刻度，要能用它量出 129 厘米的各种长度。尺子的刻度该如何选择。赛题：奥赛精解练习题 P187 页1古纸残篇在一位数学家的藏书中夹有一张古旧的纸片。纸片上的字早已模糊不清了，只留下曾经写过字的痕迹，依稀还可看出是一个乘法算式如图。这个算式上原来的数字是什么呢？夹着这张纸的书页上，标明“素数” ，经研究发现这个算式中的每个数字都是素数，而且这样的算式是只唯一的，把这个算式写出来。奥赛精解练习题 P250 页
