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

2.3 出栈序列统计

源程序名 stack.???（pas, c, cpp） 可执行文件名 stack.exe 输入文件名 stack.in 输出文件名 stack.out 【问题描述】 栈是常用的一种数据结构，有n个元素在栈顶端一侧等待进栈，栈顶端另一侧是出栈序列。你已经知道栈的操作有两种：push和pop，前者是将一个元素进栈，后者是将栈顶元素弹出。现在要使用这两种操作，由一个操作序列可以得到一系列的输出序列。请你编程求出对于给定的n，计算并输出由操作数序列1，2，?，n，经过一系列操作可能得到的输出序列总数。

【输入】 就一个数n(1≤n≤1000)。 总数目。 【样例】

stack.in

stack.out 5

3 【算法分析】

【输出】 一个数，即可能输出序列的

在第一章练习里，我们通过回溯的方法计算并输出不同的出栈序列，这里只要求输出不

同的出栈序列总数目，所以我们希望能找出相应的递推公式进行处理。

从排列组合的数学知识可以对此类问题加以解决。 我们先对n个元素在出栈前可能的位置进行分析，它们有n个等待进栈的位置，全部进栈后在栈里也占n个位置，也就是说n个元素在出栈前最多可能分布在2*n位置上。 出栈序列其实是从这2n个位置上选择n个位置进行组合，根据组合的原理，从2n个位置选n个，有C(2n,n)个。但是这里不同的是有许多情况是重复的，每次始终有n个连续的空位置，n个连续的空位置在2n个位置里有n+1种，所以重复了n+1次。所以出栈序列的种类数目为：

C(2n,n)/(n+1)=2n*(2n-1)*(2n-2)…*(n+1)/n!/(n+1)=2n*(2n-1)*(2n-2)*?*(n+2)/n!。

考虑到这个数据可能比较大，所以用高精度运算来计算这个结果。

本题实际是一个经典的Catalan数模型。有关Catalan数的详细解释请参考《组合数学》等书。

【思考与提高】

我们知道，在某个状态下，所能做的操作(移动方法)无非有两种：

（1）将右方的等待进栈的第一个元素进栈； （2）将栈顶的元素出栈，进入左边的出栈序列。

设此时右方、栈、左方的元素个数分别为a，b，c。我们就能用(a,b,c)表示出当前的状态。显然n=a+b+c，则c=n-a-b。即已知a和b，c就被确定，所以我们可以用(a,b)来作为状态的表示方法。则起始状态为(n,0)，目标状态为(0,0)。

又由上面的两种移动方法，我们可类似的得到两种状态转移方式：

再设f(a,b)为从状态(a,b)通过移动火车变为状态(0,0)的所有移动方法。类似于动?f(a?1,b?1)?f(a,b?1)(a?0,b?0)?f(a,b)(a?b?n)??f(a?1,b?1)(a?0,b?0)（此时只能做进栈操作?f(a,b?1)(a?0)（此时只能做出栈操作）?态规划的状态转移方程，我们可写出以下递归式：

）

边界值：f(0,0)=1。

有了这个递归公式后，再写程序就比较简单了，请读者自己写出递归程序。

2.4 计数器

源程序名 count.???（pas, c, cpp） 可执行文件名 count.exe 输入文件名 count.in 输出文件名 count.out 【问题描述】

一本书的页数为N，页码从1开始编起，请你求出全部页码中，用了多少个0，1，2，?，9。其中—个页码不含多余的0，如N＝1234时第5页不是0005，只是5。 【输入】

一个正整数N(N≤109)，表示总的页码。 【输出】

共十行：第k行为数字k-1的个数。 【样例】

count.in 11

count.out 1 4 1 1 1 1 1 1 1 1

【算法分析】

本题可以用一个循环从1到n，将其拆为一位一位的数字，并加到相应的变量里，如拆下来是1，则count[1]增加1。这种方法最简单，但当n比较大时，程序运行的时间比较长。这种方法的基本程序段如下： for i:=1 to n do begin

j:=i;

while j>0 do begin

count[j mod 10]:=count[j mod 10]+1; j:=j div 10; end;

end; 当n是整型数据时，程序执行的时间不会太长。而n是长整型范围，就以n是一个9位数为例，当i执行到8位数时，每拆分一次内循环要执行8次，执行完8位数累计内循环执行的次数为：

9*1+90*2+900*3+9000*4+90000*5+900000*6+9000000*7+90000000*8 时间上让人不能忍受。

可以从连续数字本身的规律出发来进行统计，这样速度比较快，先不考虑多余的0的情