[ACM実験二]C++STL汎用プログラミング(2)

実験項目:C++STL汎用プログラミング(2)実験目的:C++STL stringベクトル容器等の応用を把握する.実験要求:VC++6.0を用いて実験要求を実現する.実験内容:
1.小文字の文字列を入力し、その文字列の各文字の個数を出力します.例えば、入力:aadsef、出力:a 2 d 1 e 1 f 1 s 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.古代のある王は彼の張、王、李、趙、銭の5人の将軍と一緒に狩りに出かけ、各人の矢には自分の姓が刻まれていた.狩り中、鹿が矢で倒れたが、誰が撃ったのか分からない.張さんは「私が撃ったのか、李将軍が撃ったのか」と言った.王は「銭将軍が撃ったのではない」と言った.李さんは「趙将軍が撃ったのでなければ、王将軍が撃ったに違いない」と話した.趙さんは「私が撃ったのではなく、王将軍が撃ったのではない」と言った.金さんは「李将軍が撃ったわけでもないし、張将軍が撃ったわけでもない」と言った.王は鹿に当たった矢を持ってきて、見て、「あなたたち5人の将軍の推測は、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.自然数N(2≦N≦9)を入力すると、辺長はN行N列、元素取値は1からN*N、1は左上隅にあり、時計回り方向に各元素を順次配置する.例えば、入力4、出力:1 2 3 412 13 511 16 6109 8

#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を1つ与える×Mの整数行列は,その中で最大和を持つサブ行列を探し出す.1つのマトリクスの和は、マトリクス内のすべての要素の和であり、サブマトリクスは、マトリクス全体に位置する任意の1を指す.×1以上の連続サブマトリクス.例えば、行列0−2−7 0 9 2−6 2−4 1−4 1−1−18 0−2におけるその最大サブ行列の左下角:9 2−4 1−18の和は15である.
構想:1つの4つの要素の配列でサブマトリクスの左上角の座標と大きさを保存し、4つの要素のすべての組合せ状況を再帰的にリストすることによって、すべての状況のマトリクスの和を計算し、最大値と最大解を変数に保存し、最後に出力する.

#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;
}

原文住所(本人ブログ):
http://lanfei.sinaapp.com/2012/03/316.html