[ACM实验二]C++STL泛型编程（2）

杰拉斯 | 时间：2012-03-31, Sat | 5,700 views
编程算法　

实验项目：C++STL泛型编程（2）
实验目的：掌握C++STL string向量容器等的应用。
实验要求：使用VC++6.0实现实验要求。
实验内容：

1.输入一串小写字母字符，输出该字符串中每个字母的个数，例如输入：aadsef，输出：
a 2
d 1
e 1
f 1
s 1

2. 古代一位国王和他的张、王、李、赵、钱五位将军一同出外打猎，各人的箭上都刻有自己的姓氏。打猎中，一只鹿中箭倒下，但不知是何人所射。
张说："或者是我射中的，或者是李将军射中的。"
王说："不是钱将军射中的。"
李说："如果不是赵将军射中的，那么一定是王将军射中的。"
赵说："既不是我射中的，也不是王将军射中的。"
钱说："既不是李将军射中的，也不是张将军射中的。"
国王让人把射中鹿的箭拿来，看了看，说："你们五位将军的猜测，只有两个人的话是真的."请判断是谁射中鹿。

3. 输入一个自然数Ｎ（2≤N≤9），要求输出如下的魔方阵，即边长为N行N列，元素取值为1至N*N，1在左上角，呈顺时针方向依次放置各元素。如输入4，输出：
1 2 3 412 13 14 511 16 15 610 9 8 7

附加题：
给定一个N×M的整数矩阵，找出其中具有最大和的子矩阵。一个矩阵的和就是矩阵中所有元素的和，子矩阵是指位于整个矩阵中任何一个1×1或更大的连续的子矩阵。例如，在矩阵
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
中其最大子矩阵在其左下角：
9 2
-4 1
-1 8
其和为15。

1.输入一串小写字母字符，输出该字符串中每个字母的个数。

#include<iostream>
#include<iterator>
#include<string>
#include<map>
using namespace std;
int main(){
	string s;
	cin >> s;
	map<char, int> m;	//使用map作为容器，以键值自动排序。
	for(int i = 0; i < s.length(); ++i)
		++m[s[i]];
	for(map<char, int>::iterator it = m.begin(); it != m.end(); ++it)
		cout << (*it).first << " " << (*it).second << endl;
	return 0;
}

2. 古代一位国王和他的张、王、李、赵、钱五位将军一同出外打猎，各人的箭上都刻有自己的姓氏。打猎中，一只鹿中箭倒下，但不知是何人所射。
张说："或者是我射中的，或者是李将军射中的。"
王说："不是钱将军射中的。"
李说："如果不是赵将军射中的，那么一定是王将军射中的。"
赵说："既不是我射中的，也不是王将军射中的。"
钱说："既不是李将军射中的，也不是张将军射中的。"
国王让人把射中鹿的箭拿来，看了看，说："你们五位将军的猜测，只有两个人的话是真的."请判断是谁射中鹿。

只要能将其转换为编程思路，这道题其实很简单。

#include<iostream>
using namespace std;
int main(){
	bool b[5] = {0};	//五位将军射中情况，即其中有一个元素为true，其它为false
	char n[11] = "张王李赵钱";
	for(int i = 0; i < 5; ++i){
		int num = 0;
		b[i] = 1;	//使第i个元素为true，即第i位将军射中
		if(b[0] || b[2])	//五个if分别判断五位将军说的话是否为真，若为真则正确猜测数加1
			++num;
		if(!b[4])
			++num;
		if(b[3] || b[1])
			++num;
		if(!b[3] && !b[1])
			++num;
		if(!b[0] && !b[2])
			++num;
		if(num == 2){	//若正确猜测数为2，即有两个将军的话是真的，则输出
			cout << n[i * 2] << n[i * 2 + 1] << "将军射中的。"  << endl;	//一个中文占两个字节
		}
		b[i] = 0;
	}
	return 0;
}

3. 输入一个自然数Ｎ（2≤N≤9），要求输出如下的魔方阵，即边长为N行N列，元素取值为1至N*N，1在左上角，呈顺时针方向依次放置各元素。

如输入4，输出：1 2 3 412 13 14 511 16 15 610 9 8 7

