蓝桥杯算法训练杨辉三角形-python题解

# 求组合数
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

n=100
result=[[0 for i in range(n)]for j in range(n)]
ans=[]
for i in range(n):
    for j in range(i+1):
        if j==0:
            result[i][j]=1

        elif i==j:
            result[i][j]=1

        else:
            result[i][j]=result[i-1][j-1]+result[i-1][j]
            
        ans.append(result[i][j])
            

m=int(input())
a=ans.index(m)
print(a+1)