[第18期]字母编码（已总结）

f_qc

0问题当时确实没考虑，不应该直接去掉的

f_qc

现在发现有点晚了，不过改写了一下，还是发上来吧

[此贴子已经被作者于2006-12-23 14:04:27编辑过]

leeyong

我对0的处理是作空格处理，而且用的是子过程，可方便的改为其它字符的编码

leeyong

都没有一个人得分的，还是快些总结吧！

winland

再改一下,之前那个是一行一行加值,慢得很. 改了一下用数组, 23个1两三秒就搞定了.

确实是几秒完成的事情。关闭刷屏还可快点

[此贴子已经被northwolves于2006-12-31 2:53:22编辑过]

northwolves

QUOTE:

以下是引用guangyp在2006-12-17 15:30:49的发言：

今天再次调试后发现上一贴有两个漏洞：

1、如222这样左右连续数据，只得到结果为BBB和VB，没能得到BV值。

2、A1不是随机出现的数字，而是不断循环出现的数字。

修正后的文件：

(请审核人删除了今天3:15左右我发的贴子，该贴的运算速度不高且随机值有循环现象，本行文字也请审核人删除，谢谢了！）

思路示意图做得很好。

northwolves

附：

我的递归解法：

Option Explicit
Sub getall(ByVal mystr As String, ByRef steps() As String, Optional ByRef methodn As Long) '将mystr的所有可能编码方法保存在数组steps()中，编码方法数目保存在methodn中
Dim i As Long, a() As String, methoda As Long

If Len(mystr) = 1 Then '1位就一种可能
methodn = 1
ReDim steps(1 To methodn)
steps(1) = Chr(Val(Left(mystr, 1)) + 64)
End If

If Len(mystr) = 2 Then
methodn = 2
ReDim steps(1 To methodn)
steps(1) = Chr(Val(Left(mystr, 1)) + 64) & Chr(Val(Right(mystr, 1)) + 64)
If Val(mystr) < 26 Then
steps(2) = Chr(Val(mystr) + 64)
Else
ReDim Preserve steps(1 To 1)
methodn = 1
End If
End If

If Len(mystr) > 2 Then
getall Left(mystr, Len(mystr) - 1), steps, methodn '递归调用

For i = 1 To methodn
steps(i) = steps(i) & Chr(Val(Right(mystr, 1)) + 64)
Next

If Val(Right(mystr, 2)) < 26 Then
getall Left(mystr, Len(mystr) - 2), a, methoda '递归调用
ReDim Preserve steps(1 To methodn + methoda)
For i = 1 To methoda
steps(i + methodn) = a(i) & Chr(Val(Right(mystr, 2)) + 64)
Next
methodn = methodn + methoda
End If
End If
End Sub

Private Sub CommandButton1_Click()
Dim temp() As String, n As Long
getall [a1], temp, n
Application.ScreenUpdating = False
[a2].Resize(n, 1) = WorksheetFunction.Transpose(temp)
Application.ScreenUpdating = True
End Sub

northwolves

本题来源：

http://acm.pku.edu.cn/JudgeOnline/problem?id=2033，几乎未做任何改动，因而对0的处理未加以考

虑。所以，本次题目判分比较松，基本正确都可得分。

现在看来，题目如果设定 0=A，1=B，...25=Z 更完美些。

Alphacode
Time Limit:1000MS  Memory Limit:30000K
Total Submit:2436 Accepted:752

Description
Alice and Bob need to send secret messages to each other and are discussing ways to encode their messages:

Alice: "Let's just use a very simple code: We'll assign 'A' the code word 1, 'B' will be 2, and so on down to 'Z' being assigned 26."
Bob: "That's a stupid code, Alice. Suppose I send you the word 'BEAN' encoded as 25114. You could decode that in many different ways!”
Alice: "Sure you could, but what words would you get? Other than 'BEAN', you'd get 'BEAAD', 'YAAD', 'YAN', 'YKD' and 'BEKD'. I think you would be able to figure out the correct decoding. And why would you send me the word ‘BEAN’ anyway?”
Bob: "OK, maybe that's a bad example, but I bet you that if you got a string of length 500 there would be tons of different decodings and with that many you would find at least two different ones that would make sense."
Alice: "How many different decodings?"
Bob: "Jillions!"

For some reason, Alice is still unconvinced by Bob's argument, so she requires a program that will determine how many decodings there can be for a given string using her code.

Alice: "Let's just use a very simple code: We'll assign 'A' the code word 1, 'B' will be 2, and so on down to 'Z' being assigned 26."
Bob: "That's a stupid code, Alice. Suppose I send you the word 'BEAN' encoded as 25114. You could decode that in many different ways!”
Alice: "Sure you could, but what words would you get? Other than 'BEAN', you'd get 'BEAAD', 'YAAD', 'YAN', 'YKD' and 'BEKD'. I think you would be able to figure out the correct decoding. And why would you send me the word ‘BEAN’ anyway?”
Bob: "OK, maybe that's a bad example, but I bet you that if you got a string of length 500 there would be tons of different decodings and with that many you would find at least two different ones that would make sense."
Alice: "How many different decodings?"
Bob: "Jillions!"

For some reason, Alice is still unconvinced by Bob's argument, so she requires a program that will determine how many decodings there can be for a given string using her code.

Input
Input will consist of multiple input sets. Each set will consist of a single line of digits representing a valid encryption (for example, no line will begin with a 0). There will be no spaces between the digits. An input line of '0' will terminate the input and should not be processed

Output
For each input set, output the number of possible decodings for the input string. All answers will be within the range of a long variable.

Sample Input

25114
1111111111
3333333333
0

25114
1111111111
3333333333
0

Sample Output

6
89
1

6
89
1

Source
East Central North America 2004

northwolves

本期总结：

本期题目不够严谨，导致参与者把时间和精力花费到0的处理上，也背离了出题时的初衷。大家的做法也是

以递归为主。guangyp  和 shuyee 的代码比较特别。winland 和  guangyp 对代码进行了探讨。 这个题目

我最早见于2002年，当时首先想到的就是递归。与牛顿走楼梯的题目有些相似，如果数字都是1和2，将会产

生一个Fibonacci数列。（http://blog.csdn.net/northwolves/archive/2004/07/23/49386.aspx）

题目：

一个共有20个台阶的楼梯，从下面走到上面。一次只能迈一个台阶或两个台阶，并且不能后退，走完这个楼梯共有多少种方法。

分析：

1 步台阶只有1种走法（1）

2步台阶2种(11、2）

3步台阶有3种（111、12、21）

4 步台阶有5种（1111、112、121、211、22）

5 步台阶有8种（11111、1112、1121、1211、122、2111、212、221）

6步台阶有13种（111111、11112、11121、11211、1122、12111,1212、1221、2111、2112、2121、2211、222）

可以发现每一个台阶数的走法对应为比它少一步各种走法前加一个1步和比它少两步的走法前加一个2步，并构成一个Fibonacci数列。

感谢大家的参与，有兴趣者可将题目改过（0->A,1->B,...24->Y,25->Z)做一做。