[ACM实验五]ACM程序设计基础（3）

杰拉斯 | 时间：2012-05-09, Wed | 8,873 views
编程算法　

实验项目：ACM程序设计基础(3)
实验目的：掌握C++程序设计基础。
实验要求：使用VC++6.0实现实验要求。
实验内容：

1.为了对信件保密，需要对信件进行加密，加密方法是每个字母加5，如A写成F，B写成G。输入一行加密的英文句子，输出其解密英文句子，例如：
输入：NS BFW, JAJSYX TK NRUTWYFSHJ FWJ YMJ WJXZQY TK YWNANFQ HFZXJX
输出：IN WAR, EVENTS OF IMPORTANCE ARE THE RESULT OF TRIVIAL CAUSES
（提示：getline 是一个函数，它可以接受用户的输入的字符，直到已达指定个数，或者用户输入了特定的字符。它的函数声明形式（函数原型）如下：
istream& getline(char line[], int size, char endchar = '\n');
char line[]：就是一个字符数组，用户输入的内容将存入在该数组内。
int size : 最多接受几个字符？用户超过size的输入都将不被接受。
char endchar :当用户输入endchar指定的字符时，自动结束。默认是回车符。
例如用string buf;来保存：getline( cin , buf ); 如果用char buf[ 255 ]; 来保存：cin.getline( buf, 255 )。）

2. 某售货员要到若干城市去推销商品，一直各城市之间的路程，他要选定一条从驻地出发，经过每个城市一遍，最后回到住地的路线，使总的路程最短。

3. Anagrams by Stack问题，见Anagrams by Stack。

1.为了对信件保密，需要对信件进行加密，加密方法是每个字母加5，如A写成F，B写成G。输入一行加密的英文句子，输出其解密英文句子。
例如：
输入：NS BFW, JAJSYX TK NRUTWYFSHJ FWJ YMJ WJXZQY TK YWNANFQ HFZXJX
输出：IN WAR, EVENTS OF IMPORTANCE ARE THE RESULT OF TRIVIAL CAUSES
（提示：getline 是一个函数，它可以接受用户的输入的字符，直到已达指定个数，或者用户输入了特定的字符。它的函数声明形式（函数原型）如下：
istream& getline(char line[], int size, char endchar = '\n');
char line[]：就是一个字符数组，用户输入的内容将存入在该数组内。
int size : 最多接受几个字符？用户超过size的输入都将不被接受。
char endchar :当用户输入endchar指定的字符时，自动结束。默认是回车符。
例如用string buf;来保存：getline( cin , buf ); 如果用char buf[ 255 ]; 来保存：cin.getline( buf, 255 )。）

这道题相当简单，需要注意的题目也已经说的很清楚了，就不再重复了。

#include<iostream>
#include<string>
using namespace std;

int main(){
	string s;
	while(getline(cin, s)){
		for(int i = 0; i < s.length(); ++i){
			if(s[i] >= 'A' && s[i] <= 'Z')
				if(s[i] - 5 < 'A')
					cout << (char)(s[i] - 5 + 26);
				else
					cout << (char)(s[i] - 5);
			else
				cout << s[i];
		}
		cout << endl;
	}
	return 0;
}

全排列的思路，递归到最后一步算出路径总长度。

#include<stdio.h>
#include<iostream>
using namespace std;
int m[4][4] = {
	{ 0, 30,  6,  4},
	{30,  0,  5, 10},
	{ 6,  5,  0, 20},
	{ 4, 10, 20,  0}};
int min = 0xffffff;
void BackTrake(int n, int k, int a[]){ //全排列
	int i;
	if(k == n - 1){
		int len = 0;
		for(i = 0; i < 4; ++i){ //计算路径长度
			len += m[a[i] - 1][a[(i + 1) % 4] - 1];
		}
		if(len < min) //如果小的话赋给min
			min = len;
		return;
		//printf("%d%d%d%d %d\n", a[0], a[1], a[2], a[3], len);
	}
	for(i = k; i < n; ++i){
		swap(a[k], a[i]);
		BackTrake(n, k + 1, a);
		swap(a[k], a[i]);
	}
}

int main(){
	int a[4] = {1, 2, 3, 4};
	BackTrake(4, 1, a); //因为据点确定是1点不变，因此从数组第二位开始全排列
	printf("%d\n", min); //输出结果
	return 0;
}

3. Anagrams by Stack问题，见Anagrams by Stack。

代码及思路详见文章[ACM_HDU_1515]Anagrams by Stack。

如需转载请注明出处：杰拉斯的博客

杰拉斯的博客