6

假设我们有一个翻译莫尔斯符号的函数：

  • .->-.
  • -->...-

如果我们两次应用这个函数，我们得到例如：

.-> -.->...--.

给定一个输入字符串和多次重复，想知道​​最终字符串的长度。（来自Flemish Programming Contest VPW的问题 1 ，取自这些在 Haskell 中提供解决方案的幻灯片）。

对于给定的输入文件

4
. 4
.- 2
-- 2 
--... 50

我们期待解决方案

44
16
20
34028664377246354505728

由于我不知道 Haskell，这是我在 Python 中提出的递归解决方案：

def encode(msg, repetition, morse={'.': '-.', '-': '...-'}):
    if isinstance(repetition, str):
        repetition = eval(repetition)
    while repetition > 0:
        newmsg = ''.join(morse[c] for c in msg)
        return encode(newmsg, repetition-1)
    return len(msg)


def problem1(fn):
    with open(fn) as f:
        f.next()
        for line in f:
            print encode(*line.split())

它适用于前三个输入，但因最后一个输入的内存错误而死。

你将如何以更有效的方式重写它？

编辑

根据给出的评论重写：

def encode(p, s, repetition):
    while repetition > 0:
        p,s = p + 3*s, p + s
        return encode(p, s, repetition-1)
    return p + s


def problem1(fn):
    with open(fn) as f:
        f.next()
        for line in f:
            msg, repetition = line.split()
            print encode(msg.count('.'), msg.count('-'), int(repetition))

仍然欢迎对风格和进一步改进发表评论

4

4 回答 4

7

考虑到您实际上不必输出结果字符串，只需输出它的长度。还要考虑'.'的顺序。和字符串中的 '-' 不影响最终长度（例如，“.- 3”和“-. 3”产生相同的最终长度）。

因此，我会放弃存储整个字符串，而是存储“。”的数量。和“-”的数量为整数。

于 2012-05-09T17:42:50.740 回答
2

每@Hammar（我有同样的想法，但他解释得比我好;-)：

from sympy import Matrix

t = Matrix([[1,3],[1,1]])

def encode(dots, dashes, reps):
    res = matrix([dashes, dots]) * t**reps
    return res[0,0] + res[0,1]
于 2012-05-09T21:44:31.003 回答
2

在您的起始字符串中，计算点和破折号的数量。然后应用这个：

repetitions = 4
dots = 1
dashes = 0
for i in range(repetitions):
    dots, dashes = dots + 3 * dashes, dashes + dots

想想它为什么会这样。

于 2012-05-09T18:17:35.533 回答
1

在每次迭代中，您将点数改为破折号，并将破折号数改为点......

def encode(dots, dashes, repetitions):
    while repetitions > 0:
        dots, dashes = dots + 3 * dashes, dots + dashes
        repetitions -= 1

    return dots + dashes

def problem1(fn):
    with open(fn) as f:
        count = int(next(f))
        for i in xrange(count):
            line = next(f)
            msg, repetition = line.strip().split()
            print encode(msg.count('.'), msg.count('-'), int(repetition))
于 2012-05-09T18:16:11.117 回答