代码收藏家技术教程 2022-07-25

【完美解析】蓝桥杯省赛杨辉三角形 python组找规律+二分查找+组合数

题目

看到最后如果还不懂你来打我~

分析

我们看到杨辉三角形很容易想到一个数的值等于它肩膀两个数的和。为此，可以不断通过前一行的数求出后一行的数，重复上面操作，直到找到目标为止。但是看了用例规模后发现其涉及到十的九次方，数值非常大，只有20%的用例才在10以内，如果以刚才枚举的方式求解的话得的分值并不高。因此可以看出，这是一道思维题，需要找出其中的规律来求解。

我们找找其中的规律，可以发现杨辉三角形具有以下特点:

1.对称性

杨辉三角形左右两边数字对称相等。

2.渐增性

越往中间数字越大，除最外层1外，越往下数字越大。

3.组合数
杨辉三角形里面的每一个元素都能用组合数表示。第N行的第M列可以表示成C(N-1,M-1)，如6在第5行的第3列，它对应的组合数就是C(5-1,3-1)，即C(4,2)。

思路

因为要找出第一次N出现的位置，根据对称性可知，N出现的位置必定在左边，因此只考虑左半边位置即可。因为越靠中间的数越大，所以我们可以从最中间的数，也就是从对称轴位置的数开始找。怎么找呢？斜着找。没错，就是斜着找。

我们先将三角形的右半部分去掉，然后再区分开每一斜行。

为什么要斜着找？

因为越靠近里面的斜行每一元素的值越大，而且总是较先出现的。以上图为例，6在倒数第二斜行出现了，他对应的位置是第5行第3列，也在倒数第三斜行出现了，对的位置是第7行第2列。很显然，倒数第二斜行的6的位置明显后于前者。出现这种情况的原因是每一斜行的增长速度不同，越靠近内行的数值增长速度越快。打个比方，同样做完一道题，内行的15分钟就做完了，外行的可能要花上1个小时。

为什么可以斜着找？

因为它们是有规律的：每一斜行的元素对应的列位置都没变。还是以6为例，6在第3列，6的斜行下一个元素10同样在第三列位置。（6：C(2, 4)， 10：C(2, 5)）。最后当我们找到元素后根据组合数规律就能反推出该元素在整个杨辉三角形的位置。

解决完上面的疑惑后，就要思考该怎么斜着找的问题了。在思考之前，我们先来看下斜行有哪些性质。

在每一斜行中，越往下的元素越大。也就是说在中心轴位置的元素反而是斜行中最小的。（这里作为斜行的起始点）
在中心对称轴位置的元素组合数下限是上限的两倍（除1外）。如 2 = C（1,2）,6 = C（2,4）,10 = C（3:6）…即C（k，2k）
斜行同样可以用组合数表示。从全是1的最外层元素开始数（假设是第0斜行），则第 i 斜行的元素可以用组合数C(i, P)表示(P >= 2i，因为斜行的第一个元素就是C(i，2i)，见性质2。因此，斜行中每往下一个元素P就加1,i不变）。

怎么斜着找？

因为在内斜行中元素总是较先出现的，所以我们要从内斜行开始从内往外开始找，找到第0行全是1的最外层为止。内到什么程度才行？内到第16行。我们知道在中心对称轴的元素是每一斜行中最小的，它的特点是 C( k, 2k ) 。

如果该斜行最小元素都已经超出10的9次方那么剩下的元素都是大于10的9次方的，也就是说这一斜行是没有意义的，不用考虑。经计算，只有16斜行以内的数才符合条件。

我们已经确定了起始元素，根据杨辉三角的渐增性，越往下元素值越大，说明就是有序的，可以使用二分查找提高查找效率。这里有二分查找和排序的模板，大家可以参考下我的这篇文章。

确定了查找的起点位置后就要确定查找的终点位置。我们以目标值作为我们的组合数下限。回到分析中的第三小点：组合数下限表示元素所在横行数-1，那么如果以目标值作为终点位置的组合数下限已经是非常大了，就算找不到也有第1斜行（全为1的是第0斜行）的公差为1的等差数列守着，所以一定能找到。

因为相同斜行的组合数上限不变，我们不断更换组合数下限的值，直到最后找到目标值即可。找到目标值后，根据此时的组合数上下限，结合杨辉三角组合数性质即可求出元素所在位置。以20: C( 3, 6 )为例，它是，第7行第4个元素。前面6行是个公差为1的等差数列，根据求和公式即可求出6行共有几个元素，最后再加4即为20所在位置。

精度问题: 因为最后输出的是整数，所以最后要使用int将计算结果中小数点后面的数去除。假设一个元素在几十万横行后面找到，那么求他的位置时它的前N项和是非常大的，但他所在的列数可能非常小，如果将他们相加后再转化为整型的话会造成数据丢失，导致与实际结果不符。这样放在蓝桥杯上的话只能够拿八十分。辛辛苦苦做出来的题却因为精度问题不能拿满分，属实可惜。这个问题我也想了好久没找到问题根源，最后看到一篇文章点醒了我，感谢 @Py小郑 。

代码

# 求组合数
def C(a, b):  # a为上限， b为下限
    res = 1
    for i in range(a):
        res *= b / a
        # 当结果大于目标值时无需继续运算，提高效率
        if res > target:
            return res
        b -= 1
        a -= 1
    return res


# 二分查找目标元素
def search(k):
    # 起始下限，也就是对称轴位置的元素
    low = 2 * k
    # 终点下限
    high = target
    # 可能出现high 小于 low 的情况，比如目标值很小，但行数还在十多行的时候。
    # 这时候直接判断该斜行第一个元素也就是对称轴位置的元素的值是否是目标值即可。
    if high <= low and C(k, low) != target:
        return False
    while low <= high:
        mid = low + (high - low) // 2
        val = C(k, mid)
        if val > target:
            high = mid - 1
        elif val < target:
            low = mid + 1
        else:
            # 根据等差数列前N项和公式求出前面有多少个元素，然后再加上他所在的列数
            print(int(mid * (mid + 1) / 2) + k + 1)
            return True
    return False


target = int(input())
# range第二个参数必须是-1，因为第0斜行才有1。
for i in range(16, -1, -1):
    if search(i):
        break