我需要编写一个解码换位密码的程序。一开始我有一个词，它是加密文本。 key 的长度等于接收到的字的-1 长度。 key 是随机的。
例子:
- >
input text:Uniz isvrh tiesiime ffrmfbi jz tpywjhpf gx ucs zgvey eoj e igpg himua xgxfx qbxo xgw b xihapbx vftx jt xik jpxq pl eo owpygfrit zvjgrhri input word: mark output:They could scarcely believe it possible at two yards and a half below water mark was a regular rent in the form of an isosceles triangle - >
input text:Qr oc cvtmxen ev Rga Asto vlg uwiuxksp acw cx kxu lgmilv input word:was output:On my arrival at New York the question was at its height - >
input text: Rt kolniz qufkbnx R gjvoczkm zqk kgobzkwin ul cnn suwyckx input word: effect output:In effect however I admitted the existence of the monster
对于示例 1 和 2，程序编译速度非常快，但是对于示例 3 该程序编译了很长时间，因为我有太多 for 循环。
#include <stdio.h>
#include<string.h>
#include<stdlib.h>
#include<ctype.h>
int main()
{
unsigned int i = 0;
int key[10];
unsigned int k = 0;
int check;
unsigned int j, jj, jjj, jjjj, jjjjj, jjjjjj;
int n = 50;
char slowo[10];
char plain[500], cipher[500];
fflush(stdin);
printf("Enter text:");
fgets(plain, 500, stdin);
printf("Enter word:");
fgets(slowo, 500, stdin);
if (strlen(slowo) == 4)
{
for (j = n; j != 0; j--)
{
key[0] = (j - 25);
for (jj = n; jj != 0; jj--)
{
key[1] = (jj - 25);
for (i = 0; i<strlen(plain); i++)
{
if (isalpha(plain[i]))
{
if (islower(plain[i]))
{
check = plain[i];
if (islower(plain[i]) && check + key[k]>96 && check + key[k]<123)
{
cipher[i] = (plain[i] + key[k] - 'a') % 26 + 'a';
}
else
{
check = 123 + (check - 97 + key[k]);
cipher[i] = (check - 'a') % 26 + 'a';
check = 0;
}
}
else
{
check = plain[i];
if (isupper(plain[i]) && check + key[k]>64 && check + key[k]<91)
{
cipher[i] = (plain[i] + key[k] - 'A') % 26 + 'A';
}
else
{
check = 91 + (check - 65 + key[k]);
cipher[i] = (check - 'A') % 26 + 'A';
check = 0;
}
}
}
else
if (isspace(plain[i]))
{
k--;
cipher[i] = plain[i];
}
k++;
if (k>strlen(slowo) - 3)//ostatniznak + \0
k = 0;
}
for (i = 0; i<strlen(plain); i++)
{
if (isspace(cipher[i]) && cipher[i + 1] == slowo[0] && cipher[i + 2] == slowo[1] && cipher[i + 3] == slowo[2] && isspace(cipher[i + 4]))
{
cipher[strlen(plain) - 1] = '\0';
printf("%s", cipher);
return 0;
}
}
}
}
}
if (strlen(slowo) == 5)
{
for (j = n; j != 0; j--)
{
key[0] = (j - 25);
for (jj = n; jj != 0; jj--)
{
key[1] = (jj - 25);
for (jjj = n; jjj != 0; jjj--)
{
key[2] = (jjj - 25);
for (i = 0; i<strlen(plain); i++)
{
if (isalpha(plain[i]))
{
if (islower(plain[i]))
{
check = plain[i];
if (islower(plain[i]) && check + key[k]>96 && check + key[k]<123)
{
cipher[i] = (plain[i] + key[k] - 'a') % 26 + 'a';
}
else
{
check = 123 + (check - 97 + key[k]);
cipher[i] = (check - 'a') % 26 + 'a';
check = 0;
}
}
else
{
check = plain[i];
if (isupper(plain[i]) && check + key[k]>64 && check + key[k]<91)
{
cipher[i] = (plain[i] + key[k] - 'A') % 26 + 'A';
}
else
{
check = 91 + (check - 65 + key[k]);
cipher[i] = (check - 'A') % 26 + 'A';
check = 0;
}
}
}
else
if (isspace(plain[i]))
{
k--;
cipher[i] = plain[i];
}
k++;
if (k>strlen(slowo) - 3)//ostatniznak + \0
k = 0;
}
for (i = 0; i<strlen(plain); i++)
{
if (isspace(cipher[i]) && cipher[i + 1] == slowo[0] && cipher[i + 2] == slowo[1] && cipher[i + 3] == slowo[2] && cipher[i + 4] == slowo[3] && isspace(cipher[i + 5]))
{
cipher[strlen(plain) - 1] = '\0';
printf("%s", cipher);
return 0;
}
}
}
}
}
}
if (strlen(slowo) == 6)
{
for (j = n; j != 0; j--)
{
key[0] = (j - 25);
for (jj = n; jj != 0; jj--)
{
key[1] = (jj - 25);
for (jjj = n; jjj != 0; jjj--)
{
key[2] = (jjj - 25);
for (jjjj = n; jjjj != 0; jjjj--)
{
key[3] = (jjjj - 25);
for (i = 0; i<strlen(plain); i++)
{
if (isalpha(plain[i]))
{
if (islower(plain[i]))
{
check = plain[i];
if (islower(plain[i]) && check + key[k]>96 && check + key[k]<123)
{
cipher[i] = (plain[i] + key[k] - 'a') % 26 + 'a';
}
else
{
check = 123 + (check - 97 + key[k]);
cipher[i] = (check - 'a') % 26 + 'a';
check = 0;
}
}
else
{
check = plain[i];
if (isupper(plain[i]) && check + key[k]>64 && check + key[k]<91)
{
cipher[i] = (plain[i] + key[k] - 'A') % 26 + 'A';
}
else
{
check = 91 + (check - 65 + key[k]);
cipher[i] = (check - 'A') % 26 + 'A';
check = 0;
}
}
}
else
if (isspace(plain[i]))
{
k--;
cipher[i] = plain[i];
}
k++;
if (k>strlen(slowo) - 3)//ostatniznak + \0
k = 0;
}
for (i = 0; i<strlen(plain); i++)
{
if (isspace(cipher[i]) && cipher[i + 1] == slowo[0] && cipher[i + 2] == slowo[1] && cipher[i + 3] == slowo[2] && cipher[i + 4] == slowo[3] && cipher[i + 5] == slowo[4] && isspace(cipher[i + 6]))
{
cipher[strlen(plain) - 1] = '\0';
printf("%s", cipher);
return 0;
}
}
}
}
}
}
}
if (strlen(slowo) == 7)
{
for (j = n; j != 0; j--)
{
key[0] = (j - 25);
for (jj = n; jj != 0; jj--)
{
key[1] = (jj - 25);
if (isspace(cipher[i]) && cipher[i + 1] == slowo[0] && cipher[i + 2] == slowo[1] && isspace(cipher[i + 7]))
{
jj--;
}
for (jjj = n; jjj != 0; jjj--)
{
key[2] = (jjj - 25);
for (jjjj = n; jjjj != 0; jjjj--)
{
key[3] = (jjjj - 25);
for (jjjjj = n; jjjjj != 0; jjjjj--)
{
key[4] = (jjjjj - 25);
for (i = 0; i<strlen(plain); i++)
{
if (isalpha(plain[i]))
{
if (islower(plain[i]))
{
check = plain[i];
if (islower(plain[i]) && check + key[k]>96 && check + key[k]<123)
{
cipher[i] = (plain[i] + key[k] - 'a') % 26 + 'a';
}
else
{
check = 123 + (check - 97 + key[k]);
cipher[i] = (check - 'a') % 26 + 'a';
check = 0;
}
}
else
{
check = plain[i];
if (isupper(plain[i]) && check + key[k]>64 && check + key[k]<91)
{
cipher[i] = (plain[i] + key[k] - 'A') % 26 + 'A';
}
else
{
check = 91 + (check - 65 + key[k]);
cipher[i] = (check - 'A') % 26 + 'A';
check = 0;
}
}
}
else
if (isspace(plain[i]))
{
k--;
cipher[i] = plain[i];
}
k++;
if (k>strlen(slowo) - 3)//ostatniznak + \0
k = 0;
}
for (i = 0; i<strlen(plain); i++)
{
if (isspace(cipher[i]) && cipher[i + 1] == slowo[0] && cipher[i + 2] == slowo[1] && cipher[i + 3] == slowo[2] && cipher[i + 4] == slowo[3] && cipher[i + 5] == slowo[4] && cipher[i + 6] == slowo[5] && isspace(cipher[i + 7]))
{
cipher[strlen(plain) - 1] = '\0';
printf("%s", cipher);
return 0;
}
}
}
}
}
}
}
}
if (strlen(slowo) == 8)
{
for (j = n; j != 0; j--)
{
key[0] = (j - 25);
for (jj = n; jj != 0; jj--)
{
key[1] = (jj - 25);
for (jjj = n; jjj != 0; jjj--)
{
key[2] = (jjj - 25);
for (jjjj = n; jjjj != 0; jjjj--)
{
key[3] = (jjjj - 25);
for (jjjjj = n; jjjjj != 0; jjjjj--)
{
key[4] = (jjjjj - 25);
for (jjjjjj = 0; jjjjjj != 0; jjjjjj--)
{
key[5] = (jjjjjj - 25);
for (i = 0; i<strlen(plain); i++)
{
if (isalpha(plain[i]))
{
if (islower(plain[i]))
{
check = plain[i];
if (islower(plain[i]) && check + key[k]>96 && check + key[k]<123)
{
cipher[i] = (plain[i] + key[k] - 'a') % 26 + 'a';
}
else
{
check = 123 + (check - 97 + key[k]);
cipher[i] = (check - 'a') % 26 + 'a';
check = 0;
}
}
else
{
check = plain[i];
if (isupper(plain[i]) && check + key[k]>64 && check + key[k]<91)
{
cipher[i] = (plain[i] + key[k] - 'A') % 26 + 'A';
}
else
{
check = 91 + (check - 65 + key[k]);
cipher[i] = (check - 'A') % 26 + 'A';
check = 0;
}
}
}
else
if (isspace(plain[i]))
{
k--;
cipher[i] = plain[i];
}
k++;
if (k>strlen(slowo) - 3)//ostatniznak + \0
k = 0;
}
for (i = 0; i<strlen(plain); i++)
{
if (isspace(cipher[i]) && cipher[i + 1] == slowo[0] && cipher[i + 2] == slowo[1] && cipher[i + 3] == slowo[2] && cipher[i + 4] == slowo[3] && cipher[i + 5] == slowo[4] && cipher[i + 6] == slowo[5] && cipher[i + 7] == slowo[6] && isspace(cipher[i + 7]))
{
cipher[strlen(plain) - 1] = '\0';
printf("%s", cipher);
return 0;
}
}
}
}
}
}
}
}
}
else {
printf("Error");
return 1;
}
}
我想优化代码以使其更快，但我不知道。
最佳答案
您的代码中有一些可能的优化 - 所谓的锁孔优化，但我宁愿更改您正在使用的算法。锁孔优化是小菜一碟，而且premature optimization is the root of all evil . 降低算法的复杂性几乎总是您的首要任务。然后，也只有到那时，您才能进行进一步的优化。
这里您知道 key 长度是(在第三个示例中)五，因为 crib effect 是六个字符；我们将 key 称为 12345。
我们将 key 与密文对齐，因为忽略了空格:
12 345123 4512345 1 23451234 512 345123451 23 451 2345123
Rt kolniz qufkbnx R gjvoczkm zqk kgobzkwin ul cnn suwyckx
我们可以现在在 O(n3) 中实现暴力巴贝奇解密使用线性方程系统:
x1 - 1 = R
x2 - 2 = t
x3 - 3 = k
x4 - 4 = o
x5 - 5 = l
x6 - 1 = n
...
x48 - 3 = x
但我们可以观察到我们只有一个词，其长度等于“effect”的长度 - 它是“kolniz”。 这意味着我们可以立即恢复 key :这就是“nikol - efeec”的区别。第一个符号 1 等于从 effect 的第二个 e 向前移动到 kolniz 的 n ，即9个位置。因此，当我们找到映射到 worm 的第一个符号的字母时，例如第一个“R”，我们从 R 返回 9 个位置，找到“I”。
上述算法大致为 O(n+m)，其中 n 是密文的长度，m 是 key 的长度。
假设我们有两个长度等于“effect”的单词，假设它们是“abcdef”和“ghijkl”。我们使用哪一个？
假设1:abcdef是effect的密文。如果这是真的，那么 'e' 的第一个符号的移位是 'a' 并且相同的移位必须将 'f' 变成 't'。
假设2:ghikl是effect的密文。如果这是真的，那么“e”的第一个符号的移位是“g”，相同的移位必须将“l”变成“t”。
两个假设都为真而我们无法确定哪个假设正确的概率是另一个词的第一个和最后一个字母具有与“e”和“t”相同的移位差异的概率' 例如，在我们的婴儿床中，第一个词是“效果”，另一个是“美洲狮”、“挽歌”、“哈洛”或“老爷车”。这些机会很少。
关于c - 换位密码编译太长，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/47728684/