HJ53 杨辉三角的变形

提示：文章

前言

前期疑问：
本文目标：

---

一、背景

最近

二、

HJ53 杨辉三角的变形

2.1题目

简单 通过率：35.86% 时间限制：1秒 空间限制：32M

知识点基础数学

描述

1

1 1 1

1 2 3 2 1

1 3 6 7 6 3 1

1 4 10 16 19 16 10 4 1

以上三角的数阵，第一行只有一个数1，以下每行的每个数，是恰好是它上面的数、左上角数和右上角的数，3个数之和（如果不存在某个数，认为该数就是0）。

求第n行第一个偶数出现的位置。如果没有偶数，则输出-1。例如输入3,则输出2，输入4则输出3，输入2则输出-1。

数据范围： 1 \le n \le 10^9 \1≤n≤109

输入描述：

输入一个int整数

输出描述：

输出返回的int值

示例1

输入：4

输出：3

2.2 编写代码

第一版代码

#include <stdio.h>int GetArray(int line, int index)
{int arrayLen = 2 * line - 1;if (line == 1 && index == 1) {return 1;}if (index == 1 || index == arrayLen) {return 1;}if (index <= 0 || index > arrayLen) {return 0;}int lastIndex = index - 1;int num = GetArray(line - 1, lastIndex - 1) + GetArray(line - 1, lastIndex) + GetArray(line - 1, lastIndex + 1);
//    printf("line:%d, index:%d, num:%d\n", line, index, num);return num;
}int main()
{int line = 0;while (scanf("%d", &line) != EOF) {if (line == 1 || line == 2) {printf("-1");return 0;}int arrayLen = 2 * line - 1;int array[arrayLen];array[0] = 1;array[arrayLen - 1] = 1;array[1] = line - 1;array[arrayLen - 2] = line - 1;for (int i = 3; i <= arrayLen - 2; i++) {int lastLineIndex = i - 1;array[i - 1] = GetArray(line - 1, lastLineIndex - 1) + GetArray(line - 1, lastLineIndex) +GetArray(line - 1, lastLineIndex + 1);}for (int i = 0; i < arrayLen - 1; i++) {if (array[i] % 2 == 0) {printf("%d\n", i + 1);break;}}}return 0;
}

下述测试用例没有通过，超时了

用例输入 83

预期输出 2

针对上述测试用例，修改代码如下

第二版代码

#include <stdio.h>int GetArray(int line, int index)
{int arrayLen = 2 * line - 1;if (line == 1 && index == 1) {return 1;}if (index == 1 || index == arrayLen) {return 1;}if (index <= 0 || index > arrayLen) {return 0;}int lastIndex = index - 1;int num = GetArray(line - 1, lastIndex - 1) + GetArray(line - 1, lastIndex) + GetArray(line - 1, lastIndex + 1);
//    printf("line:%d, index:%d, num:%d\n", line, index, num);return num;
}int main()
{int line = 0;while (scanf("%d", &line) != EOF) {if (line == 1 || line == 2) {printf("-1");return 0;}int arrayLen = 2 * line - 1;int array[arrayLen];array[0] = 1;array[arrayLen - 1] = 1;array[1] = line - 1;array[arrayLen - 2] = line - 1;for (int i = 2; i <= arrayLen - 2; i++) {if (i == 2 || arrayLen - 2) {if ((line - 1) % 2 == 0) {printf("%d\n", i);break;}}int lastLineIndex = i - 1;array[i - 1] = GetArray(line - 1, lastLineIndex - 1) + GetArray(line - 1, lastLineIndex) +GetArray(line - 1, lastLineIndex + 1);if (array[i - 1] % 2 == 0) {printf("%d\n", i);break;}}}return 0;return 0;
}

下述代码没有通过

25/30 组用例通过

用例输入 100000

预期输出 3

实际输出

2.3 问题探究

针对上述的测试用例，我感觉使用递归应该行不通，栈消耗太大了，以及运行时间太久了。应该是要使用其他方法。

这时候我又突然想起来，《C和指针》书上介绍的使用栈将数字串打印的代码，需要再看下。

---

下面的是新的尝试

第三版代码

int GetLastLineNum(int line)
{if (line == 1) {return 1;}int array[3] = {0};array[0] = 1;array[1] = line - 1;int num = array[0] + array[1] + GetLastLineNum(line - 1);return num;
}int main()
{int line = 0;while (scanf("%d", &line) != EOF) {if (line == 1 || line == 2) {printf("-1");return 0;}int array[3] = {0};array[0] = 1;array[1] = line - 1;array[2] = GetLastLineNum(line - 1);for (int i = 0; i < 3; i++) {if (array[i] % 2 == 0) {printf("%d\n", i + 1);}}}return 0;
}

上述代码还是使用了递归，只是想降低递归的成本，因为我任务前三个元素就已经可以判断出偶数的位置，所以该方法是只求杨辉三角每一行的第三个元素，第三个元素是通过前三个元素相加得到的。但是对于用例100000还是不行。

第四版代码

int GetLastLineNum(int line)
{if (line == 1) {return 1;}int num = GetLastLineNum(line - 1) + line;return num;
}int main()
{int line = 0;while (scanf("%d", &line) != EOF) {if (line == 1 || line == 2) {printf("-1");return 0;}int array[3] = {0};array[0] = 1;array[1] = line - 1;array[2] = GetLastLineNum(line - 1) + line;for (int i = 0; i < 3; i++) {if (array[i] % 2 == 0) {printf("%d\n", i + 1);break;}}}return 0;
}

上述代码还是使用了递归，该方法是通过发现每行第三个元素一次为1 3 6 10 15，a[i] = a[i - 1] + i,依次创建了递归函数。但是对于用例100000还是不行。

第五版代码

// 这个应该就是递归吧
int GetLastLineNum(int line)
{if (line == 1) {return 0;}int total = 0;for (int i = 0; i < line; i++) {total += i;}return total;
}int main()
{int line = 0;while (scanf("%d", &line) != EOF) {if (line == 1 || line == 2) {printf("-1");return 0;}int array[3] = {0};array[0] = 1;array[1] = line - 1;array[2] = GetLastLineNum(line);for (int i = 0; i < 3; i++) {if (array[i] % 2 == 0) {printf("%d\n", i + 1);break;}}}return 0;
}

该方法是通过发现每行第三个元素一次为1 3 6 10 15，a[i] = 前面索引的求和。比如第三行的6 = 1 + 2 + 3。第四行的10 = 1 + 2 + 3 + 4。依此设计了迭代。

第六版代码

执行第五版代码发现还有高手

用例输入 66

预期输出 4

实际输出

三、

3.1

---

总结

未完待续