#include<iostream>
#include<iomanip>
using namespace std;
int main(){
	int r[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};	//方向数组，共四个
	int n, i = 0, k = 0, row = 0, col = 0;
	cin >> n;
	int **a = new int*[n];
	for(i = 0; i < n; ++i){
		a[i] = new int[n];
		for(int j = 0; j < n; ++j){
			a[i][j] = 0;	//将数组全部元素附为0
		}
	}
	i = 1;
	while(i <= n * n){
		a[row][col] = i;
		int newrow = row + r[k][0];
		int newcol = col + r[k][1];
		if(newrow < 0 || newcol < 0 || newrow == n || newcol == n || a[newrow][newcol] > 0){
			k = (k + 1) % 4;	//当超出范围或下一个位置有数字，转换方向
		}
		row += r[k][0];
		col += r[k][1];
		++i;
	}
	for(i = 0; i < n; ++i){
		for(int j = 0; j < n; ++j){
			cout << setw(4) << a[i][j];
		}
		cout << endl;
	}
	return 0;
}

附加题：
给定一个N×M的整数矩阵，找出其中具有最大和的子矩阵。一个矩阵的和就是矩阵中所有元素的和，子矩阵是指位于整个矩阵中任何一个1×1或更大的连续的子矩阵。例如，在矩阵
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
中其最大子矩阵在其左下角：
9 2
-4 1
-1 8
其和为15。

思路：用一个四个元素的数组来保存子矩阵左上角的坐标及大小，通过递归列出四个元素的所有组合情况，把所有情况的矩阵之和计算出来，并将最大值及最大解保存在变量中，最后输出。

#include<iostream>
using namespace std;
int max[4] = {0};
int maxnum = -2147483648;
int sum(int **&a, int r[4]){	//矩阵求和
	int num = 0;
	for(int i = 0; i < r[2]; ++i){
		for(int j = 0; j < r[3]; ++j){
			num += a[r[0] + i - 1][r[1] + j - 1];
		}
	}
	return num;
}
void printmax(int **&a){
	int num = 0;
	for(int i = 0; i < max[2]; ++i){
		for(int j = 0; j < max[3]; ++j){
			cout << a[max[0] + i - 1][max[1] + j - 1] << " ";
		}
		cout << endl;
	}
}
void Solve(int **&a, int r[4], int n, int m, int k = 0){
	if(k == 4){	//数组4个元素全部赋值完毕，递归结束
		if(r[0] + r[2] < n + 2 && r[1] + r[3] < m + 2){	//若子矩阵不超出矩阵范围
			//cout << r[0] << r[1] << r[2] << r[3] << endl;	//输出递归结果以查看递归情况是否无误
			int s = sum(a, r);
			if(s > maxnum){	//若该子矩阵和大于当前最大的矩阵和，储存该子矩阵行列高宽及矩阵和
				max[0] = r[0];
				max[1] = r[1];
				max[2] = r[2];
				max[3] = r[3];
				maxnum = s;
			}
		}
		return;
	}
	if(k % 2 == 0){	//模2等于0的为数组中下标为0、2的元素，为子矩阵的行、高
		for(int i = 1; i <= n; ++i){	//子矩阵的行、高不得超出矩阵总行数
			r[k] = i;
			Solve(a, r, n, m, k + 1);	//下层递归
		}
	}else{	//不等于0的为子矩阵的列、宽
		for(int i = 1; i <= m; ++i){	//子矩阵的列、宽不得超出矩阵总列数
			r[k] = i;
			Solve(a, r, n, m, k + 1);	//下层递归
		}
	}
}
int main(){
	int n, m;
	cin >> n >> m;
	int **a = new int*[n];
	for(int i = 0; i < n; ++i){
		a[i] = new int[m];
		for(int j = 0; j < m; ++j){
			cin >> a[i][j];
		}
	}
	int r[4] = {0};	//四个元素分别代表子矩阵左上角的行、列、子矩阵的高、宽
	Solve(a, r, n, m);
	printmax(a);
	cout << maxnum << endl;
	system("pause");
	return 0;
}

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

杰拉斯的博客