发布时间 : 星期二 文章pascal-算法例题 - 图文更新完毕开始阅读9571631e650e52ea55189837
中山纪念中学信息学奥林匹克算法设计题选
writeln(t);
for k:=1 to 8 do begin
for l:=1 to 8 do if (a[k]<>l) then write('.':3) else write('O':3); writeln; end; writeln; zz:=readkey; end else begin
for k:=1 to 8 do begin
b:=true;
for l:=1 to n-1 do if (a[l]=k) or (abs(a[l]-k)=abs(l-n)) then b:=false; if b then begin
a[n]:=k; qu(n+1); end; end; end; end;
begin clrscr; t:=0; qu(1); writeln;
writeln(' total ',T,'');readln; end. 2、回溯：分派整数1、2、3??8给以下各方框，并保证没有两个相邻的方框（垂直相邻，斜对角相邻或水平相邻）含有连续的整数。写一个程序，找出所有的分派方案。 分析：此题与八皇后问题相似，大家自己把程序编出。 3、回溯：在一个NXN的方格网上从某一点（I，J）开始，沿水平、垂直或对角线向前进，最后回到（I，J），形成一个不相交的封闭的折线，设此封闭折线不与方格网的边界相交，求此封闭折线所围成的面积。面积的计算方法是统计折线上以及它所围成的封闭区域中的水平线与垂直线交点的数目。如图中围住了41个点（包括折线本身上的点），因而面积为41。 输入格式：文件读入，格式如下（定义走法：U向上，D向下，L向左，R向右，UL、UR、DL、DR依次累推）： 5 2 表示起点为（5，2） R 2 表示向右走三点 DR 2 表示向下右走三点 D 3 表示向下走四点 L 1 表示向左走一点 D 2 表示向下走二点
第 17 页 共 31页
中山纪念中学信息学奥林匹克算法设计题选 分析：（1）、用一个二维数组来存放该网格，折线经过的点的值存为1，不经过的点存为0。注意：该题的判错很重要，如何判断折线是否相交？如何判断折线是否闭合？ （2）存好数组后，我们得到一个0、1数字矩阵，这时应该如何判断折线图形的面积呢？ （3）实际上，题目中重点说明了该图形不与边界相交，我们完全可以从某个边界点入手，把它压入栈，然后将其周围所有相邻元素中不为1的点的值改为2，表示该点已经被处理。 （4）再把本次改成2的点逐个压入栈进入回溯下一层，将其周围所有不为1的相邻点的值也改为2，直到所有这样的点都被处理完。这时我们得到的网格是数字0、1、2组成的矩阵，所有数字为2的点都没有被折线包围。数字为0，1的点的总数就是所要求的面积。 4、回溯：有一个由N个数组成的序列，有0，1两种数，要求在任一个数前1的个数不得超过0的个数，求出所有这样的序列。 分析：用回溯过程来产生这个序列，每次可把0或1加入已产生序列的未尾，但当加入数字1时，使得当前的1的个数超过0的个数，这就表示该处不能加入数字1。 注意：结果序列如果用数组存放可作为全局变量；如果用一个字符串来存放就只能作为回溯过程的输入参数之一。 5、回溯：以下列方式向5X5矩阵中填入数字。设数字I(1<=I<=25)已被置于座标位置（X,Y），则数字I+1的座标位置应为（E，W），（E，W）可根据以下关系由（X，Y）算出： （1）（E，W）=（X±3，Y）； （2）（E，W）=（X，Y±3）； （3）（E，W）=（X±2，Y±2）。 编写一个程序，当数字1被指定于某个起始位置时，列举出其它24个数字应在的位置；列举出该条件下的所有可能方案，输出所有可能的情况。 6、回溯：编一程序，从键盘输入数字R，计算机自动检查在下列算式的“（）”中能否填上“+”或“-”号凑成相应的等式。如能凑成，则打印出这些算式。如不能则打印“NO ANSWER”。 1( )2( )3( )4( )5( )6( )7( )8( )9=R 7、一笔画问题：一个平面图如下，仅有两点为奇结点（某个点连接的线数为奇数则为奇结点，否则为偶结点），其余为偶结点，以这两个点为起、终点。给出一条经过各边一次且仅一次的路径。打印所有结果。
3 5 4
1 9 10 2
7 6 8
8、有NXM张邮票边在一起，但其中某一张被挖掉了。如下图就5X4的邮票的形状和编号，其中第11张被挖掉了，现在要求从这些邮票中撕出4张连在一起的邮票，请打印出所有答案。 1 2 3 4 5 6 7 8 9 10 12 13 14 15 16
第 18 页 共 31页
中山纪念中学信息学奥林匹克算法设计题选
17 18 19 20 输入格式： 5 4 表示5行4列 3 3 表示第3行第3列的邮票被撕掉了，如果输入0 0则表示没有撕掉邮票。
输出格式 1-2-3-4 以下若干行为各种方案 1-5-9-13 5-9-13-17 1-5-6-7 1-6-7-10 ??
七、排列组合问题：
一、排列：如：1、2、3三个数字，排列成一队，共有多少种排法。可知，有以下几种：
123，132，213，231，312，321 共六种情况。
实际上，我们可以把三个数字的全排列看成是：先取第一个数字（有三种情况），再取第二个数字（有两种情况），然后取第三个数字，则只有一种情况了。所以，三个数字的全排共有3*2*1种情况。这就是乘法原则。
乘法原则：如果一件事可分成若干个小步骤来完成，每步又有数种可能性，则该事件的可能性总数为所有小步骤的可能性之积！例如：有以下图表示三个声城市之间的路径：
由上图可见，A到B有两条路可走，B到C有三条路可走，则A到C有多少种走法呢？ 根据乘法原则可知：是2*3=6条走法。
再如，有6个人，选出三个来排成一列，共有多少种排法呢？
我们知道，选第一个人时，有6种可能性；然后选第二个人时，有5种可能性；再选第三个人时，有4种可
A B C 能性。所以，从6个人中选3个人排成一列，共有：6*5*4=120种排法。
排列问题我们用P来表示，Pnm表示从N个物件中选出M个来排列的所有情况。如：P63表示从6个物件中选出3个的排列情况。并且我们可以得到以下公式：
Pnm?n*(n?1)*(n?2)......(m?1) 如：P63?6*5*4?120
共M个数相乘 共3个数相乘
3例：从5个人中选出3个人排成一列，共有P5?5*4*3?60种排法。
二、组合：组合问题与排列问题非常相似，如：从5个人中选出3个人来，共有多少种选法？从N个人中选出M
3个人来表示为：Cn，所以上题可表示为求：C5。
m请大家注意上题，并没有提到排成一列的问题，也就是说，只要把人选出来，并不用排列他们。这就是组合问题，而这样情况总数会少掉多少呢？我们知道，从5个人中选3个人排列，共有P5?5*4*3?60种排法。这实际上是从5个人中选出3个人来，然后再把他们排列一下，每次有P33?6种排法。所以，如果只是选出3个人的组合，就应该是P/P3533种。所以我们可以得到下列公式：
3333PnmC?m。这就是组合的公式。
Pmmn所以，从5个人中选出3个人来，共有：C5?P5/P3?60/6?10种选法。如：从1至5五个数字中选出3个的所有选法有：123，124，125，134，135，145，234，235，245，345。 除了乘法原则外，我们在做排列组合问题时，还经常用到以下原理或原则：
加法原则：如果一件事的完全有几种大情况，每种大情况都又有几种可能性，则该事件的可能性总数为这几
第 19 页 共 31页
中山纪念中学信息学奥林匹克算法设计题选
种大情况的可能性之和。
鸽笼原理：也叫抽屈原理。即有N+1只鸽子，N个鸽笼，如果要把所有的鸽子都装进鸽笼，则至少有一个鸽笼中至少有两只鸽子。
例：有2名女生，5名男生，再要从中选出四人，且至少要一个女生，问共有多少种选法？ 分析：该题可分成两种情况：
131、 只选一个女生：又分成两部分，一是选女生，有C2?2种选法；二是选男生，有C5?10种选法。所以
13只选一个女生的选法有：C2*C5?20种。
22、 选二个女生：第一部分选女生，只有一种选法，就是两个人都选；第二部分是选男生，有C5?10种。
所以选两个女生时的选法有10种。
所以，该题的答案应该是上述两种情况的选法数相加，共有30种选法。
八、概率问题：
一件事中，各种情况都有可能发生，其中某种或某些情况发生的可能性是多少呢？这就是概率问题。答案是指定某种或某些情况发生的种数除以所有情况的种数，所得的大于等于0，小于等于1的一个小数。
例如上题中，如果改为有2名女生、5名男生，从中选出4个人，问其中一定有一个女生的概率是多少？
134答案是：所有的可能性是：C7 *C5?20。所以，概率为20/30=0.66。?35；有一个女生的可能性是：C2
九、分治策略
1、分治策略：求N个数A1，A2，A3??AN中的最大值MAX和最小值MIN。 分析：分治策略是指这样一种算法：把一个大问题分解成若干个小问题，比如：计算教室面积时，可把它分成若干小块，分别计算面积后再相加。步骤为：分割——求解——合并，共三步。 该题如果N等于1时，MAX=MIN=A1，如果N=2时，MAX=A1，MIN=A2或MAX=A2，MIN=A1，这是非常简单的，所以此题可把所有的数作为一个序列，每次从中取出开头两个数，求共MAX，MIN，然后再从剩余的数中取开头两个数，求其MAX、MIN后与前一次的MAX、MIN比较，可得出新的MAX、MIN，这样重复下去，直到把所有的数取完（注意最后一次取可能是只有一个数），MAX，MIN也就得到了。这就是典型的分治策略。注意：这样做与把所有数字排序后再取MAX、MIN要快得多。 2、分治策略：找出N个整型元素中的第K个最小元素。 分析：当然，此题用排序方法做也要花不少时间，如果用分治策略，可这样考虑：按某个元素M（称为分划元素）把这N个元素分成3个子序列，S1中存放小于M的数，S2中存放等于M的数，S3中存放大于M的数。我们可以很容易地知道这三个子序列中元素的个数，即可以确定我们要找的第K个最小元素在哪个子序列中。这样，就等于是让我们再在某个子序列中找某个数，把一个大问题划成了小问题了，递归地做下去，最后就能找到第K个最小元素。分划元素可简单地取序列中的第一个数。
N
3、分治策略：计算X。
N2N/2N2P1
分析：如果N为偶数，则X=（X）；如果N为奇数，则X=X*X，（2P+1=N）转化成了偶数次方。这样递
0
归地做下去，直到计算X为止。
十、动态规划
1、动态规划：（最优策略）在一个需要多步决策的过程中，每一步都可能有若干种方案可供选择，一旦每一步的方案都选择好后，即构成了一个解决问题的决策策略。问题往往有一种标准，需要衡量决策的优劣，以确
第 20 页 共 31页