杰拉斯的博客

[ACM实验五]ACM程序设计基础(3)

杰拉斯 杰拉斯 | 时间:2012-05-09, Wed | 8,247 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;
}

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

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

#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

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

相关文章

2 条评论 »

  1. That's an astute awsner to a tricky question

    1. Yep, the difficulty is how to converted the question into the idea of programming.