TeilyMa's BlogHomeArchivesTagsCategories
杭电2015年计算机复试真题
|文章
字数总计: 2.1k|阅读时长: 8 分钟

注意：此复试题目是根据CSDN博客逃离地球的小小呆上发布的回忆版整理复原。为了恢复试题的原貌，我根据试题要求进行合理的脑补，按照oj系统的风格补全了试题的Problem Description、Input、Output、Sample Input、Sample Out等内容，并加入了详解、具体的代码实现。因为是复原版，不能保证当时的题目就是这么呈现的，也不能说明考场上的试题就是oj风格叙述的，仅供大家参考。有什么错误、不合理的地方欢迎指出。
原创不易，还请大家多支持

第一题

Problem Description

给定一个字符串,计算字符串中数值的个数并求和。

Input

输入的字符串中不仅包含数字、字母还包含了负号，若紧跟负号的是一个数值，则表示这是一个负数，若后面跟着的不是数字，则不表示什么。有多组测试用例，每组占一行

Output

输出字符串中所有的数字之和，每组输出占一行

Sample Input

312ab-2-9-a
ccd---584hdu6com-1

Sample Output

301
-597

这道题并没有涉及太多算法、思想上的问题，而是注重考察对基本逻辑的判断能力。首先我们可以遍历输入的字符串，并用一个变量index记录字符串中每个数字的起始指针（索引）。当遍历到i个字符不是数字且不是负号时数字起始指针index就自增1。若第i个字符是负号，且后面其的字符不是数字，index也自增1。直到第i个字符是数字，index就停止增加，这样我们就记录了数字的起始位置。得到数字的起始位置之后，只需判断第i+1个字符是不是数字就可得到数字的终止指针（坐标），累加到sum输出就可以了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <stdio.h>
#include <stdlib.h>
#include <string>
#define IsNumber(x) x>='0'&&x<='9' //宏定义判断字符是否是数字
using namespace std;
int main() {
	char str[10001];
	while (scanf("%s",&str)!=EOF)
	{
		string temp = str;
		int sum = 0;
		int index = 0;//字符串中数字开始的指针
		int len = strlen(str);
		for (int i = 0; i < len; i++)
		{
			if (!(IsNumber(temp[i])) && temp[i] != '-')//若该字符不是数字且不是负号
				index++;//数字开始指针后移
			else
			{
				if (temp[i]=='-'&& !(IsNumber(temp[i+1])))//若负号后不是数字
					index++;//数字开始指针后移
				else if(!(IsNumber(temp[i + 1])))//若下一个字符不再是数字
				{
					sum += atoi(temp.substr(index, i - index + 1).data());//累加结果
					index = i + 1;
				}
			}	
		}
		printf("%d\n", sum);
	}
	return 0;
}

第二题

Problem Description

给定一个数字矩阵，如果上下左右数值相同，则表示是一个连通的区域。求矩阵中连通块的数量。

Input

输入有多组测试实例，每组输入有两行。第一行是两个整数n、m，表示矩阵的行数、列数,接下来输入的是n*m阶矩阵，矩阵中的元素用空格隔开。当输入的n、m都是0时结束

Output

输出该矩阵中的连通块的数量，每组输出占一行

Sample Input

5 6
4 4 4 4 4 4
4 2 3 3 1 4
4 2 2 3 1 4
4 2 3 3 1 4
4 4 4 4 4 4

Sample Output

4

