C++算法记录册

1.递归剪枝法

输入一串数组，找到数组中子序列的的最大顺序

fun_back(int a[], int i, int n) {
	int max_len = 1;
	for (int j = i + 1; j < n; j++)
		if (a[j] > a[i])
			if (max_len < fun_back(a, j, n) + 1)
				max_len = fun_back(a, j, n) + 1;
	return max_len;
	if (i == n - 1)
		return max_len;

}

int main() {
	int n, max = 0; //输入个数
	cin >> n;
	int a[n];
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < n; i++) {
		//max > fun_back(a, i, n) ? max : fun_back(a, i, n);
		if (max < fun_back(a, i, n))
			max = fun_back(a, i, n);
	}
	cout << max;
}

例如输入了5个数

1.主函数对每个变量都都进行遍历一遍，是根节点的所有子节点是标识一处。

2，递归函数只需要判断当前节点是否大于父节点，如果满足，就调用下一个递归，如果不满足就返回值。

最后，递归要判断是否到了底层，就是到第四层的时候。要么就往下走，要么就退出。不然最后一层已经在无法向下递归了。

2，二维数组遍历法

对角线遍历

int main() {
	int n, m; //输入个数
	cin >> n;
	cin >> m;
	int temp = 0;
	int a[n][m];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++)
			cin >> a[i][j];
	}
	//输入n行m列的二位数组

	for (int p = 0; p < n + m - 1; p++) {
		for (int i = 0; i <= p; i++)
			if (i < n && (p - i) < m) {
				cout << a[i][p - i] << " ";
			}
		cout << endl;
	}



}

我以其中的的交点作为二维坐标的焦点。

1：我们可以发现所有线上的坐标，在同一条坐标之上的值总是相等的。

2：我们要遍历这个值，是M+N-1。对角线分别对应着一个值

3：注意绿线坐标的部分，如果是4*4的二维坐标，则这个坐标最开始是a[4][0],这个坐标是并不存在的。所以需要判断所遍历的值是否在二维坐标的范围之内。

类似地，还可以把代码改为蛇形遍历

int main() {
	int n, m; //输入个数
	cin >> n;
	cin >> m;
	int temp = 0;
	int a[n][m];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++)
			cin >> a[i][j];
	}
	//输入n行m列的二位数组

	for (int p = 0; p < n + m - 1; p++) {
		if (p % 2 == 0) {
			for (int i = 0; i <= p; i++)
				if (i < n && (p - i) < m) {
					cout << a[i][p - i] << " ";
				}
			cout << "#" << p << endl;
		} else {
			for (int i = p; i >= 0; i--)
				if (i < n && (p - i) < m) {
					cout << a[i][p - i] << " ";
				}
			cout << "#" << p << endl;
		}

		cout << endl;
	}



}

如下图：