例73  Caesar 密码

问题描述

Julius Caesar 生活在充满危险和阴谋的年代。为了生存，他首次发明了密码，用于军队的消息传递。假设你是Caesar 军团中的一名军官，需要把Caesar 发送的消息破译出来、并提供给你的将军。消息加密的办法是：对消息原文中的每个字母，分别用该字母之后的第5个字母替换（例如：消息原文中的每个字母A都分别替换成字母F），其他字符不变，并且消息原文的所有字母都是大写的。

密码字母：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

原文字母：V W X Y Z A B C D E F G H I J K L M N O P Q R S T U

输入

最多不超过100个数据集组成。每个数据集由3部分组成：

起始行：START

密码消息：由1到200个字符组成一行，表示Caesar发出的一条消息

结束行：END

在最后一个数据集之后，是另一行：ENDOFINPUT

输出

每个数据集对应一行，是Caesar 的原始消息。

输入样例

START

NS BFW, JAJSYX TK NRUTWYFSHJ FWJ YMJ WJXZQY TK YWNANFQ HFZXJX

END

START

N BTZQI WFYMJW GJ KNWXY NS F QNYYQJ NGJWNFS ANQQFLJ YMFS XJHTSI NS WTRJ

END

START

IFSLJW PSTBX KZQQ BJQQ YMFY HFJXFW NX RTWJ IFSLJWTZX YMFS MJ

END

ENDOFINPUT

输出样例

IN WAR, EVENTS OF IMPORTANCE ARE THE RESULT OF TRIVIAL CAUSES

I WOULD RATHER BE FIRST IN A LITTLE IBERIAN VILLAGE THAN SECOND IN ROME

DANGER KNOWS FULL WELL THAT CAESAR IS MORE DANGEROUS THAN HE

        （1）编程思路。

        消息加密的办法是：对消息明文（原文）中的每个字母，分别用该字母之后的第5个字母替换，因此解密时，每个字母，分别用该字母之后的第21（26-5）个字母替换。对于消息密文字符串mess，每个字母解密时，可以用如下表达式简单完成。

          if(mess[i]>='A'&& mess[i]<='Z')

                mess[i]=(mess[i]-'A'+21)%26+'A';

        （2）源程序。

#include <stdio.h>

#include<string.h>

int main()

{

    char mess[201];

    int i,flag=0;

    while(1)

    {

           gets(mess);

           if(strcmp(mess,"ENDOFINPUT")==0)

                     break;

           if(strcmp(mess,"START")==0)

           {

                     flag = 1;

                     continue;

           }

           if(strcmp(mess,"END")==0)

           {

                     flag=0;

                     continue;

           }

           if(flag==1)

           {

               for(i=0;mess[i]!='\0';i++)

                 if(mess[i]>='A'&& mess[i]<='Z')

                          mess[i]=(mess[i]-'A'+21)%26+'A';

               puts(mess);

           }

     }

    return 0;

}

习题73

73-1  W的密码

问题描述

加密一条信息需要三个整数码：k1, k2 和 k3。字符[a-i] 组成一组，[j-r] 是第二组，其它所有字符（[s-z] 和下划线）组成第三组。 在信息中属于每组的字符将被循环地向左移动ki个位置。 每组中的字符只在自己组中的字符构成的串中移动。解密的过程就是每组中的字符在自己所在的组中循环地向右移动ki个位置。

例如对于信息 the_quick_brown_fox 以ki 分别为2，3和1进行加密。加密后变成 _icuo_bfnwhoq_kxert。下图显示了右旋解密的过程。

观察在组[a-i]中的字符，我们发现{i,c,b,f,h,e}出现在信息中的位置为{2,3,7,8,11,17}。当k1=2右旋一次后, 上述位置中的字符变成{h,e,i,c,b,f}。下表显示了经过所有第一组字符旋转得到的中间字符串，然后是所有第二组，第三组旋转的中间字符串。在一组中变换字符将不影响其它组中字符的位置。

所有输入字符串中只包含小写字母和下划线（_）。所有字符串最多100个字符。ki 是1~100之间的整数。

输入

输入包括多组测试用例。每个测试用例包括两行，第1行包括三个整数 k1，k2 和 k3，第2行是待解密的信息。输入的最后一行是由三个0组成的，表示输入结束。

输出

对于每组加密数据，输出它加密前的字符串。

输入样例

2 3 1

_icuo_bfnwhoq_kxert

1 1 1

bcalmkyzx

3 7 4

wcb_mxfep_dorul_eov_qtkrhe_ozany_dgtoh_u_eji

2 4 3

cjvdksaltbmu

0 0 0

输出样例

the_quick_brown_fox

