[ACM实验二]C++STL泛型编程(2)
杰拉斯 | 时间:2012-03-31, Sat | 6,147 views编程算法
实验项目:C++STL泛型编程(2)
实验目的:掌握C++STL string向量容器等的应用。
实验要求:使用VC++6.0实现实验要求。
实验内容:
1.输入一串小写字母字符,输出该字符串中每个字母的个数,例如输入:aadsef,输出:
a 2
d 1
e 1
f 1
s 1
2. 古代一位国王和他的张、王、李、赵、钱五位将军一同出外打猎,各人的箭上都刻有自己的姓氏。打猎中,一只鹿中箭倒下,但不知是何人所射。
张说:"或者是我射中的,或者是李将军射中的。"
王说:"不是钱将军射中的。"
李说:"如果不是赵将军射中的,那么一定是王将军射中的。"
赵说:"既不是我射中的,也不是王将军射中的。"
钱说:"既不是李将军射中的,也不是张将军射中的。"
国王让人把射中鹿的箭拿来,看了看,说:"你们五位将军的猜测,只有两个人的话是真的."请判断是谁射中鹿。
3. 输入一个自然数N(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. 古代一位国王和他的张、王、李、赵、钱五位将军一同出外打猎,各人的箭上都刻有自己的姓氏。打猎中,一只鹿中箭倒下,但不知是何人所射。
张说:"或者是我射中的,或者是李将军射中的。"
王说:"不是钱将军射中的。"
李说:"如果不是赵将军射中的,那么一定是王将军射中的。"
赵说:"既不是我射中的,也不是王将军射中的。"
钱说:"既不是李将军射中的,也不是张将军射中的。"
国王让人把射中鹿的箭拿来,看了看,说:"你们五位将军的猜测,只有两个人的话是真的."请判断是谁射中鹿。
只要能将其转换为编程思路,这道题其实很简单。
3. 输入一个自然数N(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> 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 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; }
如需转载请注明出处:杰拉斯的博客
当前暂无评论 »