CUMTOJ算法实验作业

问题 A: 凯撒加密法

题目描述

凯撒加密法,或称恺撒加密、恺撒变换、变换加密,是一种最简单且最广为人知的加密技术。它是一种替换加密的技术,明文中的所有字母都在字母表上向后(或向前)按照一个固定数目进行偏移后被替换成密文。
例如,当偏移量是左移3的时候:
明文字母表:ABCDEFGHIJKLMNOPQRSTUVWXYZ
密文字母表:DEFGHIJKLMNOPQRSTUVWXYZABC
使用时,加密者查找明文字母表中需要加密的消息中的每一个字母所在位置,并且写下密文字母表中对应的字母。需要解密的人则根据事先已知的密钥反过来操作,得到原来的明文。例如:
明文:THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG
密文:WKH TXLFN EURZQ IRA MXPSV RYHU WKH ODCB GRJ
现在给定你一个字符串S(长度不会超过1000000)和一个整数k(-1000000000<=k<=1000000000),分别代表接受者收到的密文和在加密该密文时向后的偏移量,你的任务是计算出原来的明文
注意:只有字母在加密时才会发生偏移,其它字符保持不变

输入

输入包含多组数据,其中第一行为数据组数T(T<=10)
每组数据第一行为一个字符串S,由数字、字母以及常见字符组成(不含空格),第二行为一个整数k代表加密时向后的偏移量(|S|<=1000000,-1000000000<=k<=1000000000)

输出

对每组数据,输出一行字符串,代表输入中的密文对应的明文。

样例输入

1
DEFGHIJKLMNOPQRSTUVWXYZABC
3

样例输出

ABCDEFGHIJKLMNOPQRSTUVWXYZ

思路

此题就是将输入的字符串传到string类型的变量str中,然后对数组进行操作即可。

1
str[i][j] = 'A' + (str[i][j] - 'A' - offset[i] + 26) % 26;

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <string>
using namespace std;
const int max_num = 10;
int main()
{
int i, j, T;
string str[max_num];
int offset[max_num];
cin >> T;
for(i = 0; i < T; i++)
{
cin >> str[i];
cin >> offset[i];
offset[i] %= 26;
}
for(i = 0; i < T; i++)
{
for(j = 0; j < str[i].length(); j++)
{
if(str[i][j] >= 'A' && str[i][j] <= 'Z')
str[i][j] = 'A' + (str[i][j] - 'A' - offset[i] + 26) % 26;
else if(str[i][j] >= 'a' && str[i][j] <= 'z')
str[i][j] = 'a' + (str[i][j] - 'a' - offset[i] + 26) % 26;
}
cout << str[i] << endl;
}
return 0;
}

问题 B: Vigenère 密码

题目描述

16 世纪法国外交家 Blaise de Vigenère 设计了一种多表密码加密算法——Vigenère 密码。Vigenère 密码的加密解密算法简单易用,且破译难度比较高,曾在美国南北战争中为南军所广泛使用。

在密码学中,我们称需要加密的信息为明文,用 MM 表示;称加密后的信息为密文,用 CC 表示;而密钥是一种参数,是将明文转换为密文或将密文转换为明文的算法中输入的数据,记为 kk。 在 Vigenère 密码中,密钥 kk 是一个字母串,k=k1k2…kn。当明文 M = m1m2…mn 时,得到的密文 C = c1c2…cn ,其中 ci = mi ® ki,运算 ® 的规则如下表所示:

Vigenère 加密在操作时需要注意:

1 ® 运算忽略参与运算的字母的大小写,并保持字母在明文 MM 中的大小写形式;
2 当明文 MM 的长度大于密钥 kk 的长度时,将密钥 kk 重复使用。 例如,明文 M=M=Helloworld,密钥 k=k=abc时,密文 C=C=Hfnlpyosnd。

输入

第一行为一个字符串,表示密钥 kk,长度不超过 100100,其中仅包含大小写字母。

第二行为一个字符串,表示经加密后的密文,长度不超过 10001000,其中仅包含大小写字母。

输出