abcklmxyz

the_quick_brown_fox_jumped_over_the_lazy_dog

ajsbktcludmv

         （1）编程思路。

        加密时，将密文中的字符分成三组，每组的字符将被循环地向左移动ki（i=1~3）个位置。这三组各自循环移位只会移到自己所在组中成员的位置，不会破坏其他组的顺序。因此可先求出密文字符串中每个组字符的个数、每组中每个字符在明文字符串中的下标，最后用mod循环移位求得明文字符串。

        定义数组int a[105],b[105],c[105];分别保存3个组中各字符在密文字符串中的下标，定义int num1,num2,num3;分别保存各组字符的个数。用如下的循环

               for (i=0;i<strlen(plaintext);i++)

              {

                     if(plaintext[i]>='a'&&plaintext[i]<='i')

                            a[num1++]=i;

                     else if(plaintext[i]>='j'&&plaintext[i]<='r')

                            b[num2++]=i;

                     else

                            c[num3++]=i;

              }

        求出每个组中字符的个数，并保存每个字符在字符串中的下标。

        之后，分别用3个循环对每组进行循环移位，得到解密后的原文。

       （2）源程序。

#include <stdio.h>

#include <string.h>

int main()

{

       int k1,k2,k3,num1,num2,num3,i;

       int a[105],b[105],c[105];

       char plaintext[105],ciphertext[105];

       while (1)

       {

              scanf("%d%d%d",&k1,&k2,&k3);

              if (k1==0 && k2==0 && k3==0) break;    

              memset(a,-1,sizeof(a));

              memset(b,-1,sizeof(b));

              memset(c,-1,sizeof(c));

              memset(ciphertext,0,sizeof(ciphertext));

              num1=num2=num3=0;

              scanf("%s",plaintext);

              for (i=0;i<strlen(plaintext);i++)

              {

                     if(plaintext[i]>='a'&&plaintext[i]<='i')

                            a[num1++]=i;

                     else if(plaintext[i]>='j'&&plaintext[i]<='r')

                            b[num2++]=i;

                     else

                            c[num3++]=i;

              }

              for (i=0;i<num1;i++)

                     ciphertext[a[(i+k1)%num1]]=plaintext[a[i]];

              for (i=0;i<num2;i++)

                     ciphertext[b[(i+k2)%num2]]=plaintext[b[i]];

              for (i=0;i<num3;i++)

                     ciphertext[c[(i+k3)%num3]]=plaintext[c[i]];

              ciphertext[strlen(plaintext)]='\0';

              printf("%s\n",ciphertext);

       }

    return 0;

}

73-2  古代密码

问题描述

古罗马帝国有一个拥有各种部门的强大政府组织。其中一个部门就是保密服务部门。为了保险起见，在省与省之间传递的重要文件中的大写字母是加密的。当时最流行的加密方法是替换和重新排列。

替换方法是将所有出现的字符替换成其它的字符。有些字符会替换成它自己。例如：替换规则可以是将“A”到“Y”替换成它的下一个字符，将“Z”替换成“A”，如果原词是 "VICTORIOUS"，则它变成 "WJDUPSJPVT"。

排列方法改变原来单词中字母的顺序。例如：将顺序<2 1 5 4 3 7 6 10 9 8> 应用到 "VICTORIOUS" 上，则得到"IVOTCIRSUO"。

人们很快意识到单独应用替换方法或排列方法加密，都是很不保险的。但是如果结合这两种方法，在当时就可以得到非常可靠的加密方法。所以，很多重要信息先使用替换方法加密，再将加密的结果用排列的方法加密。用两种方法结合就可以将"VICTORIOUS" 加密成"JWPUDJSTVP"。

考古学家最近在一个石台上发现了一些信息。初看起来它们毫无意义，所以有人设想它们可能是用替换和排列的方法被加密了。人们试着解读了石台上的密码，现在他们想检查解读的是否正确。他们需要一个计算机程序来验证，你的任务就是写这个验证程序。

输入

输入有两行。第一行是石台上的文字。文字中没有空格，并且只有大写英文字母。第二行是被解读出来的加密前的文字。第二行也是由大写英文字母构成的。

两行字符数目的长度都不超过100。

输出

如果第二行经过某种加密方法后可以产生第一行的信息，输出 "YES"，否则输出"NO"。

输入样例

JWPUDJSTVP

VICTORIOUS

输出样例

