ACM典型试题--古代密码(二)

旧城等待， 2022-09-17 12:21 105阅读 0赞

## 1. 题目描述 ##

古罗马帝国有两种简单的加密算法，第一种按照顺序替换，例如把a-y 分别替换成b-z，  
把z 替换成a，这样可以把VICTORIOUS 替换成WJDUPSJPVT。  
第二种是打乱顺序消息的顺序，例如<2, 1, 5, 4, 3, 7, 6, 10, 9, 8>的含义就是把第二个字  
符放在第一位，而把第一位的字符放到第二位，然后是第5 个字符，第4 个字符，…，可以  
把VICTORIOUS 替换成IVOTCIRSUO。  
后来发现同时使用两种算法， 加密效果更好。可以把VICTORIOUS 替换成  
JWPUDJSTVP。  
题目要求：能不能把第二行中的原文转换为第一行的密文。  
输入格式  
输入包括两行：第一行为加密后的密文，第二行原文。  
输出格式  
如果能够按此方法把第二行的原文转换为第一行的密文，则输出 YES，否则输出NO。  
输入样例  
JWPUDJSTVP  
VICTORIOUS  
输出样例  
YES

## 2. 题目分析和算法实现 ##

首先，要找出规律，第二种方法只会改变每个字符的位置，但是不会影响每个字符在字  
符串中出现的次数。例如A 在原来的字符串中出现3 次，那么通过第二种算法它出现的次  
数还是3 次。第一种算法虽然改变了字符串的内容，但是有些东西没有变化，例如原来字符  
串中的a、b、c 出现的次数分别n1、n2、n3，假设abc 替换def，则d、e、f 出现的次数应  
该是n1、n2、n3。所以只要保证相对位置上的字符出现的次数相同即可实现转换。  
统计输入信息第一行中每个字符出现的次数。使用长度为26 的数组表示，分别表示字  
母A 到字母Z 出现的次数，使用int\[\] a 表示。  
统计输入信息第二行中的每个字符出现的次数。使用长度为26 的数组表示，分别表示  
字母A 到字母Z 出现的次数，使用int\[\] b 表示。  
我们循环26 次，第j 次循环中，再循环比较a\[(i+j)%26\]与b\[i\]是否相同，如果都相同则

说明能够转换，输出YES 即可，退出外层循环，否则继续循环。如果26 次循环完之后，没有得到结果，输出NO。

## 3. 问题实现及代码分析 ##

#include<stdio.h>
    #include<string.h>
    void init(), work(), sort(), print();
    int sum1[120], sum2[120], sm1, sm2, count1[120], count2[120], bj;
    char s1[120], s2[120];
    int main() {
    	init();
    	work();
    	return 0;
    }
    void init() {
    	int i;
    	for(i = 1; i <= 119; ++i) {
    		sum1[i] = sum2[i] = count1[i] = count2[i] = 0;
    	}
    	sm1 = 0;
    	sm2 = 0;
    	gets(s1);
    	gets(s2);
    }
    void work() {
    	int i;
    	for(i = 0 ; i <= strlen(s1) - 1; ++i){
    		++sum1[s1[i] - 'A' + 1];
    		++sum2[s2[i] - 'A' + 1];
    	}
    	for(i = 1; i <= 26; ++i) {
    		if(sum1[i])
    			count1[++sm1] = sum1[i];
    		if(sum2[i])
    			count2[++sm2] = sum2[i];
    	}
    	if(sm1 != sm2) {
    		bj = 1;
    		print();
    	}
    	else {
    		sort();
    		bj = 2;
    		for(i = 1; i <= sm1; ++i)
    			if(count1[i] != count2[i]) {
    					bj = 1;
    				break;
    			}
    			print();
    	}
    }
    void print() {
    	if(bj == 1) printf("NO\n");
    	else
    		printf("YES\n");
    }
    void sort() {
    	int i, j, ch;
    	for(i = 1; i <= sm1; ++i )
    		for(j = i + 1; j <= sm1; ++j ) {
    			if(count1[i] > count1[j]) {
    				ch = count1[i];
    				count1[i] = count1[j];
    				count1[j] =ch;
    			}
    			if(count2[i] > count2[j]) {
    				ch = count2[i];
    				count2[i] = count2[j];
    				count2[j] =ch;
    			}
    		}
    }

## 4.结果 ##

![20131019121442265][]

[20131019121442265]: /images/20220828/5ed7fcf263f048c98cb877f4ef071548.png