pascal中级教程第二章递归与递推

况，假设从0000~9999，这一万个连续的数，0到9用到的次数都是相同的，一万个四位数，0到9这十个数字共用了40000次，每个数字使用了4000次。

进一步推广，考虑所有的n位数情况，从n个0到n个9，共10n个n位数，0到9十

n-1

个数字平均使用，每个数字共用了n*10次。

有了这样的规律后，可以从高位向低位进行统计，最后再减去多余的0的个数。 以n=3657为例：(用count数组来存放0到9各个数字的使用次数)

最高位(千位)为3，从0千、1千到2千，000~999重复了3次，每一次从000到999，每个基本数字都使用了3*102＝300次，重复3次，所以count[0]～count[9]各增加3*300； 另外最高位的0到2作为千位又重复了1000次，count[0]～count[2]各增加1000，3作为千位用了657次(＝n mod 100)，因此count[3]增加657；

接下来对百位6再进行类似的处理，0到9在个位和十位平均重复使用6*20次，所以count[0]～count[9]先各增加6*20，0到5作为百位重复使用了100次，所以count[0]～count[5]再各增加100，6作为百位在这里重复用了57次(＝n mod 100)；因此count[6]增加57； 对十位和个位也进行相同的处理，得出count[0]~count[9]的值； 最后再减去多算的0的个数。 那么0到底多算了多少次呢?

当没有十位及以更高位时，个位的0，只多算了1次； 当没有百位及以更高位时，十位的0，多算了10次； 当没有千位及以更高位时，百位的0，多算了100次；

??

因此在统计m位数时，0多算了(11??1)这样一个全是1的m位数。

基本算法描述如下：

输入n； 计算n的位数Len； 将n每一位上的数字存放到数组c里； 计算10的0次方到len-1次方并存放到数组b里； i控制位数，for i:=len downto 1 do begin 0到9的使用次数增加平均使用的次数b[i-1]*(i-1)*c[i]； 0到c[i-1]的使用次数增加作为当前位使用的次数b[i-1]； c[i]的使用次数增加n mod b[i-1] end 最后减去多计算的0的个数； 输出结果。

2.5 诸侯安置

源程序名 empire.???（pas, c, cpp） 可执行文件名 empire.exe 输入文件名 empire.in 输出文件名 empire.out 【问题描述】 很久以前，有一个强大的帝国，它的国土成正方形状，如图2—2所示。

这个国家有若干诸侯。由于这些诸侯都曾立下赫赫战功，国王准备给他们每人一块封地(正方形中的一格)。但是，这些诸侯又非常好战，当两个诸侯位于同一行或同一列时，他们就会开战。如下图2—3为n＝3时的国土，阴影部分表示诸侯所处的位置。前两幅图中的诸侯可以互相攻击，第三幅则不可以。

致使国家动荡不安。 他希望通过合 国王自然不愿意看到他的诸侯们互相开战， 因此，

理的安排诸侯所处的位置，使他们两两之间都不能攻击。

现在，给出正方形的边长n，以及需要封地的诸侯数量k，要求你求出所有可能的安置方案数。(n≤l00，k≤2n2-2n+1)

由于方案数可能很多，你只需要输出方案数除以504的余数即可。 【输入】 仅一行，两个整数n和k，中间用一空格隔开。 【输出】 一个整数，表示方案数除以504的余数。 【样例】 empire.in 2 2 【样例说明】

empire.out 4

四种安置方案如图2-4所示。注意：镜面和旋转的情况属于不同的方案。

【算法分析】

重新描述一下问题，其实就是在一个边长为2n-1的正菱形(如上图2-2为n＝3的情形)

