前言

其實道題在寒假的時候就做了，現在有機會發出來了。(〃‘▽’〃)

題目

思路

參考了大佬斜行查找的思路，為了便于觀察和敘述，我把楊輝三角形如圖排一下

1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1 1 10 45 120 210 252 210 120 45 10 1

從圖形上看，第一列全都是1，顯然沒什么查詢的價值，省略。。

每一行的第一個也都是1，也沒什么價值，省略。。

通過觀察發現，每個奇數行中間的數都是最大的，也是第一次出現的。也就是說從(1,2)開始每次坐標(+1,+2)上的數都是最早出現的，比如說2,6,20,70…

利用這個規律，我們先找到離要查找的數最近的那一列（差的絕對值最小 and 小于等于）

我們可以從2這個數的坐標(1,2)開始查找每一列最接近要查找的數的值，比如要查找21，我們先利用上面那個規律查找

首先21>2，坐標(+1,+2)來到(2,4)；

21>6，坐標(+1,+2)來到(3,6)；

21>20，坐標(+1,+2)來到(4,8)；

21<70，不移動坐標了，鎖定20這個數的坐標。

然后在20這一列(3,*)開始查找21,用二分查找的方法提高速度。突然發現在這一列中找不到21，只能將坐標往前移動一列來到15這個位置。

為什么不往后移動而是往前移動呢？是因為楊輝三角形的對稱的特點，往后找雖然可能找得到，但是一定不是最早出現的。

往前移動一列后，再次利用二分查找，發現找到了21，而且這 個21的位置一定是最早出現的。

我這里用排列組合的方法求楊輝三角，就不用每次都把一個完整的楊輝三角計算出來了,最后再用坐標求位置

題解

import sys n = int(input()) t = 1#n為1直接出結果 if n == 1:print(1)sys.exit()#先找到是哪一列比較接近 l = 0 #行 r = 0 #列 while t < n:t = 1l += 2r += 1for i in range(l-r+1,l+1):#排列組合求楊輝三角t *= ifor i in range(2,r+1):t //= i ## print(t)if t == n:print(l*(l+1)//2+r+1)sys.exit() else:l -= 2r -= 1t = 1#再用二分法在豎列中查找 j = l k = n while t != n:l = (j+k)//2t = 1for i in range(l-r+1,l+1):#排列組合求楊輝三角t *= ifor i in range(2,r+1):t //= iif j < k: #二分查找if t > n:k = l - 1elif t < n:j = l + 1elif t == n: #找到就退出，以免坐標錯亂break;else: #這里是該列找不到，就往前一列找r -= 1k = n ## print(t)print(l*(l+1)//2+r+1) #利用坐標求位置

總結

以上是生活随笔為你收集整理的第十二届蓝桥杯 杨辉三角形 Python题解 满分的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。