这是一道有关深搜的问题，与《王道论坛计算机考研机试指南》第六章例6.6基本相同。首先对图上所有位置均设置一个标记位，表示该位置是否已经被计算过。这样我们按从左至右、从上往下的顺序依次遍历地图上所有位置，若该点未被标记，则所有与其直接相邻、或者间接相邻的相同数字与其一起组成一个块，该块即为一个我们需要计算的块，将该块中所有的相同数字标记为已经计算。这样，当所有的位置被遍历过后，我们即得到了所需的答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <stdio.h>
int maze[101][101]; //保存地图信息
bool mark[101][101]; //为图上每一个点设立一个状态
int n, m; //地图大小为n*m
int go[][2] = { 1,0,-1,0,0,1,0,-1}; //四个相邻点与当前位置的坐标差
void DFS(int x, int y) //递归遍历所有与x,y直接或间接相邻的相同的数
{
	for (int i = 0; i < 4; i++)
	{
		int nx = x + go[i][0];
		int ny = y + go[i][1];
		if (nx<1 || nx>n || ny<1 || ny>m)	continue;//若该坐标超出矩阵范围则丢弃
		if (maze[nx][ny] != maze[x][y])	continue;//若扩展的字符与当前字符不同则丢弃
		if (mark[nx][ny])	continue;//若该块计算过
		mark[nx][ny] = true;//标记已计算
		DFS(nx, ny);//递归查询与其相邻的点
	}
}
int main() {
	while (scanf("%d%d", &n, &m))
	{
		if (n == 0 && m == 0) break;
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
				scanf("%d", &maze[i][j]);// 第 i 行地图信息保存在 maze[i][1] 到maze[i][m]中
		for (int i = 1; i <= n; i++)  //初始化所有位置为未被计算
			for (int j = 1; j <= m; j++) 
				mark[i][j] = false;
		int ans = 0;//计数器
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
			{
				if (mark[i][j])	continue;//若该块计算过
				DFS(i, j);
				ans++;//答案递增				
			}
		printf("%d\n", ans);
	}
	return 0;
}

细心的人可能会发现这样一个问题，当输入是这个样子的时候：

Sample Input

2 3
1 2 3
4 5 6

通过该程序运行出的结果是6！这显然有些不符合我们对这道题的理解（当然题目本身也就没叙述清楚）。如果题目说：当出现2个及以上相同字符时才算一个联通块时，那我们仅需设置一个标志，在DFS查找时若一次也没有扩展到其周围的位置，那么这个这个块就是孤立的，同时在计算块的数量时加以判断，就可得出在这种题设条件下的答案，下面是改进后的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <stdio.h>
int maze[101][101]; //保存地图信息
bool mark[101][101]; //为图上每一个点设立一个状态
int n, m; //地图大小为n*m
int go[][2] = { 1,0,-1,0,0,1,0,-1}; //四个相邻点与当前位置的坐标差
bool flag = false;//设置一个标志位，记录该点是否扩展到了其他位置
void DFS(int x, int y) //递归遍历所有与x,y直接或间接相邻的相同的数
{
	for (int i = 0; i < 4; i++)
	{
		int nx = x + go[i][0];
		int ny = y + go[i][1];
		if (nx<1 || nx>n || ny<1 || ny>m)	continue;//若该坐标超出矩阵范围则丢弃
		if (maze[nx][ny] != maze[x][y])	continue;//若扩展的字符与当前字符不同则丢弃
		if (mark[nx][ny])	continue;//若该块计算过
		mark[nx][ny] = true;//标记已计算
		flag = true;//已扩展到其他位置
		DFS(nx, ny);//递归查询与其相邻的点
	}
}
int main() {
	while (scanf("%d%d", &n, &m))
	{
		if (n == 0 && m == 0) break;
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
				scanf("%d", &maze[i][j]);// 第 i 行地图信息保存在 maze[i][1] 到maze[i][m]中
		for (int i = 1; i <= n; i++)  //初始化所有位置为未被计算
			for (int j = 1; j <= m; j++) 
				mark[i][j] = false;
		int ans = 0;//计数器
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
			{
				if (mark[i][j])	continue;//若该块计算过
				DFS(i, j);
				if (flag)//若不是孤立的块则将其计算在内
				{
					ans++;//答案递增
					flag = false;
				}
			}
		printf("%d\n", ans);
	}
	return 0;
}
文章作者: Teily
文章链接: https://teily.cn/article/HDU2015.html
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 TeilyMa's Blog！
杭电复试考试相关