1

モールス符号では、区切り記号で区切られた 1 ～ 4 のグループにドットとダッシュがあります。各グループは 1 つの文字を意味します。単語の間には 2 つのセパレーターがあります。文の間 3。

基本的なモールス符号を解読するためのアプリケーションは非常に簡単に作成できます。しかし、私の質問は、セパレーターがない場合に問題を解決する方法です。ばかげた結果が大量に出てくることはわかっていますが、それは私の主張ではありません。最も効率的な方法ですべての可能な結果を​​得る必要があるだけです。

これは入力になります：

......-...-..---

そして、これは多くの出力の 1 つになります。

hello

どうやってそれをしますか？

4

3 に答える 3

2

IMO 最も効率的なアプローチはトライを使用することです。これは、特定の段階でこれらの文字が可能な場合、すべてのノードに最大 2 つの子 (1 つは 用.、もう 1 つは 用) があるようなツリーです。-息子へのリンクに加えて、ノードには、ルートからこのノードへのパスがエンコードする文字を示す「終端」文字があります。終端文字は、パスが文字をエンコードしていない (文字列が完成していない) ことを示すゼロにすることができます。

モールス文字は小さいので、手でトライを作ることもできます。これがその一部です。

. => E
    . => I
        . => S
        - => U
    - => A
        . => R
        - => W
- => T
    . => N
        . => D
        - => K
    - => M
        . => G
        - => O

トライを活用するには、入力ストリーム内の位置とトライ内のノードを入力として受け取る再帰関数を記述します。ノードに終端文字がある場合は、終端文字を出力文字列に追加し、ノードをトライのルートにリセットします。同時に、次の入力記号に一致する子をたどって、トライの探索を続けます。

あなたの例の場合の再帰的実行のいくつかの最初のステップ (最初の 4 つの入力シンボルの分析) は次のとおりです。

. => E
    .|. => EE
        .|.|. => EEE
            .|.|.|. => EEEE
            .|.|.. => EEI
        .|.. => EI
            .|..|. => EIE
            .|... => ES
    .. => I
        ..|. => IE
            ..|.|. => IEE
            ..|.. => II
        ... => S
            ...|. => SE
            .... => H
于 2016-01-25T09:43:56.183 に答える