YES

        （1）编程思路。

        定义两个数组int a[26]={0},b[26]={0}分别保存输入两个字符串中各大写字母出现的次数，例如，a[0]的值是密文字符串中字母A出现的次数，b[0] 的值是明文字符串中字母A出现的次数。

        由于加密的方法是替换和重新排列，并且明文和密文中只有大写英文字母，因此，分别求得明文和密文中各大写字母（A~Z）出现的次数后，将数组a和b从小到大排列，若两个数组对应元素均相等，则输入的第二行信息经过某种加密方法后可以产生第一行的信息；否则，不能。设明文中字母A出现次数最多，加密时字母A被替换为字母E，则加密后字母E的出现次数一定最多，且两个次数值一定要相等，这样才可能完成加密。

        （2）源程序。

#include <stdio.h>

void sort(int a[],int n)

{

    int i,j,t;

    for (i=0;i<n-1;i++)

          for (j=0;j<n-1-i;j++)

                 if (a[j]>a[j+1])

                 {

                            t=a[j]; a[j]=a[j+1]; a[j+1]=t;

                 }

}

int main(void)

{

    int a[26]={0},b[26]={0},i;

    char mess1[101],mess2[101];

    scanf("%s%s",mess1,mess2);

    i=0;

    while (mess1[i]!='\0' && mess2[i]!='\0')

    {

        a[mess1[i]-'A']++;

        b[mess2[i]-'A']++;

        i++;

    }

    sort(a,26);

    sort(b,26);

    for(i=0; i<26;i++)

    {

       if(a[i]!=b[i]) break;

    }

    if (i==26)

          printf("YES\n");

    else

          printf("NO\n");

    return 0;

}

73-3  密码

问题描述

Bob 和 Alice 开始使用一种全新的编码系统。它是一种基于一组私有钥匙的。他们选择了n个不同的数a1，…，an，它们都大于0小于等于n。 加密过程如下：待加密的信息放置在这组加密钥匙下，信息中的字符和密钥中的数字一一对应起来。信息中位于i位置的字母将被写到加密信息的第ai个位置，ai是位于i位置的密钥。加密信息如此反复加密，一共加密 k 次。

信息长度小于等于n。如果信息比 n 短, 后面的位置用空格填补直到信息长度为n。

请你帮助 Alice 和 Bob 写一个程序，读入密钥，然后读入加密次数 k 和要加密的信息，按加密规则将信息加密。

输入

输入包括多个测试用例。每个测试用例第一行有一个数字n（0 < n <= 200），接下来的行包含n个不同的数字，数字都是大于0小于等于n的。下面每行包含一个k和一个信息字符串，它们之间用空格格开。每行以换行符结束，换行符不是要加密的信息。每个测试用例的最后一行只有一个0。最后一个测试用例只有一行，该行只有一个0，表示输入结束，无需处理。

输出

输出有多个块，每个块对应一个测试用例。每个块包含输入中的信息经过加密后的字符串，顺序与输入顺序相同。所有加密后的字符串的长度都是 n。 每一个块后有一个空行。

输入样例

10

4 5 3 7 2 8 1 6 10 9

1 Hello Bob

1995 CERC

0

0

输出样例

BolHeol  b

C RCE

         （1）编程思路。

        加密的方法是进行置换，对于置换可以先求各个循环节，一个循环节中的所有字符的置换是不会影响其他字符的。

        以输入样例中的数据“4 5 3 7 2 8 1 6 10 9”为例，可以看出，a[1]=4,a[4]=7,a[7]=1，即（1、4、7）是一个循环节，a[2]=5,a[5]=2，（2、5）也是一个循环节，…，（3）、（6、8）、（9、10）是另外的3个循环节。

        由于给定的加密次数k值可能会很大，因此可以编写函数int getm(int a[],int i)求出位置i所在循环节的长度m，由于循环节中有m个数，这样加密m次（置换m次），循环节中每个数又回到了初始位置，这样只需加密k%m次即可

       （2）源程序。

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

int getm(int a[],int i)

{

    int ret=1;

    int now=a[i]-1;

    while(now!=i)

    {

        ret++;

        now=a[now]-1;

    }

    return ret;

}

int main()

{

    int key[201];

    char src[201],dest[201];

    int n,i,k,m,kk,now;

    while (scanf("%d",&n) && n!=0)

    {

        for (i=0;i<n;i++)

            scanf("%d",&key[i]);

        while (scanf("%d",&k) && k!=0)

         {

              getchar();

              gets(src);

              for (i=strlen(src);i<n;i++)

                    src[i]=' ';

             src[n]='\0';

             for(i=0;i<n;i++)

              {

                m=getm(key,i);

                kk=k%m;

                now=i;

                while(kk--)

               {

                    now=key[now]-1;

                }

                dest[now]=src[i];

            }

            dest[n]='\0';

            printf("%s\n",dest);

         }

         printf("\n");

    }

    return 0;

}