主要是算法题练习记录3……
加密问题
给定一个长度不超过80个字符的字符串s，用输入的密钥key对s进行加密。其中，s可包含大小写字母与其他非字母符号等，key为长度不超过12的全部由小写字母构成的字符串。加密规则为，先将key反转，然后将a-z这26个字母从a开始依次与反转后的key的每个字符对应，对应完毕后a-z中会有若干个字符无对应，则从a开始按照字母表的顺序给余下的字符对应值，对应时，若key中已出现过的字符则取下一个，直到a-z这26个字符都有对应为止。请见下面举例说明：
假设key为字符串‘welovencut’, 将它反转为：‘tucnevolew’
将a-z对应如下：
a b c d e f g h i j k l m n o p q r s t u v w x y z
t u c n e v o l e w a b d f g h i j k m p q r s x y
对于s中的大写字母，将其转换成小写字母后可按照上述规则进行加密，但输出时还要输出加密后的小写字母所对应的大写字母；s中的其他非字母符号则直接输出即可。
Input
输入为第一行为密钥key，余下的行每行表示一个待加密的字符串s，输入一个“#”表示输入结束。
Output
输出为被加密后的字符串，每行一个对应的加密结果。
welovencut
NCUT is a Great university!
How-Are-You?
FCPM ek t Ojetm pfeqejkemx!
Lgr-Tje-Xgp?
编码：
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
|
char s[26];
char tran_s[26];
bool is_in(char a)//判断a是否在输入密钥中存在
{
int i=0;
for(i;i<strlen(tran_s);i++)
{
if(tran_s[i]==a)
{
return true;
}
}
return false;
}
int main()
{
scanf("%s",s);
int i;
char cha;
int k=0;
for(i=0;i<strlen(s);i++)
{
tran_s[i]=s[strlen(s)-i-1];
}
printf("%s\n",tran_s);
for(i;i<26;i++)//构造26个字母对应密钥生成的对应字母
{
cha = 'a' + k;
if(!is_in(cha))
{
tran_s[i] = cha; //转换成对应的字符
}
else
i--;//如果在密钥中出现，则跳过改字母
k++;
}
printf("%s\n",tran_s);
char input[100];
gets(input);//读取空行
gets(input);
while(input[0]!='#')//用
{
for(i=0;i<strlen(input);i++)
{
if(input[i]>='A' && input[i]<='Z')//大写字母
{
printf("%c",'A'+ (tran_s[input[i]-'A']-'a'));//大写字母转成小写字母对应的加密字母->变成对应的大写字母
}
else if(input[i]>='a' && input[i]<='z')
printf("%c",tran_s[input[i]-'a']);
else
{
printf("%c",input[i]);
}
}
printf("\n");
gets(input);
}
}
|
组合数
C(m,n)=m!/(n!(m-n)!)
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
float fun(int n)//求阶乘
{
if(n==0 || n==1)
{
return 1;
}
else if(n>1)
{
return fun(n-1) * n;
}
}
int main()
{
int m,n,sum;
printf("请输入m,n:");
scanf("%d %d",&m,&n);
sum = fun(m)/(fun(n)*fun(m-n));//求组合数公式
printf("%d\n",sum);
}
|
但组合数过大时，不能通过组合数的计算公式C(m,n)=m!/(n!(m-n)!)直接来求(因为可能会溢出)，可以根据C(m,n)=C(m-1,n)+C(m-1,n-1),C(i,0)=1,c(i,i)=1来求，用a[i][j]来表示C(i,j)，通过循环求出来C(m,n)
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
int a[101][101];
int main()
{
int m,n,i,j;
scanf("%d %d",&m,&n);
for(i=0;i<=100;i++) //初始化C(i,0)=1,C(i,i)=1
{
a[i][0]=1;
a[i][i]=1;
}
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
a[i][j]=a[i-1][j-1]+a[i-1][j]; //循环
}
}
printf("%d\n",a[m][n]);
return 0;
}
|
拆分偶数
把一个偶数拆成两个不同素数的和，有几种拆法呢？
输入包含一些正的偶数，其值不会超过10000，个数不会超过500，若遇0，则结束。
input：
30
26
0
output：
3
2
首先，判断是否为素数；其次两个素数的和，若一个为i，则另一个为n-i，分别判断这两个数是否为素数即可。
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
|
int is_prime(int n)//判断是不是素数
{
for(int i=2;i<=sqrt(n);i++)
{
if(n%i==0)
return 0;
}
return 1;
}
int main()
{
int n,sum;
while(~scanf("%d",&n)&&n)
{
sum=0;
for(int i=2;i<n/2;i++)
{
if(is_prime(i)&&is_prime(n-i))
sum++;
}
printf("%d\n",sum);
}
return 0;
}
|