1

我的任务是解决学校的一个问题，这让我很困惑。我需要做的是读取一个模棱两可的摩尔斯电码字符串（即没有任何空格来说明什么是字母，什么不是）并打印出该摩尔斯电码所有可能的有效英文翻译。我在互联网上的某个地方看到了一种算法来解决这个确切的问题，但不知道如何将其转换为 Python 3，并且在我的一生中都找不到它。

一些有用的东西：

  • 我有一个程序认为有效的单词列表：下载

  • 该程序不需要输出语法正确的句子，只需要输出有效且在words.txt.

  • 定义一个句子是否有效的一些额外的事情是该句子不能有两个相同的单词；所有单词都必须是唯一的，并且句子中不能有超过一个 1 字母单词和 1 个 2 字母单词。

  • 我的代码，目前不完整，但将所有单词分类为相应的摩尔斯电码定义：

    # Define the mapping from letter to Morse code.
CODES = {
    'A': '.-',
    'B': '-...',
    'C': '-.-.',
    'D': '-..',
    'E': '.',
    'F': '..-.',
    'G': '--.',
    'H': '....',
    'I': '..',
    'J': '.---',
    'K': '-.-',
    'L': '.-..',
    'M': '--',
    'N': '-.',
    'O': '---',
    'P': '.--.',
    'Q': '--.-',
    'R': '.-.',
    'S': '...',
    'T': '-',
    'U': '..-',
    'V': '...-',
    'W': '.--',
    'X': '-..-',
    'Y': '-.--',
    'Z': '--..',
}
words={}

f=open('words.txt').read()
a=f
for i in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ':
  a=a.replace(i,CODES[i])
f=f.split('\n')
a=a.split('\n')
for i in f:
      words[i]=a[f.index(i)]
    q=input('Morse: ')

一个如何工作的示例测试用例是：

Morse: .--....-....-.-..-----.
A BED IN DOG
A DID IN DOG
A BLUE DOG
A TEST IF DOG
WEST I IN DOG
WEST EVEN A ON
WEST IF DOG
4

1 回答 1

1

要完成该程序，您需要使用递归算法，因为有很多可能的单词组合。

我已经更改了您的变量名称，以便它们易于理解它们保存的数据。

该decode函数用作递归算法。第一行检查 Morse 是否为空，因此无需运行该函数，因为它是一个终点，它会打印该分支的输出。

该函数的其余部分将检查是否可以从前 i 个字母中组成一个单词。i开头，1因为这是最短的字母，最大长度是文件中的最大莫尔斯长度。while 循环还通过检查i不大于 Morse 的长度来检查是否没有发生越界错误。

代码无法更改函数的参数，因为在相同的函数中可以找到其他单词，从而导致冲突，因此为更改的英语和莫尔斯语创建了新变量。检查可能单词的长度是否已被重复和允许。

from string import ascii_uppercase

#Defines the letter to Morse mapping
code = {
    'A': '.-',
    'B': '-...',
    'C': '-.-.',
    'D': '-..',
    'E': '.',
    'F': '..-.',
    'G': '--.',
    'H': '....',
    'I': '..',
    'J': '.---',
    'K': '-.-',
    'L': '.-..',
    'M': '--',
    'N': '-.',
    'O': '---',
    'P': '.--.',
    'Q': '--.-',
    'R': '.-.',
    'S': '...',
    'T': '-',
    'U': '..-',
    'V': '...-',
    'W': '.--',
    'X': '-..-',
    'Y': '-.--',
    'Z': '--..'
}

#Opens the file and reads all words
file = open("words.txt","r")
words = file.read()
file.close()

morse = words

# Converts all words to morse
for letter in list(ascii_uppercase):
    morse = morse.replace(letter, code[letter])

# Creates list of the morse and english words from strings
morsewords = morse.split("\n")
engwords = words.split("\n")

# Finds the max length of morse words
maxlength = max([len(i)] for i in morsewords)[0]

# Creates a dictionary of {morse words : english words}
words = dict(zip(morsewords, engwords))

# MorseInput = input("Morse code :")
MorseInput = ".--....-....-.-..-----."

# This is the recursive function
def decode(morse, eng="", oneWord=False, twoWord=False):
    # Print the english when finished
    if morse == "":
        print(eng)
    else:
        i = 1
        # While loop allows to go through all possWord where condition met
        while len(morse) >= i and i <= maxlength:
            possWord = morse[:i]
            # Checks if the word is a real word
            if possWord in words.keys():
                # Real word therefore add to english and the morse
                newEng = eng + " " + words[possWord]
                newMorse = morse[i:]
                # Checks if that not more than one, One length word used
                if len(words[possWord]) == 1:
                    if not oneWord:
                        decode(newMorse, newEng, True, twoWord)
                # Checks if that not more than one, Two length word used
                elif len(words[possWord]) == 2:
                    if not twoWord:
                        decode(newMorse, newEng, oneWord, True)
                # Word is greater than two so doesn't matter
                else:
                    decode(newMorse, newEng, oneWord, twoWord)                    
            i += 1


decode(MorseInput)

我希望我的评论有点道理。

我确信代码可以做得更好更短，但我在不到一个小时内就完成了。

它打印

A TEST IF DOG
A DID IN DOG
A BLUE DOG
WEST I IN DOG
WEST IF DOG
WEST EVEN A ON
于 2016-08-29T13:54:25.717 回答