编程语言

MIT 6.00.1x 计算机科学和Python编程导论 Part1 of Set 6

Problem 1: Encryption

buildCoder

感谢 glhezjnucn 童鞋对本周问题的给力翻译 !
You’ll now write a program to encrypt plaintext into ciphertext using the Caesar cipher. 你现在来写一个函数将使用凯撒密码将明文转为密文。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def buildCoder(shift):
    """
    Returns a dict that can apply a Caesar cipher to a letter.
    The cipher is defined by the shift value. Ignores non-letter characters
    like punctuation, numbers, and spaces.

    shift: 0 <= int < 26
    returns: dict
    """
    ### TODO 
    ciphertext = {}
    uppercase_plaintext = [i for i in string.ascii_uppercase]
    lowercase_plaintext = [i for i in string.ascii_lowercase]
    for i in range(26):
        if i < (26 - shift):
            ciphertext[uppercase_plaintext[i]] = uppercase_plaintext[i+shift]
        else:
            ciphertext[uppercase_plaintext[i]] = uppercase_plaintext[i+shift-26]
    for i in range(26):
        if i < (26 - shift):
            ciphertext[lowercase_plaintext[i]] = lowercase_plaintext[i+shift]
        else:
            ciphertext[lowercase_plaintext[i]] = lowercase_plaintext[i+shift-26]
    return ciphertext

applyCoder

Next, define the function applyCoder, which applies a coder to a string of text. 接着定义函数applyCoder, 将一个密钥变换作用到字符串.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def applyCoder(text, coder):
    """
    Applies the coder to the text. Returns the encoded text.

    text: string
    coder: dict with mappings of characters to shifted characters
    returns: text after mapping coder chars to original text
    """
    ### TODO
    cipherText = ''
    for char in text:
        if char in string.ascii_letters:
            cipherText += coder[char]
        else:
            cipherText += char
    return cipherText

encode strings

Once you have written buildCoder and applyCoder, you should be able to use them to encode strings. 写完了buildCoder 和 applyCoder函数,你就能对字符串加密解密了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def applyShift(text, shift):
    """
    Given a text, returns a new text Caesar shifted by the given shift
    offset. Lower case letters should remain lower case, upper case
    letters should remain upper case, and all other punctuation should
    stay as it is.

    text: string to apply the shift to
    shift: amount to shift the text (0 <= int < 26)
    returns: text after being shifted by specified amount.
    """
    ### TODO.
    ### HINT: This is a wrapper function.
    return applyCoder(text,buildCoder(shift))

Problem 2: Decryption

Your friend, who is also taking 6.00.1x, is really excited about the program she wrote for Problem 1 of this problem set. She sends you emails, but they’re all encrypted with the Caesar cipher! 你的朋友, 也参加了6.00.1x课程,对她在问题1中编写的程序很是兴奋，她发了一份email给你，不过她用了恺撒密文
If you know which shift key she is using, then decrypting her message is an easy task. If the string message is the encrypted message and k is the shift key she is using, then calling applyShift(message, 26-k) returns her original message. Do you see why? 如果你知道她所用的密钥，那么解码她的信息是很容易的事情，如果信息message是按k-移位转换的，你只需用applyShift(message, 26-k)就返回原来的信息message. 你明白为什么吗?
The problem is, you don’t know which shift key she is using. The good news is, you know your friend only speaks and writes English words. So if you can write a program to find the decoding that produces the maximum number of real English words, you can probably find the right decoding (there’s always a chance that the shift may not be unique. Accounting for this would use statistical methods that we won’t require of you.)
问题是，如果你不知道她用了什么k-移位密钥，好在你知道你的朋友仅用英语单词. 因此如果你能写个程序，找出能解码成含有最多英语单词的密钥，那你很有可能找到正确的解码方法 (按此想法有可能得到不唯一的移位密钥，对付它可能需要统计方法，但这里我们不对此作要求.)

pseudocode 伪码

Right now, you should take time to write some pseudocode! Think about an algorithm you could use to solve this problem and write the steps down. Then, you can verify your algorithm with the supplied pseudocode in ps6_pseudo.txt before coding.
现在你需要花点时间来写伪码! 想想你来解这个问题的算法并将它写成步骤，然后在开始编程之前你可以对照我们提供的伪码（ps6_pseudo.txt）.
After you’ve done writing and checking your pseudocode, implement findBestShift(). This function takes a wordList and a sample of encrypted text and attempts to find the shift that encoded the text. A simple indication of whether or not the correct shift has been found is if most of the words obtained after a shift are valid words. Note that this only means that most of the words obtained are actual words. It is possible to have a message that can be decoded by two separate shifts into different sets of words. While there are various strategies for deciding between ambiguous decryptions, for this problem we are only looking for a simple solution.
当你写好了伪码并加以检查，开始设计 findBestShift().这个函数接收单词列表wordList以及密文样本,试着找出最好的移位密钥. 看是否找到了正确的密钥的一个简单的征兆是看看它是否把很多密文中的单词转换成了真实的单词。有可能会有不同的密钥将密文解码为不同的单词集，这时需要决定哪个解码是需要很多策略的，但这个问题我们只需要你应对简单的情形.
To assist you in solving this problem, we have provided a helper function, isWord(wordList, word). This simply determines if word is a valid word according to the wordList. This function ignores capitalization and punctuation.
为辅助你解决问题，我们提供了辅助函数isWord(wordList, word). 它能判定一个串是否是英语单词列表wordList中的有效词汇。函数将忽略大写开头以及标点符号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def findBestShift(wordList, text):
    """
    Finds a shift key that can decrypt the encoded text.

    text: string
    returns: 0 <= int < 26
    """
    ### TODO
    max_num_of_words_finded,best_shift = 0,0
    str_split = string.punctuation + string.digits 
    for shift in range(26):
        num_of_valid_words = 0
        plaintext = applyShift(text, shift)
        for i in str_split:  #剔除符号和数字
            text0 = plaintext.split(i)
            plaintext = "".join([i for i in text0])
        textList =plaintext.split(' ') #剔除空格
        for word in textList:
            if word in wordList:
                num_of_valid_words += 1
                if num_of_valid_words > max_num_of_words_finded:
                    max_num_of_words_finded = num_of_valid_words
                    best_shift = shift            
    return best_shift

decryptStory

Now that you have all the pieces to the puzzle, please use them to decode the file story.txt. In the skeleton file, you will see a method getStoryString() that will return the encrypted version of the story. Fill in the following function; it should create the wordList, obtain the story, and then decrypt the story. Be sure you’ve read through the whole file to see what helper functions we’ve defined for you that may assist you in these tasks! This function will be only a few lines of code (our solution does it in 4 lines).
现在你已经准备好一切解题所需要的细节，请用它们来解密story.txt. 在外壳程序中，你会发现getStoryString()函数来返回story的密文，填入后续的函数，你从story中载入单词列表，再将其解码。确保你通读过我们为你写好的包装函数。这个函数不需要多少行代码（我们用了4行代码完成）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def decryptStory():
    """
    Using the methods you created in this problem set,
    decrypt the story given by the function getStoryString().
    Once you decrypt the message, be sure to include as a comment
    your decryption of the story.

    returns: string - story in plain text
    """
    ### TODO
    wordList = loadWords()
    story = getStoryString()
    bestshift = findBestShift(wordList, story)
    return   applyCoder(story, buildCoder(bestshift))

念起即觉，觉而不随