第十二屆藍橋杯 Python組 試題 G: 楊輝三角形
??大家好，我叫亓官劼（qí guān jié ），在GitHub & CSDN中記錄學習的點滴歷程，時光荏苒，未來可期，加油~博主目前僅在GitHub & CSDN中寫博客，唯一博客更新的地址為：亓官劼的博客 ，近期將逐漸同步刷題相關記錄到GitHub：Algorithmic-learning-records，大多是本人的刷題記錄，如果轉載請附上原文地址，謝謝，
由于學習作業的需要，演算法刷題將會逐漸由C++向Python3過度，正在過度中，如實作的不太優美，請見諒，
本文原創為亓官劼，請大家支持原創，部分平臺一直在惡意盜取博主的文章！！！
若需聯系博主，可以聯系本人微信：qiguanjie2015
時間限制: 5.0s 記憶體限制: 512.0MB
本題總分：20 分
【問題描述】
下面的圖形是著名的楊輝三角形：
如果我們按從上到下、從左到右的順序把所有數排成一列，可以得到如下數列：
1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, …
給定一個正整數 N，請你輸出數列中第一次出現 N 是在第幾個數？
【輸入格式】
輸入一個整數 N，
【輸出格式】
輸出一個整數代表答案，
【樣例輸入】
6
【樣例輸出】
13
【評測用例規模與約定】
對于 20% 的評測用例，1 ≤ N ≤ 10；
對于所有評測用例，1 ≤ N ≤ 1000000000，
解題思路
遞回，這里只需要保留當行的數值，就可以推出下一行，為了方便計算，可以在兩邊加0.當數量級到10^10時，當行的數也就100個不到，不會存在記憶體壓力，
演算法實作
n = int(input())
if n == 1:
print("1")
else:
a = [0,1,0]
index = 1
flag = True
while flag:
i = 1
tmp = []
while i < len(a):
t = a[i]+a[i-1]
tmp.append(t)
index += 1
if n == t:
print(index)
flag = False
break
i += 1
tmp.insert(0,0)
tmp.append(0)
a = tmp
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/277710.html
標籤：其他