[C++知识库]暑假C/C++作业Day1

1.填空题

数组定义为int a[4][5],则a[1]+3表示哪个元素的地址？

a[1]表示a[1] [0],而a[1]+3就是a[1][3]。

因为内存地址是按照a[1][0],a[1][1],a[1][2],a[1][3],a[1][4]来进行存储的，
所以+3是内存地址加3。

2.算法题：

要求：

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。时间复杂度O(row+col)

数组样例：
int arr[4][4] = {
1,2,8,9,
2,4,9,12,
4,7,10,13,
6,8,11,15
};

分析：

查找资料分析，大体有三种思路：
1.直接查找：每一个arr[i][j]与val进行比较，时间复杂度为o(m*n);
2.先按行再按列查找：arr[i][col-1]与val进行比较确定行，再按列进行查找，时间复杂度o(m+n);
3.按行再按列结合二分查找：按行确定行值，二分查找确定列值，时间复杂度o(m+lgn);

先给出第二种思路的算法思路：从右上角开始遍历，如果这个数字小于右上角的数，则列减1，如果大于右上角的数，则行加1。

#include<stdio.h>
void find(int a[4][4], int val) {
	int row = 0;        //行
	int col = 3;        //列
	while (row <= 3 && col >= 0) {           //从右上角开始遍历
		if (a[row][col] < val) {             //val是要找的那个数
			row++;
		}
		else if (a[row][col] > val) {
		    col--;
		}
		else if (a[row][col] == val) {
			printf("找到了！\n");
			break;
		}
		else 
			printf("未找到！\n");	
		}
	}
int main() {

	int a[4][4] = { { 1, 2, 8, 9 },
					{ 2, 4, 9, 12 },
					{ 4, 7, 10, 13 },
					{ 6, 8, 11, 15 }
	};
	find(a, 8);       //8可以换成数组中的任意一个数
	return 0;
}