算法作业。
问题 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
提示
代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int k;
string s;
cin>>s;
cin>>k;
k=k%26;
int len=s.length();
for(int i=0;i<len;i++)
{
if(s[i]>='A'&&s[i]<='Z')
{
s[i]=s[i]-k;
if(s[i]<'A')
{
s[i]=s[i]+26;
}
if(s[i]>'Z')
{
s[i]=s[i]-26;
}
}
if(s[i]>='a'&&s[i]<='z')
{
s[i]=s[i]-k;
if(s[i]<'a')
{
s[i]=s[i]+26;
}
if(s[i]>'z')
{
s[i]=s[i]-26;
}
}
}
cout<<s<<endl;
}
}
问题 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 加密在操作时需要注意：
- ® 运算忽略参与运算的字母的大小写，并保持字母在明文 MM 中的大小写形式；
- 当明文 MM 的长度大于密钥 kk 的长度时，将密钥 kk 重复使用。 例如，明文 M=M=Helloworld，密钥 k=k=abc时，密文 C=C=Hfnlpyosnd。
输入
第一行为一个字符串，表示密钥 kk，长度不超过 100100，其中仅包含大小写字母。
第二行为一个字符串，表示经加密后的密文，长度不超过 10001000，其中仅包含大小写字母。
输出
输出共 11 行，一个字符串，表示输入密钥和密文所对应的明文。
样例输入
CompleteVictory
Yvqgpxaimmklongnzfwpvxmniytm
样例输出
Wherethereisawillthereisaway
提示
代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
char k[102],c[1002];
int i,j;
char temp;
cin>>k;
cin>>c;
for(i=0,j=0;c[j]!='\0';j++)
{
if(c[j]>='A'&&c[j]<='Z')
{
if(k[i]>='A'&&k[i]<='Z')
temp=(c[j]-'A'-(k[i]-'A')+26)%26+'A';
else
temp=(c[j]-'A'-(k[i]-'a')+26)%26+'A';
}
else
{
if(k[i]>='A'&&k[i]<='Z')
temp=(c[j]-'a'-(k[i]-'A')+26)%26+'a';
else
temp=(c[j]-'a'-(k[i]-'a')+26)%26+'a';
}
cout<<temp;
i++;
if(k[i]=='\0') i=0;
}
return 0;
}
问题 C: 简单的密码
题目描述
密码是按特定法则编成，用以对通信双方的信息进行明密变换的符号。密码是隐蔽了真实内容的符号序列。其实就是把用公开的、标准的信息编码表示的信息通过一种变换手段，将其变为除通信双方以外其他人所不能读懂的信息编码，这种独特的信息编码就是密码。
现在我们定义一种非常简单的密码，它的长度固定为n（n<=30）并且每一位只能由数字0或者数字1组成，但是有一个特殊的要求：一个密码序列中至少要有连续的3个0出现才可以，否则就是无效的。现在给定你密码序列的长度n，你的任务是计算长度为n的序列能产生多少种不同的并且有效的密码？
输入
输入包含多组数据，每组数据只有一个正整数n（1<=n<=30）代表密码序列的长度，单独占一行。
输出
对每组数据，输出一个整数，代表长度为n的序列能产生的不同密码的种类数。
样例输入
4
5
6
样例输出
3
8
20
提示
代码
#include<bits/stdc++.h>
using namespace std;
int dp[32] = {0,0,0,1,3,8,20,47,107,238,520,1121,2391,5056,10616,22159,46023,95182,196132,402873,825259,1686408,3438828,6999071,14221459,28853662,58462800,118315137,239186031,483072832,974791728};
int main()
{
int n;
while(cin>>n)
{
cout<<dp[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
代码
#include<bits/stdc++.h>
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};
void pc(int cur)
{
if(cur == n && isPrime[1+last])
{
ans++;
return;
}
for(int 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;
}
}
}
int main()
{
while(cin>>n)
{
memset(visited,0,sizeof(visited));
ans = 0;
last = 1;
pc(1);
cout<<ans<<endl;
}
return 0;
}
问题 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个字符……如此继续，来比较整个字符串的大小
代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
char str[2005],ans[2005];
while(cin>>n)
{
cin>>str;
int i = 0,j = n-1;
while(i <= j)
{
bool flag = false;
for(int 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;
}
