例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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/438607.html
標籤：C