分类： C/C++
2008-09-27 00:54:19
题意是给定一个从字母到数字的映射关系：a--1, b--2, ..., z--26.
则可以将一串字母表示成数字，如abc表示成123， xyz表示成242526.
但是这样的表示方法存在一个问题，就是同一个数字表示可能对应不同 的字母表示，比如242526可以翻译成xyz，也可以翻译成bdbebf。
题目的输入是一串数字，要求的输出是一个整数，该整数表示的是有多少种不同的字母串可以按照上述规则被翻译，换句话说，就是有多少种不同的翻译方法。（只要求出可能的不同字符串的个数，不需要求出具体的字符串）。
Sample Input
25114
1111111111
3333333333
0
Sample Output
6
89
1
【分析】
对于一个给定的数字串，我们要想按照上述规则进行翻译，可以一次取一个数字翻译成一个字母，但有时也可以一次取2个数字翻译成一个字母。
例子一：以输入范例25114为例，假如我们现在扫描到第一个数字2，对于它，我们有2钟不同的翻译方法：一种是将2替换成b，然后继续翻译5114；另一种是将25替换成y，然后继续翻译114.如果继续翻译5114共有m种翻译方法，继续翻译114有n种翻译方法，则串25114共有m+n种翻译方法。
例子二：再看一个例子，假如存在数字序列35114，仍然假设我们扫描到第一个数字3，此时由于35不可能翻译成一个字母，所以我们只有一种翻译方法，就是将3翻译成c。这样，35114共有多少种翻译方法取决于5114共有多少种翻译方法。
通过前面的两个例子的分析可以看出，问题的解是递归的。可以用下面的递归式表示：（其中input是输入的数字串，采用string存储）
对例子一：
method_cnt (input, n) = method_cnt (input, n+1) + method_cnt (input, n+2)
对例子二：
method_cnt (input, n) = method_cnt (input, n+1)
终止条件是什么呢？我们一直往下想，当上述翻译翻译到最后一个数字时，就会停止翻译，而最后一个数字的翻译方式只有一种，这样就有了终止条件。
而例子一和例子二的判断条件很简单，可以采用下面的方法实现：
int value = (input [n] – ‘0’) * 10 + (input [n+1] – ‘0’); //获得前两位转换成整数
if (value <=26) //判断是哪一种情况（注意，这个判断条件有个问题！后面再说）
{例子一情况}
else
{例子二情况}
看来我们已经可以开始动手了。下面是按照上面的分析写的代码：
#include
#include
using namespace std;
int Calc (string &input, int pos)
{
if (pos >=str.size()-1 )
{
table[pos] = 1;
return 1;
}
int tmp = (input[pos] - '0') * 10 + (input[pos+1] - '0');
if (tmp<=26)
{
int res = Calc (input, pos+1) + Calc (input, pos+2);
return res;
}
else
{
int res = Calc (input, pos+1);
return res;
}
}
int main()
{
string str;
while (cin>>str, str!="0")
{
cout<
}
return 0;
}
看上去似乎是正确的，但是其实问题很多，不信你可以提交一下，保证WA。
但是有一点可以肯定，我们的想法没错，也就是说递归式是正确的。我们一定是漏掉一些条件没考虑。
看一个输入实例：1020 。
我们应该怎么翻译?按照上面的程序，会把0也当成可以翻译成一个字母的！显然是错的！我们忘记了处理0！
事实上上例只能有一种翻译方式，就是10和20这两个字母。我们要在递归调用之前就把0的情况排除。所以我们要修改上面 的Calc函数：
int Calc (string &input, int pos)
{
if (pos >=str.size()-1 )
{
return 1;
}
if (input[pos] == 0)
{
return 0; //让其返回0，即没有办法（有0种办法）翻译以0 打头的。
}
int tmp = (input[pos] - '0') * 10 + (input[pos+1] - '0');
if (tmp<=26)
{
int res = Calc (input, pos+1) + Calc (input, pos+2);
return res;
}
else
{
int res = Calc (input, pos+1);
return res;
}
}
现在总算可以放心了。但是提交后发现还是会超时（Time Limit Exceed）。
不过这种情况自然会想到动态规划。打一张表就可以了。
具体思路是：把求到过的结果存储起来，下次再要求的时候直接返回结果，而不需要再求解一次。
这样源代码会变为如下：
#include
#include
#include
using namespace std;
vector <int> table; //用来存储计算结果的表
int Calc (string &input, int pos)
{
if (table[pos] != -1)
{ //如果已经求过这个值，则直接返回。
return table[pos];
}
if (input [pos] == '0')
{ //对串input当前扫描的pos位置为数字0时的处理
table[pos] = 0;
return 0;
}
else
{
if (pos >=input.size()-1 )
{ //递归终止条件
table[pos] = 1;
return 1;
}
else
{ //递归条用
int tmp = (input[pos] - '0') * 10 + (input[pos+1] - '0');
if (tmp<=26)
{
int res = Calc (input, pos+1) + Calc (input, pos+2);
table [pos] = res; //求得结果后填表，方便下次直接取答案
return res;
}
else
{
int res = Calc (input, pos+1);
table [pos] = res; //求得结果后填表，方便下次直接取答案
return res;
}
}
}
}
int main()
{
string str;
while (cin>>str, str!="0")
{
table.assign (str.size()+1, -1);
cout<
}
return 0;
}
这样就可以通过了。
