首页 > 试题广场 > 密码破译
[编程题]密码破译
我们来做一个简单的密码破译游戏。破译的规则很简单,将数字转换为字母,1转化为a,2转化为b,依此类推,26转化为z。现在输入的密码是一串数字,输出的破译结果是该数字串通过转换规则所能产生的所有字符串。

输入描述:
多行数据,每行为一个数字串。
保证数字串的总长度不超过1000,每行数据的答案至少有1个且不超过1000个。


输出描述:
多行数据,每行对应输出通过数字串破译得到的所有字符串,并按照字符串顺序排列,字符串之间用单个空格分隔。每行开头和结尾不允许有多余的空格。
示例1

输入

1
12
123

输出

a
ab l
abc aw lc
""""
递归求解,一种变式DFS
对存在'0'的情况特殊处理
"""
import sys


def dfs(s, temp, ans):
    if not s:
        ans.append(''.join(temp))
        return
    if (len(s) >= 2 and s[1] != '0') or len(s) == 1:
        dfs(s[1:], temp + (chr(int(s[0]) + ord('a') - 1),), ans)
    if (len(s) >= 3 and s[2] != '0' or len(s) == 2) and int(s[:2]) <= 26:
        dfs(s[2:], temp + (chr(int(s[:2]) + ord('a') - 1),), ans)


if __name__ == "__main__":
    for line in sys.stdin:
        s = line.strip()
        ans = []
        dfs(s, tuple(), ans)
        print(' '.join(ans))

发表于 2019-07-13 21:44:07 回复(0)
#include <bits/stdc++.h>

using namespace std;

string s;
vector<string> v;
int l;

void DFS(string t, int p){
    if(p==l){
        v.push_back(t);
        return ;
    }
    char c = 'a'+s[p]-'1';
    if(!(p+1<l && s[p+1]=='0'))      //除了第二位0的情况
        DFS(t+c, p+1);
    if(p+1<l && (s[p]=='1' || (s[p]=='2' && s[p+1]<='6'))){
        if(!(p+2<l && s[p+2]=='0')){
            c = 'a' + 10*(s[p]-'0') + (s[p+1]-'1');
            DFS(t+c, p+2);
        }
    }
}

int main(){    
    while(cin>>s){
        l = s.length();
        v.clear();
        string t="";
        DFS(t,0);
        for(int i=0;i<v.size();i++){
            if(i==v.size()-1)
                cout<<v[i]<<endl;
            else
                cout<<v[i]<<" ";
        }
    }
    return 0;
}

发表于 2019-07-22 16:06:32 回复(0)
虽然代码长了点,但是读起来真的很简单,比下面看着很短的答案要更方便理解。
import sys
def game(s,cur):
    if not s:
        res.append(cur)
    else:
        i = 0
        if s[i]=='1':
            game(s[i+1:],cur+dic[s[i]])
            if i<len(s)-1:
                game(s[i+2:],cur+dic[s[i:i+2]])
        elif s[i]=='2':
            game(s[i+1:],cur+dic[s[i]])
            if i<len(s)-1 and int(s[i+1])<7:
                game(s[i+2:],cur+dic[s[i:i+2]])
        elif s[i]=='0':
            return
        else:
            game(s[i+1:],cur+dic[s[i]])
if __name__=='__main__':
    dic = {}
    for i in range(1,27):
        dic[str(i)] = chr(i+96)
    for line in sys.stdin.readlines():
        res = []
        s = line.strip()
        game(s,'')
        res.sort()
        print(' '.join(res))


发表于 2019-08-10 20:47:52 回复(0)
输入输出是个谜
d = {}
for i in range(26):
    d[i+1] = chr(97+i)
def decode(strs, d):
    temp = [[strs[0]]]
    res = temp
    for i in range(1,len(strs)):
        res = []
        for j in temp:
            res.append(j+[strs[i]])
            if j[-1]*10+strs[i]<=26:
                res.append(j[:-1]+[j[-1]*10+strs[i]])
        temp = res 
    strs = []
    for i in res:
        strs.append(''.join(d[k] for k in i))
    return strs
while True:
    try:
        strs = list(map(int,input()))
        s = decode(strs,d)
        for i in range(len(s)-1):
            print(s[i],end=' ')
        print(s[-1])
    except:
        break

发表于 2019-07-11 17:46:06 回复(0)
#include<iostream>
#include<string>
#include<vector>
using namespace std;
void dfs(string &s, int index, string &one, vector<string> &ans){
    if(index==s.size()){
        ans.push_back(one);
        return ;
    }
    if(s[index]!='0'){
        one.insert(one.size(), 1, s[index]-'0'-1+'a');
        dfs(s, index+1, one, ans);
        one.erase(one.size()-1);
    }
    if(index+1>=s.size()) return ;
    int tmp = atoi(s.substr(index,2).c_str());
    if(tmp>=10 && tmp<=26){
        one.insert(one.size(), 1, tmp-1+'a');
        dfs(s, index+2, one, ans);
        one.erase(one.size()-1);
    }
}
void getAns(string &s){
    vector<string> ans;
    string one;
    dfs(s, 0, one, ans);
    if(ans.size()>0){
        cout<<ans[0];
        for(int i=1; i<ans.size(); i++) cout<<' '<<ans[i];
    }
    cout<<endl;
}
int main(){
    string line;
    while(getline(cin, line)){
        if(line.size()==0) break;
        getAns(line);
    }
    return 0;
}

发表于 2019-07-06 11:24:00 回复(0)