递规与递推习题汇总.docx

递规与递推习题汇总2.1遍历问题源程序名trave1.?(pas,c,cpp)可执行文件名输入文件名输出文件名【问题描述】我们都很熟悉二叉树的前序、中序、后序遍历，在数据结构中常提出这样的问题：已知一棵二叉树的前序和中序遍历，求它的后序遍历，相应的，己知一棵二叉树的后序遍历和中序遍历序列你也能求出它的前序遍历。然而给定一棵二叉树的前序和后序遍历，你却不能确定其中序遍历序列，考虑如下图中的儿棵二叉树：aaaa/bbbb/CCCC所有这些二叉树都有着相同的前序遍历和后序遍历，但中序遍历却不相同。【输入】输A数据共两行，第一行表示该二叉树的前序遍历结果si,第二行表示该二叉树的后序遍历结果s2o【输出】输出可能的中序遍历序列的总数，结果不超过长整型数。【样例】abe4bca【算法分析】根据二叉树先序遍历和后序遍历的特点，可以知道，先序遍历的第一个结点是后序遍历的最后一个结点，对于中序遍历来说却是中间的一个结点，这里所说的中间也只是相对而言的中间。如果一棵二叉树的根结点没有左子树，那么先序遍历的第一个结点也是中序遍历的第一个结点，如果一棵二叉树的根结点没有右子树，那么先序遍历的第一个结点是中序遍历的最后一个结点。我们这里还认为就是中序遍历的中间结点，上面两种情况只是特殊的情况。设二叉树的结点总数为n(对于输入的字符串来说是它的长度)，对于先序遍历的结果，第一个结点为根结点，从第二个结点到最后一个结点分为n种情况：根结点的左子树结点个数为n-1,右子树结点的个数为0；根结点的左子树结点个数为n-2,右子树结点的个数为1；根结点的左子树结点个数为n-i,右子树结点的个数为H1.；0<=i<=nT);根结点的左子树结点个数为0,右子树结点的个数为n-1.。根据这n种情况，分别将二叉树拆分为左子树和右子树，左子树结点个数为nT,右子树结点的个数为iTS<=i<=n-1),先序遍历的结果是从第二个结点(字符)开始取，而后序遍历的结果里是从第1个结点字符开始取。也就是说对于每一种情况，分两步处理：第一步在先序遍历和后序遍历的结果里取左子树，看是否符合规则，统计这部分可能有的中序遍历的结果数目；第二步在先序遍历和后序遍历的结果里取右子树，看是否符合规则，统计这部分可能有的中序遍历的结果数目。这两步都递归调用了统计过程，不再递归调用的条件就是当统计的是空树或只有一个结点的树，这时返回的值是可能有的中序遍历结果数目。结合“分类相加原理”和“分步相乘原理”，可以得到下面的递归函数：FunctionCOUnt（先序结果first,后序结果1.ast:string）:Iongint;begin1.en:=遍历结果的长度：如果Ien为。或。则返回结果即COUnt:=1否则begint为当前统计后符合条件的数目，初值为0；分类统计fori:=1.en-1.downto0dobegin在first中取出长度为i的左子树结果1.F；在1.ast中取出长度为i的左子树结果1.1.；在first中取出长度为1.en-1-i的左子树结果RF；在1.ast中取出长度为1.en-1-i的右子树结果R1.；如果1.F、1.1.符合基本规则（1.F的首字符跟1.1.的尾字符相同、1.F中，所有的字符在1.1.中也都有）并且RF、R1.也符合基本规则，那么t:=t+count（1.F,1.1.）*count（RF,R1.）;分步相乘、分步相加这里COUnt函数中递归调用了countend;返回值为t即count:=t;end;end;其中，检查先序结果和后序结果两个字符串是否符合基本规则，可以再通过一个函数来实现:functioncheck（先序字符串F,后序字符串1.）：boo1.ean；beginCheck:=true;如果F的首字符不等于1.的尾字符则check:=fa1.se;从F的第二个字符取到最后一个字符，如果该字符不在1.中，则CheCk:=fa1.se;end;【思考与提高】上面的算法通过递归，结合统计的基本原理“分步相乘，分类相加”，从而统计出所有可能解的个数，如果输入的两个字符串没有解，上述算法同样能得到结果。在肯定有解的情况下，上述算法最终可以递归调用到0、1个结点，如果有多组解，那么调用到两个结点时，如先序为ab、后序为ba,此时有可能有如下两种结构：这两种结构的中序遍历结果分别为：ba、ab,有两种。根据分步相乘的原理，对比两个字符串，每出现一次如上的情况，可能有的结构数目(结构不同，中序遍历结果也不同，因此可能有的二叉树结构的数目就是可能有的中序遍历结果数目)就乘以2次，最终得到总的数目。这也可以理解为一种递推的方法。从这里可以看到，在肯定有解的情况下，给定先序遍历的结果和后序遍历的结果，可能有2n种可能的结构，也就是中序遍历可能得到2口种不同的结果，其中n>=0°那么这里的n最大可能是多少呢？可以证明n的最大值为字符串的长度加1整除2。递推的程序如下：Programtrave1.(intputzoutput);VarTotaIJzITiiIongint;S1.,s2:string;BeginAssign(input/);Assign(output/');Reset(input);rewrite(output);Read1.n(si);read1.n(s2);tota1.:=1;Fori:=1.to1.ength(S1.)IdoBeginM:=pos(s1.izs2);Ifm>1.thenifsi+1.=sm-1.thentotak=tota1.*2;End;Write1.n(tota1.);c1.ose(iinput);c1.ose(output);End.2.2产生数源程序名bui1.d.?(pas,c,cpp)可执行文件名输入文件名输出文件名【问题描述】给出一个整数n(n<103°)和m个变换规则(mW20)。约定：一个数字可以变换成另一个数字，规则的右部不能为零，即零不能由另一个数字变换而成。而这里所说的一个数字就是指一个一位数。现在给出一个整数n和m个规则，要你求出对n的每一位数字经过任意次的变换(0次或多次)，能产生出多少个不同的整数。【输入】共m+2行，第一行是一个不超过30位的整数n,第2行是一个正整数m,接下来的m行是m个变换规则，每一规则是两个数字x、y,中间用一个空格间隔，表示X可以变换成y。【输出】仅一行，表示可以产生的不同整数的个数。【样例】123621223【算法分析】如果本题用搜索，搜索的范围会很大(因为n可能有30位!)，显然无法在规定的时间内出解。而我们注意到本题只需计数而不需要求出具体方案，所以我们稍加分析就会发现，可以用乘法原理直接进行计数。设Fi表示从数字i出发可以变换成的数字个数(这里的变换可以是直接变换，也可以是间接变换，比如样例中的1可以变换成2,而2又可以变换成3,所以1也可以变换成3；另外自己本身不变换也是一种情况)。那么对于一个长度为m位的整数a,根据乘法原理，能产生的不同的整数的个数为：Fa1.*Fa2*Fa3*Famo下面的问题是如何求Fi呢？由于这些变换规则都是反映的数字与数字之间的关系，所以定义一个布尔型的二维数组g0.9,0.9来表示每对数字之间是否可以变换，初始时都为Fa1.se；根据输入的数据，如果数字i能直接变换成数字j,那么gi,j置为TrUe,这是通过一次变换就能得到的；接下来考虑那些间接变换可得到的数字对，很明显：如果i可以变为k,k又可以变为j,那么i就可以变为j,即：fork:=0to9dofori:=0to9doforj:=0to9dogiJ=giJor(g(iandgkj)；最后还要注意，当n很大时，解的个数很大，所以要用高精度运算。2.3出栈序列统计源程序名stack.?(pas,c,cpp)可执行文件名输入文件名输出文件名【问题描述】栈是常用的一种数据结构，有n个元素在栈顶端一侧等待进栈，栈顶端另一侧是出栈序列。你已经知道栈的操作有两种：PUSh和pop,前者是将一个元素进栈，后者是将栈顶元素弹出。现在要使用这两种操作，由一个操作序列可以得到一系列的输出序列。请你编程求出对于给定的n,计算并输出由操作数序列1,2,，n,经过一系列操作可能得到的输出序列总数。【输入】【输出】就一个数n(1.n1000)。一个数，即可能输出序列的总数目。【样例】35【算法分析】在第一章练习里，我们通过回溯的方法计算并输出不同的出栈序列，这里只要求输出不同的出栈序列总数目，所以我们希望能找出相应的递推公式进行处理。从排列组合的数学知识可以对此类问题加以解决。我们先对n个元素在出栈前可能的位置进行分析，它们有n个等待进栈的位置，全部进栈后在栈里也占n个位置，也就是说n个元素在出栈前最多可能分布在2*n位置上。出栈序列其实是从这2n个位置上选择n个位置进行组合，根据组合的原理，从2n个位置选n个，有C(2n,n)个。但是这里不同的是有许多情况是重复的，每次始终有n个连续的空位置，n个连续的空位置在2n个位置里有n+1种，所以重复了n+1.次。所以出栈序列的种类数目为：C(2nzn)(n+1.)=2n*(2n-1.)*(2n-2).*(n+1.)n!(n+1.)=2n*(2n-1.)*(2n-2)*(n+2)n!o考虑到这个数据可能比较大，所以用高精度运算来计算这个结果。本题实际是一个经典的Cata1.an数模型。有关Cata1.an数的详细解释请参考组合数学等书。【思考与提高】我们知道，在某个状态下，所能做的操作(移动方法)无非有两种：(1)将右方的等待进栈的第一个元素进栈；(2)将栈顶的元素出栈，进入左边的出栈序列。设此时右方、栈、左方的元素个数分别为a,b,Co我们就能用(a,b,c)表示出当前的状态。显然n=a+b+c,则c=n-a-b0即已知a和b,c就被确定，所以我们可以用(a,b)来作为状态的表示方法。则起始状态为(n,0),目标状态为(0,0)。又由上面的两种移动方法，我们可类似的得到两种状态转移方式：再设f(a,b)为从状态(a,b)通过移动火车变为状态(0,0)的所有移动方法。类似于动态规划的状态转移方程，我们可写出以下递归式：f(a-ib+1.)+f(a,h-1.)m>0,b>0)f(a9b)(a+bn)=(a>O,b=O)(此时只能做进栈操作)(67=0)(此时只能做出栈操作)边界值：f(0,0)=Io有了这个递归公式后，再写程序就比较简单了，请读者自己写出递归程序。2.4计数器源程序名count.?(pas,c,cpp)可执行文件名输入文件名输出文件名【问题描述】一本书的页数为N,页码从1开始编起，请你求出全部页码中，用了多少个0,1,2,9。其中一个页码不含多余的0,如N=1234时第5页不是Oo05,只是5。【输入】一个正整数N(NWIo9),表示总的页码。【输出】共十行：第k行为数字*1的个数。【样例】111411111111【算法分析】本题可以用一个循环从1到n,将其拆为一位一位的数字，并加到相应的变量里，如拆下来是1,则CoUnt1增加1。这种方法最简单，但当n比较大时，程序运行的时间比较长。这种方法的基本程序段如下：fori:=1.tondobeginj：=i；whi1.ej>0dobegincountjmod10:=countjmod10+1.;j:=jdiv10;end;end;当n是整型数据时，程序执行的时间不会太长。而n是长整型范围，就以n是一个9位数为例，当i执行到8位数时，每拆分一次内循环要执行8次，执行完8位数累计内循环执行的次数为：9*1.+90*2+900*3+9000*4+90000*5+900000*6+*7+*8时间上让人不能忍受。可以从连续数字本身的规律出发来进行统计，这样速度比较快，先不考虑多余的0的情况，假设从OOoO9999,这一万个连续的数，。到9用到的次数都是相同的，一万个四位数，0到9这十个数字共用了40000次，每个数字使用了4000次。进一步推广，考虑所有的n位数情况，从n个O到n个9,共Ion个n位数，0至U9十个数字平均使用，每个数字共用了n*10ni次。有了这样的规律后，可以从高位向低位进行统计，最后再减去多余的。的个数。以n=3657为例：(用count数组来存放0到9各个数字的使用次数)最高位(千位)为3,从0千、1千至12千，(X)O999重复了3次，每一次从OOO到999,每个基本数字都使用了3*102=300次，重复3次，所以CoUntOcount各增加3*300；另外最高位的0到2作为千位又重复了1000次，coUnt0CoUnt各增加1000,3作为千位用T657次(=nmod100),因此COUnt增加657；接下来对百位6再进行类似的处理，。到9在个位和十位平均重复使用6*20次，所以COUntCOUnt先各增力口6*20,0到5作为百位重复使用了100次,所以CoUntCOUnt再各增加100,6作为百位在这里重复用了57次(=nmod100)；因此CoUnt增加57；对十位和个位也进行相同的处理，得出CoUnt0count9的值；最后再减去多算的0的个数。那么0到底多算了多少次呢？当没有十位及以更高位时，个位的0,只多算了1次；当没有百位及以更高位时，十位的0,多算了10次；当没有千位及以更高位时，百位的0,多算了100次；因此在统计m位数时，0多算了(111)这样一个全是1的m位数。基本算法描述如下：输入n；计算n的位数1.en；将n每一位上的数字存放到数组c里；计算10的0次方到IenT次方并存放到数组b里；i控制位数,fori:=1.endownto1dobegin0到9的使用次数增加平均使用的次数bi-1.*(i-1.)*ci:0到ci-1.的使用次数增加作为当前位使用的次数bi-1.:ci的使用次数增加nmodbi-1.end最后减去多计算的0的个数；输出结果。源程序名empire.?(paszczcpp)可执行文件名输入文件名输出文件名【问题描述】很久以前，有一个强大的帝国，它的国土成正方形状，如图22所示。这个国家有若干诸侯。由于这些诸侯都曾立下赫赫战功，国王准备给他们每人一块封地（正方形中的一格）。但是，这些诸侯又非常好战，当两个诸侯位于同一行或同一列时，他们就会开战。如下图23为n=3时的国土，阴影部分表示诸侯所处的位置。前两幅图中的诸侯可以互相攻击，第三幅则不可以。因此，他希望通过合国王自然不愿意看到他的诸侯们互相开战，致使国家动荡不安。理的安排诸侯所处的位置，使他们两两之间都不能攻击。现在，给出正方形的边长n,以及需要封地的诸侯数量k,要求你求出所有可能的安置方案数。（nIOO,k2n2-2n+1.）由于方案数可能很多，你只需要输出方案数除以504的余数即可。【输入】仅一行，两个整数n和k,中间用一空格隔开。【输出】一个整数，表示方案数除以504的余数。【样例】【算法分析】重新描述一下问题,其实就是在一个边长为2n-1.的正菱形（如上图2-2为n=3的情形）上摆放k个棋子，使得任意两个棋子都不在同一行、同一列。试问：这样的摆法共有多少种?看到这道题目，我们就会立即想起一道经典的老题目：n皇后问题。这道题目与n皇后问题非常相似。但有两个不同点：一是n皇后问题可以斜着攻击对方棋子，而本题不能；二是n皇后问题是在n,n的正方形棋盘上面放置k个皇后，而本题却是在一个正菱形上摆放。我们试着先将n皇后变为不可斜攻的，再作思考，如果不能够斜着攻击，n皇后的公式是：(C(k,n)2*k1.但是本题不是一个正方形，所以这个公式对本题好像没有任何帮助。看来只能够从另外一个角度思考问题了。首先想到在2n-1列中任意取出k列进行具体分析，这样一来问题就转化成：有一个长为k的数列(无重复元素)，每一个数在一个不定的区间a,b当中，第i个数一定在区间EbU之间，求这样的数列有多少种?如果就是这个问题，那么比较难解决，但若把这个数列放在本题中，就比较简单。因为题目中任意两个区间都是一种包含关系。可以先把区间按照长度排一下序，就可以看出来，再用乘法原理进行求解即可,但是，n最多可到IOO,k最多可到50,穷举要进行C(50,100)种方案！显然无法在规定的时间内出解!那么怎么办呢?再继续分析一下问题发现，里面有重叠子问题。1.1.Z1.如果一个列作为最后一列，且这一列以及前面所有列共放置P个诸侯，设I-I-有q种情况，那么这一列后面的所有列共放置P+1个棋子的方案数都要用1.到q,从而引用乘法原理。而且在穷举过程中，这一个工作做了许多遍，所以干脆用递推。递推前，先把图形转化为类似图2-5的形式(即列排序)。设fij表示以第i列为最后一列，放置j个棋子的总方案数，得出公式：U=-y-U*(-y+i)J1.=I不过还要注意，当k22n-1时，问题无解。2.6括号序列源程序名bracket.?(pas,c,cpp)可执行文件名输入文件名输出文件名【问题描述】定义如下规则序列(字符串)：1 .空序列是规则序列；2 .如果S是规则序列，那么和也是规则序列；3 .如果A和B都是规则序列，那么AB也是规则序列。例如，下面的字符串都是规则序列：(),口,(0),(),0,()()而以下几个则不是：(,1.,)(,0),()现在，给你一些由黄，T,，构成的序列，你要做的，是找出一个最短规则序列，使得给你的那个序列是你给出的规则序列的子列。(对于序列，明和序歹Ib.,b2,，bm,如果存在一组下标IWiKi2<<i,Wm,使得对一切IWjWn成立，那么为，。2，就叫做b1.，匕2，6”,的子列。【输入】输入文件仅一行，全部由'C,')',T，T组成，没有其他字符，长度不超过100。【输出】输出文件也仅有一行，全部由C,')',T，T组成，没有其他字符，把你找到的规则序列输出即可。因为规则序列可能不止一个，因此要求输出的规则序列中嵌套的层数尽可能地少。【样例】()00最多的嵌套层数为1,如层数为2时的一种为()()【算法分析】对于输入的括号序列字符串，从左向右进行查找，用一个数组来记录查找配对的情况，如果一个括号有相应的括号跟它对应，则将它标记为0,如果没有相应的括号跟它对应，则保存原子始代码的编号，“口”分别为T和1,“()”分别为-2和2。因此对于读入的字符串，首先将其转换为相应的代码存放到数组里，为后面查找匹配做准备。查找匹配时，可用这样的方法：如果当前的字符是右括号，则跟前面的一个没有匹配的左括号对照，看是否匹配，如果匹配，则将两个字符标记为0,查找并定位到左边的第一个没有匹配的左括号(如果有的话)。如果当前的字符是左括号，则记住这个不匹配的左括号的位置，为后面找到右括号时匹配做准备。从第一个字符开始到最后一个字符重复上面的过程，检查处理完毕。输出时考虑到不增加嵌套的层数，以就近的原则，将出现不匹配的一个括号时，输出两个匹配的括号。源程序名hanoi.?(paszctcpp)可执行文件名输入文件名输出文件名【问题描述】设有n个大小不等的中空圆盘，按从小到大的顺序从1到n编号。将这n个圆盘任意的迭套在三根立柱上，立柱的编号分别为A、B、C,这个状态称为初始状态。现在要求找到一种步数最少的移动方案，使得从初始状态转变为目标状态。移动时有如下要求：一次只能移一个盘；不允许把大盘移到小盘上面。【输入】文件第一行是状态中圆盘总数；第二到第四行分别是初始状态中A、B、C柱上圆盘的个数和从上到下每个圆盘的编号;第五到第七行分别是目标状态中A、B、C柱上圆盘的个数和从上到下每个圆盘的编号。【输出】每行一步移动方案，格式为：moveIfromPtoQ最后一行输出最少的步数。【样例】5 move1fromAtoB6 321move2fromAtoC254move1fromBtoC0move3fromAtoB12move1fromCtoB3543move2fromCtoA11move1fromBtoC7【算法分析】要从初始状态到目标状态.就是要把每个圆盘分别移到自己的目标状态。怎样才能保证总的移动步数最少呢?关键是首先考虑把编号最大的圆盘移到它的目标状态，因为编号最大的圆盘移到目标位置后就不再移动了，而在编号最大的圆盘没有移到目标之前，编号小的圆盘可能还要移动，即使它已在目标状态。所以编号最大的圆盘一旦固定，对以后的移动不会造成影响。最大的移动好后，再考虑剩余的没有到达目标状态的最大号圆盘直到最小的编号为1的圆盘到目标状态为止。设计一个移动过程：move(k,w),表示把编号k的圆盘移到W柱。2.8排序集合源程序名sort.?(paszc1.cpp)可执行文件名输入文件名输出文件名【问题描述】对于集合N=U,2,n的子集，定义一个称之为“小于”的关系：设SEX1,Xi,(X<X2<-<Xi),S2=Y,Y2,Yj,(YKY2<如果存在一个k,(Okmin(i,j),使得XI=YI,，×k=Yk,且k=i或X(k+i)<Y(g»，则称S1“小于”S2。你的任务是，对于任意的n(nW31)及k(k<2n),求出第k小的子集。【输入】输入文件仅一行，包含两个用空格隔开的自然数，n和k。【输出】输出文件仅一行，使该子集的元素，由小到大排列。空集输出0。【样例】34123【算法分析】我们知道，n个元素构成的集合有2。种情况。本题的意思是：把这些集合按照某种规则排序，然后输入k,输出第k个集合。所以排序的规则是本题的关键，其实很简单，当n=3时，8个集合排序如下：<1.<1.,2<1.,2,3<1.,3<2<2,3<3,你发现规律了吗?具体算法为:先推出第k小的一个子集的第一个数宇是多少,第一个数字确定了之后，再推出第二个数字,从第一个数字加1一直计算累加集合个数，直到得到不超过k的最大的那个数字，就是第二位数字，这样一直递推，推到最后一个。要注意：终止条件是有了n个数字或者第i个数字为空，这时递推终止，输出最后的结果。源程序名frog.?(pas,c,卬P)可执行文件名输入文件名输出文件名【问题描述】有一条河，左边一个石墩(A区)上有编号为1,2,3,4,，n的n只青蛙，河中有k(1)石墩上可以承受任意多只青蛙，荷叶只能承受一只青蛙(不论大小)；(2)青蛙可以：A-B(表示可以从A跳到B,下同)，AiAfC-B,D-B,D-C,C-*D；(3)当一个石墩上有多只青蛙时，则上面的青蛙只能跳到比它大1号的青蛙上面。你的任务是对于给出的h,k,计算并输出最多能有多少只青蛙可以根据以上规则顺利过河？【样例】23河中间有2个石碳，3个荷叶16最多有16只青蛙可以按照规则过可【算法分析】结论为：f(hzk)=2h(k+1.)从具体到一般，推导过程如下：f(0,0)=1f(Ozk)=k+1.;(如k=3时，有4只青蛙可以过河)f(1.zk)=2(k+1.);(递推思想)依此类推：f(2zk)=(2*(k+1.)*2=22(k+1.);2.10电话号码源程序名phone.?(pas,c,cpp)可执行文件名输入文件名输出文件名【问题描述】电话机上每一个数字下面都写了若干个英文字母。分布如下:1.abc2def3ghi4ik1.5mn6opq7rst8uvw9xyz现在给定一个单词表和一串数字密码，请你用单词表中的单词翻译这个密码。【输入】第一行为一个正整数N表示单词表中单词的个数(NW1.O0)；第二行为一个长度不超过100的数字串，表示密码；接下来的N行，每行一个长度不超过20的单词，表示单词表。【输出】仅一行，表示翻译后的原文，如果密码无法翻译，则输出“NoSo1.utions!”，如果密码有多种翻译方式，则输出任意一种即可。【样例】8thishsbbookthiShSthisisbabook【算法分析】本题可以用递归搜索求解。首先，我们注意到一个数字串对应的单词是不惟一的，而反之，一个单词所对应的数字串却是惟一的!所以，我们一开始就读入一大串的数字密码和一些可以出现的单词，我们把每一个单词所表示的密码(是惟一的)存在数组中。然后从密码的开头开始扫描，得出密码的第一个单词有可能的情况，选择其中一种，得出第一个单词，得到除第一个单词以外的后面的子密码。然后用递归实现子密码的破译。若子密码无解，就可以换一种第一个单词的取法，再次试验。如果全是无解，那整个密码也是无解的。另外，首先要判断整个密码串是否是一个单词，避免无限递归。2.11编码源程序名encode.?(pas,c,cpp)可执行文件名输入文件名输出文件名【问题描述】编码工作常被运用于密文或压缩传输。这里我们用一种最简单的编码方式进行编码：把一些有规律的单词编成数字。字母表中共有26个字母a,b,，z,这些特殊的单词长度不超过6且字母按升序排列。把所有这样的单词放在一起，按字典顺序排列，一个单词的编码就对应着它在字典中的位置。例如：a-*1.b-*2Z-26ab27ac-*28你的任务就是对于所给的单词，求出它的编码。【输入】仅一行，被编码的单词。【输出】仅一行，对应的编码。如果单词不在字母表中，输出0。【样例】ab27【算法分析】对于输入的字符串，首先检查是否符合编码的条件：全是由小写字母组成并且前面的字母不会比后面的字母大。如果符合条件则进行编码，否则输出0。编码时如果不找规律，可以根据顺序，从第一个符合条件的单词a开始往后构造，每构造一个，相应的编码增加1,直到构造到输入的字符串。一个单词的后序单词类似于数字的进位，如十进制中8后面是9,9后面是10一进位的情况，再如99后面是IO0,199后面是200。而这里单词的规则是一串中后面的字符不比前面的大，所以Z后是ab,az后是be,两个字符的单词最大的为yz,三个字符最小的为abc,最大的为xyz,六个字符的单词最小的为abcdef,最大的为UVWXyz,根据上面的进位规则进行构造，构造到输入的字符串时则输出相应的序号。由此可以写出程序。另外可以从数学上寻找递推的规则：一个字符的单词有26个；两个字符的单词有：25+24+23+-+1个；其中abaz共25个,bcbz共24个，cdcz共23个，yz共1个三个字符的单词有：(24+23+22+1)+(23+22+21+-+1)+-+(2+1)+(1)个abcayzbcdbyzWXywyzxyz四个字符的单词有：(23+22+21+-+1)+(22+21+20+1)+-+(2+1)+(1)+abcdaxyz(22+21+20+1.)+(21+20+-+1)+(2+1)+(1)+(1)个wxyzbcdebxyz以此类推，得到相应的数学公式。