6

モールス信号を変換する関数があるとします。

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

この関数を2回適用すると、次のようになります。

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

入力文字列と繰り返し回数が与えられた場合、最終的な文字列の長さを知りたい。（フラマン語プログラミングコンテスト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())

これは最初の3つの入力では機能しますが、最後の入力ではメモリエラーで停止します。

これをより効率的な方法でどのように書き直しますか？

編集

与えられたコメントに基づいて書き直してください：

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

開始文字列で、ドットとダッシュの数を数えます。次に、これを適用します。

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

なぜこれが機能するのか考えてみてください。

于 2012-05-09T18:17:35.533 に答える
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 に答える
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 に答える