首页 > 试题广场 >

破译密码

[编程题]破译密码

热度指数：379 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛牛收到了一个任务，任务要求牛牛破译一个密码。牛牛将被给予两个字符串s1和s2，均由四个小写字母构成。需要破译的密码为从s1变换到s2最少需要的变换次数。

变换的方式是这样：每次变换可以选择当前字符串中的一个位置，然后剩下的三个位置的字符从左到右分别加上2，3，5，若是超出'z'，则重新从'a'开始，例如：对于字符串"abcd"，我们选择'c'的位置进行变换，则变换之后的字符串为"ceci";对于字符串"qyzr",我们选择'r'位置进行变换，则变换之后的字符串为"sber"。

示例1

输入

"aaaa","ccgk"

输出

说明

第一次变换选择第一个'a'，变成"acdf"，第二次变换选择第二个'c'，变成"ccgk"，故答案为2

备注:

s1,s2均由四个小写字母组成

算法知识视频讲解

heyJulian

#include<string.h>
/**
 * 返回最终的答案
 * @param s1 string字符串 表示初始的字符串
 * @param s2 string字符串 表示目标的字符串
 * @return int整型
 */
int solve(char* s1, char* s2 ) {
    int bias[4];//s1与s2差值
    int min = 200,maxTime = 26;//最小变换次数最大循环次数
    int i,j,k,p;//i j k p分别代表选择第0123元素的次数
    for(int i = 0; i < 4; i++){
        bias[i] = (s2[i] - s1[i] + 26) % 26;
    }
    for(i=0;i<maxTime;i++) {
        for(j=0;j<maxTime;j++) {
            for(k=0;k<maxTime;k++) {
                for(p=0;p<maxTime;p++) {
                    //四种方式变换的大小应与差值相同
                    if( (2*(j+k+p))%26 == bias[0] 
                       && (2*i+3*(k+p))%26 == bias[1]
                       && (3*i + 3*j + 5*p)%26 == bias[2] 
                       && (5*(i+j+k)%26 == bias[3]) ) {
                        min = min < i+j+k+p ? min : i+j+k+p; 
                    }
                }
            }
        }
    }
    return min;
}

发表于 2020-07-22 16:37:15 回复(0)