题解 P1079 【Vigenère 密码】
Sweetlemon
2017-02-08 21:16:42
此题我打了极大的表,并使用了string类使代码简洁(也许高效)。
思路是:读入密文code和密钥(yuè) key——预处理密钥,使每个字符都为大写——逐字符还原原文。
其中逐字符还原原文的过程如下:
- 分支讨论原文的大小写。
- 在打的表中的第k行【k为密钥对应字符(可用模运算得出)的ASCII码减去‘A’的ASCII码的值】查找密文该字符的大写形式的位置pos,则明文中该字符应为pos+'A'或pos+'a'(视原文大小写而定)。查找过程可用string.find(char)实现。
---------------------------------
下面给出该题程序和打表生成Python程序。
```cpp
//题解
#include <iostream>
#include <string>
#include <cctype>
using namespace std;
int main(void){
string key,code,raw; //依次为密钥,密文,原文
int i;
string table[]={"ABCDEFGHIJKLMNOPQRSTUVWXYZ",
"BCDEFGHIJKLMNOPQRSTUVWXYZA",
"CDEFGHIJKLMNOPQRSTUVWXYZAB",
"DEFGHIJKLMNOPQRSTUVWXYZABC",
"EFGHIJKLMNOPQRSTUVWXYZABCD",
"FGHIJKLMNOPQRSTUVWXYZABCDE",
"GHIJKLMNOPQRSTUVWXYZABCDEF",
"HIJKLMNOPQRSTUVWXYZABCDEFG",
"IJKLMNOPQRSTUVWXYZABCDEFGH",
"JKLMNOPQRSTUVWXYZABCDEFGHI",
"KLMNOPQRSTUVWXYZABCDEFGHIJ",
"LMNOPQRSTUVWXYZABCDEFGHIJK",
"MNOPQRSTUVWXYZABCDEFGHIJKL",
"NOPQRSTUVWXYZABCDEFGHIJKLM",
"OPQRSTUVWXYZABCDEFGHIJKLMN",
"PQRSTUVWXYZABCDEFGHIJKLMNO",
"QRSTUVWXYZABCDEFGHIJKLMNOP",
"RSTUVWXYZABCDEFGHIJKLMNOPQ",
"STUVWXYZABCDEFGHIJKLMNOPQR",
"TUVWXYZABCDEFGHIJKLMNOPQRS",
"UVWXYZABCDEFGHIJKLMNOPQRST",
"VWXYZABCDEFGHIJKLMNOPQRSTU",
"WXYZABCDEFGHIJKLMNOPQRSTUV",
"XYZABCDEFGHIJKLMNOPQRSTUVW",
"YZABCDEFGHIJKLMNOPQRSTUVWX",
"ZABCDEFGHIJKLMNOPQRSTUVWXY"};
cin >> key >> code;
raw.reserve(code.size()); //此句亦可删,意思是让原文字符串预留足够大(正好和code的长度相同)的空间
for (i=0;i<key.size();i++)
key[i]=toupper(key[i]); // 预处理密钥
for (i=0;i<code.size();i++){
if (isupper(code[i]))
raw[i]=table[key[i%key.size()]-'A'].find(code[i])+'A';
else
raw[i]=table[key[i%key.size()]-'A'].find(toupper(code[i]))+'a';
cout.put(raw[i]); //此处用逐字符输出的cout.put(char)
}
return 0;
}
```
--------------------------------
```python
#打表生成程序
l=[]
for i in range(ord('A'),ord('A')+26):
s='"'
for j in range(i,ord('Z')+1):
s+=chr(j)
for j in range(ord('A'),i):
s+=chr(j)
l.append(s+'"')
print("string x[]={"+",\n".join(l)+"};")
```
----------------------------------
另:做了这题才发现tg T1原来是这种难度……