首页 > 试题广场 > 密码破译
[编程题]密码破译
  • 热度指数:944 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
我们来做一个简单的密码破译游戏。破译的规则很简单,将数字转换为字母,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<iostream>
#include<string>
#include<vector>
using namespace std;

void get_all(string s,int i,string res,vector<string> &tmp)
{
    if(i==s.size()-1)
    {
        res+=char((s[i]-48)+96);
        tmp.push_back(res);
        return;
    }
    if(i>s.size()-1)
    {
        tmp.push_back(res);
        return;
    }
    if((s[i]-48)*10+(s[i+1]-48)>26)
    {
        res+=char((s[i]-48)+96);
        get_all(s,i+1,res,tmp);
    }
    else{
        string aux=res;
        res+=char((s[i]-48)+96);
        //判断s[i+1]是否为'0',如果是'0',则不能在当前位置一个一个的解码
        if(s[i+1]!='0')
            get_all(s,i+1,res,tmp);
        res=aux+char(((s[i]-48)*10+(s[i+1]-48))+96);
        //下面是判断s[i+2]是否为'0',假如s[i+2]为'0',则我们在当前位置两个一组解码后会对'0'本身解码
        //当i==s.size()-2时,i+2已经越界,所以要加一个判断
        if(i==s.size()-2)
            get_all(s,i+2,res,tmp);
        else if(s[i+2]!='0')
            get_all(s,i+2,res,tmp);
    }
    
}

int main()
{
    string s;
    while(cin>>s)
    {
        vector<string> tmp;
        get_all(s,0,"",tmp);
        for(int i=0;i<tmp.size();i++)
        {
            cout<<tmp[i]<<' ';
        }
        cout<<endl;
    }
}

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

using namespace std;

int main(){
	string s;
	vector <string> ver;
	auto solve = [&](auto& self, string use, string ret){
		if(use.size() == 0){
			ver.push_back(ret);
			return;
		}
		int t1 = (use[0] - '0');
		if(t1 >= 1){
			char ch1 = (t1 - 1) + 'a';
			self(self, use.substr(1), ret + ch1);
		}
		if(use.length() >= 2){
			int t2 = 10 * (use[0] - '0') + (use[1] - '0');
			if(t2 >= 10 && t2 <= 26 ){
				char ch2 = (t2 - 1) + 'a';
				self(self, use.substr(2), ret + ch2);
			}
		}
	};
	while(cin >> s){
		ver.clear();
		solve(solve, s, "");
		for (auto ss : ver){
			cout << ss << " ";
		}
		cout << "\n";
	}
	return 0;
}	

发表于 2019-10-24 18:09:08 回复(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)
#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 java.util.*;

public class Main {

    public static void main(String[] args)  {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            char[] s = sc.next().toCharArray();
            if(s.length == 1) {
                System.out.println(parse(s[0]));
                continue;
            }

            List<String> lst = new ArrayList<>();
            char[] dst = new char[s.length * 2];
            dfs(s, 0, dst, 0, lst);
            for (String str : lst) {
                System.out.print(str);
                System.out.print(" ");
            }

            System.out.println();
        }
    }


    private static void dfs(char[] src, int idx, char[] dst, int dstIdx, List<String> result) {
        if(src.length == idx) {
            result.add(new String(dst, 0, dstIdx));
            return;
        }

        char a = src[idx];
        if(a == '0') {
            return;
        }

        dst[dstIdx] = parse(a);
        dfs(src, idx + 1, dst, dstIdx + 1, result);

        if(idx + 1 < src.length) {
            char b = src[idx + 1];
            char tb = parse(a, b);
            if (tb > 'z' || tb < 'a') {
                return;
            }

            dst[dstIdx] = tb;
            dfs(src, idx + 2, dst, dstIdx + 1, result);
        }
    }

    private static char parse(char n1) {
        return (char)('a' + n1 - '0' - 1);
    }

    private static char parse(char n1, char n2) {
        int n = (n1 - '0') * 10 + n2 - '0';
        return (char)(n + 'a' - 1);
    }


}

编辑于 2019-09-18 22:14:44 回复(0)
/*回溯法,这里注意的一个小坑是a排在1而不是0*/
#include <iostream>
#include <istream>
#include <string>

using namespace std;
string input;
bool isfirst = true;

void dfs(string& ans, int n, int p, bool& isfirst){
    
    if(p>=n){
        if(isfirst){
            isfirst = false;
            cout << ans;
        } else{
            cout << " " << ans;
        }
        return;
    }
    
    if(p<n){
        
        if(input[p] == '0'){
            return;
        }
        
        ans += input[p]-'1'+'a';
        dfs(ans, n, p+1, isfirst);
        
        ans.erase(ans.size()-1);
        if(p+1<n && 10*(input[p]-'0')+input[p+1]-'0' <= 26){
            ans += 10*(input[p]-'0')+input[p+1]-'0' -1 + 'a';
            dfs(ans, n, p+2, isfirst);
            ans.erase(ans.size()-1);
        }
    }
    
    
}

int main(){
    
    while(cin >> input){
        
        int n = input.size();
        string ans = "";
        isfirst = true;
        dfs(ans, n, 0, isfirst);
        
        cout << endl;
    }
    
    
    return 0;
}

发表于 2019-09-18 09:35:23 回复(0)
def func(nn, res, lst):
    if len(nn) == 0:
        if res not in lst:
            lst.append(res)
            return
    for i in range(len(nn)):
        if nn[i] == "1" and i+1 < len(nn):
            if nn[i+1] == "0":
                func(nn[i+2:], res+num_to_char(nn[i:i+2]), lst)
                return
            else:
                if i+2 < len(nn) and nn[i+2] == "0":
                    func(nn[i+1:], res+num_to_char(nn[i]), lst)
                    return
                else:
                    func(nn[i+1:], res+num_to_char(nn[i]), lst)
                    func(nn[i+2:], res+num_to_char(nn[i:i+2]), lst)
                    return
        elif nn[i] == "2" and i+1<len(nn) and int(nn[i+1]) <= 6:
            if nn[i+1] == "0":
                func(nn[i+2:], res+num_to_char(nn[i:i+2]), lst)
                return
            else:
                if i+2<len(nn) and nn[i+2] == "0":
                    func(nn[i+1:], res+num_to_char(nn[i]), lst)
                    return
                else:
                    func(nn[i+1:], res+num_to_char(nn[i]), lst)
                    func(nn[i+2:], res+num_to_char(nn[i:i+2]), lst)
                    return
        else:
            res += num_to_char(nn[i])
    if res not in lst:
        lst.append(res)
        
            

def num_to_char(num_str):
    return chr(int(num_str) + 96)
while True:
    try:
        nn = input()
        res = ""
        lst = []
        func(nn, res, lst)
        lst.sort()
        for per_str in lst:
            print(per_str, end=" ")
        print()
    except:
        break

发表于 2019-09-08 12:55:01 回复(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)

问题信息

上传者:小小
难度:
10条回答 1603浏览

热门推荐

通过挑战的用户

查看代码