上摆放k个棋子，使得任意两个棋子都不在同一行、同一列。试问：这样的摆法共有多少种? 看到这道题目，我们就会立即想起一道经典的老题目：n皇后问题。这道题目与n皇后问题非常相似。但有两个不同点：一是n皇后问题可以斜着攻击对方棋子，而本题不能；二是n皇后问题是在n，n的正方形棋盘上面放置k个皇后，而本题却是在一个正菱形上摆放。我们试着先将n皇后变为不可斜攻的，再作思考，如果不能够斜着攻击，n皇后的公式是：(C(k,n))*k!。但是本题不是一个正方形，所以这个公式对本题好像没有任何帮助。看来只能够从另外一个角度思考问题了。

首先想到在2n-1列中任意取出k列进行具体分析，这样一来问题就转化成：有一个长为k的数列(无重复元素)，每一个数在一个不定的区间[a,b]当中，第i个数一定在区间[ai,bi]之间，求这样的数列有多少种?如果就是这个问题，那么比较难解决，但若把这个数列放在本题中，就比较简单。 因为题目中任意两个区间都是一种包含关系。可以先把区间按照长度排一下序，就可以看出来，再用乘法原理进行求解即可。但是，n最多可到100，k最多可到50，穷举要进行C(50,100)种方案! 显然无法在规定的 时间内出解!那么怎么办呢?再继续分析一下问题发现，里面有重叠子问题。 如果一个列作为最后一列，且这一列以及前面所有列共放置p个诸侯，设 有q种情况，那么这一列后面的所有列共放置p+1个棋子的方案数都要用

2

到q，从而引用乘法原理。而且在穷举过程中，这一个工作做了许多遍，所以干脆用递推。递推前，先把图形转化为类似图2-5的形式(即列排序)。

设f[i,j]表示以第i列为最后一列，放置j个棋子的总方案数，得出公式：

i?jf[i,j]??k?1f[i?k,j?1]*(i?j?1)

不过还要注意，当k≥2n-1时，问题无解。

2.6 括号序列

源程序名 bracket.???（pas, c, cpp） 可执行文件名 bracket.exe 输入文件名 bracket.in 输出文件名 bracket.out 【问题描述】 定义如下规则序列(字符串)： 1．空序列是规则序列； 2．如果S是规则序列，那么(S)和[S]也是规则序列；

3．如果A和B都是规则序列，那么AB也是规则序列。 例如，下面的字符串都是规则序列： ()，[]，(())，([])，()[]，()[()] 而以下几个则不是： (，[，]，)(，())，([()

现在，给你一些由‘(’，‘)’，‘[’，‘]’构成的序列，你要做的，是找出一个最短规则序列，

an和序列bl，使得给你的那个序列是你给出的规则序列的子列。(对于序列a1，a2，?，b2，?，bm，如果存在一组下标1≤i1

ja2?，an就叫做b1，b2，?，bm的子列。

【输入】

输入文件仅一行，全部由‘(’，‘)’，‘]’，‘]’组成，没有其他字符，长度不超过100。 【输出】 输出文件也仅有一行，全部由‘(’，‘)’，‘]’，‘]’组成，没有其他字符，把你找到的规则序列输出即可。因为规则序列可能不止一个，因此要求输出的规则序列中嵌套的层数尽可能地少。 【样例】 bracket.in ([() 一种为()[()]}

bracket.out ()[]()

{最多的嵌套层数为1，如层数为2时的

【算法分析】

对于输入的括号序列字符串，从左向右进行查找，用一个数组来记录查找配对的情况，如果一个括号有相应的括号跟它对应，则将它标记为0，如果没有相应的括号跟它对应，则保存原子始代码的编号，“[]”分别为-1和1，“()”分别为-2和2。 因此对于读入的字符串，首先将其转换为相应的代码存放到数组里，为后面查找匹配做准备。

查找匹配时，可用这样的方法：

如果当前的字符是右括号，则跟前面的一个没有匹配的左括号对照，看是否匹配，如果匹配，则将两个字符标记为0，查找并定位到左边的第一个没有匹配的左括号(如果有的话)。如果当前的字符是左括号，则记住这个不匹配的左括号的位置，为后面找到右括号时匹配做