输出共 11 行,一个字符串,表示输入密钥和密文所对应的明文。

样例输入

CompleteVictory
Yvqgpxaimmklongnzfwpvxmniytm

样例输出

Wherethereisawillthereisaway

思路

此题就是将输入的字符串传到string类型的变量str中,然后对数组进行操作即可。

1
text += 'a' + (secretText[i] - 'a' - Key[i % KeyLength] + 'a' + 26) % 26;

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <string>
using namespace std;
int main()
{
int i, KeyLength, secretTextLength;
string Key, secretText, text;
cin >> Key;
cin >> secretText;
KeyLength = Key.length();
secretTextLength = secretText.length();
for(i = 0; i < KeyLength; i++) //k to all lowwer
{
if(Key[i] >= 'A' && Key[i] <= 'Z')
Key[i] = Key[i] - 'A' + 'a';
}
for(i = 0; i < secretTextLength; i++)
{
if(secretText[i] >= 'A' && secretText[i] <= 'Z')
text += 'A' + (secretText[i] - 'A' - Key[i % KeyLength] + 'a' + 26) % 26;
else
text += 'a' + (secretText[i] - 'a' - Key[i % KeyLength] + 'a' + 26) % 26;
}
cout << text << endl;
return 0;
}

问题 C: 简单的密码

题目描述

密码是按特定法则编成,用以对通信双方的信息进行明密变换的符号。密码是隐蔽了真实内容的符号序列。其实就是把用公开的、标准的信息编码表示的信息通过一种变换手段,将其变为除通信双方以外其他人所不能读懂的信息编码,这种独特的信息编码就是密码。
现在我们定义一种非常简单的密码,它的长度固定为n(n<=30)并且每一位只能由数字0或者数字1组成,但是有一个特殊的要求:一个密码序列中至少要有连续的3个0出现才可以,否则就是无效的。现在给定你密码序列的长度n,你的任务是计算长度为n的序列能产生多少种不同的并且有效的密码?

输入

输入包含多组数据,每组数据只有一个正整数n(1<=n<=30)代表密码序列的长度,单独占一行。

输出

对每组数据,输出一个整数,代表长度为n的序列能产生的不同密码的种类数。

样例输入

4
5
6

样例输出

3
8
20

思路

先给出递推式:

1
f[i] = 2 * f[i - 1] + (1 << (i - 4)) - f[i - 4];

为什么呢?

  1. 2*f[i-1]上一步如果已经有连续3个0了,那这一步可0可1;
  2. (1<<(i-4))-f[i-4]什么时候会有除上一种情况之外的解呢?答案是当上一步最后3位为100的时候,这三位(i-1位、i-2位、i-3位)已经定死了,那我们只要考虑到i-4位时不符合条件的数量,即总的减去符合条件的(2^(i-4)-f[i-4])。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
using namespace std;
int main()
{
int i, n;
int f[32] = {0, 0, 0, 1};
while(~scanf("%d",&n))
{
for(i = 4; i <= 30; i++)
{
f[i] = 2 * f[i - 1] + (1 << (i - 4)) - f[i - 4];
}
cout << f[n] << endl;
}
return 0;
}

问题 D: 有趣的素数

题目描述

素数被广泛地应用于密码学中,所谓的公钥就是将想要传递的信息在编码时加入砠数,编码之后传给收信人,任何人收到此信息之后,若没有此收信人所拥有的秘钥,则在解密的过程中将会因为分解质因数过久而无法破解信息,可见素数在密码学中的重要性。
现在给你n(2<=n<=16)个正整数1,2,3…n,你的任务是把这n个正整数组成一个环,使得任意相邻的两个整数之和为一个素数,输出有多少种合法方案。

输入

多组输入数据,每组数据只有一个正整数n(2<=n<=16)代表有n个正整数 1,2,3…n

输出

对每组数据,输出一个整数,代表有多少种不同的可行方案数。

样例输入

6
8

样例输出

2
4

提示

对于输入样例中的6,有以下2种合法方案(首尾相连构成一个环)

1 4 3 2 5 6

1 6 5 2 3 4

对于输入样例中的8,有以下4种合法方案(首尾相连构成一个环)

1 2 3 8 5 6 7 4

1 2 5 8 3 4 7 6

1 4 7 6 5 8 3 2

1 6 7 4 3 8 5 2

思路

当层数等于n时跳出(往回走,即回溯) 判断下首尾加起来是不是素数,若是,则ans++; 否则什么也不做。
中间约束剪枝就是判断当前和前面一个加起来是不是素数,不是的话就直接剪。
普通的素数判定方法可能会TLE,所以判断素数最好打个表。原问题n最大是16,所以打30多的表就够了(16+15==31)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <cstring>
using namespace std;
int n, ans, last;
bool visited[32];
bool isPrime[40]={0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0};
int main()
{
void pc(int cur);
while(~scanf("%d",&n))
{
memset(visited, 0, sizeof(visited));
ans = 0;
last = 1;
pc(1);
cout << ans << endl;
}
return 0;
}
void pc(int cur)
{
int i;
if(cur == n && isPrime[1 + last])
{
ans++;
return;
}
for(i = 2; i <= n; i++)
{
if(!visited[i] && isPrime[last + i])
{
int t = last;
last = i;
visited[i] = true;
pc(cur + 1);
visited[i] = false;
last = t;
}
}
}

问题 E: 数据加密

题目描述

密码学是研究编制密码和破译密码的技术科学。研究密码变化的客观规律,应用于编制密码以保守通信秘密的,称为编码学;应用于破译密码以获取通信情报的,称为破译学,总称密码学。密码是通信双方按约定的法则进行信息特殊变换的一种重要保密手段。依照这些法则,变明文为密文,称为加密变换;变密文为明文,称为脱密变换。密码在早期仅对文字或数码进行加、脱密变换,随着通信技术的发展,对语音、图像、数据等都可实施加、脱密变换。
现在要求你用下面给定的方法对数据实现加密。给定长度为n的字符串S(1<=n<=2000,S中只有大写字母)作为明文,要求构造一个字符串T作为密文,起初T是一个空串,之后反复执行以下任意操作

1.从S的头部删除一个字符,加入到T的尾部
2.从S的尾部删除一个字符,加入到T的尾部

最后S会变成空串,T会变成一个长度为n的字符串作为密文。当然并非所有的构造方案都是符合条件的,我们要求构造出的密文T的字典序尽可能小,你能找出这个字典序最小的密文吗?

输入

输入包含多组数据,每组数据占两行,第一行为一个整数n(1<=n<=2000)代表字符串S的长度,第二行为一个长度为n的字符串S代表明文,保证S中只有大写字母

输出

对每组数据,输出一行字符串,代表构造出的字典序最小的密文T

样例输入

6
ACDBCB

样例输出

ABCBCD

提示

字典序是指从前往后比较两个字符串大小的方法。首先比较第1个字符,如果不同则第1个字符更小的字符串更小,如果相同则继续比较第2个字符……如此继续,来比较整个字符串的大小

思路

当头和尾不等的时候好选,关键就是头和尾一样怎么办?
仔细想想,容易发现,假设头指针为i,尾指针为j,如果相同,则比较i+1和j-1,如果再相同,继续下去……
我们可以写个循环,如果相同继续比较,不同就跳出。头小flag置为true,否则置为false。
其实T字符串根本不用存,直接输出即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
using namespace std;
int main()
{
int n, k;
char str[2005], ans[2005];
while(~scanf("%d", &n))
{
cin >> str;
int i = 0, j = n - 1;
while(i <= j)
{
bool flag = false;
for(k = 0; i + k < j - k; k++)
{
if(str[i + k] < str[j - k])
{
flag = true;
break;
}
if(str[i + k] > str[j - k])
break;
}
if(flag)
cout << str[i++];
else
cout << str[j--];
}
cout << endl;
}
return 0;
}

声明

本文参考了下面大佬的文章
https://comydream.github.io/2018/10/20/algorithm-meets-crypt/


转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达,可以邮件至 xingshuaikun@163.com。

×

喜欢就点赞,疼爱就打赏