快捷導(dǎo)航

python如何打印楊輝三角及輸出第m行第k個數(shù)

更新時間：2023年08月10日 09:08:56 作者：qiuqiu1027

這篇文章主要介紹了python如何打印楊輝三角及輸出第m行第k個數(shù)問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教

python打印楊輝三角及輸出第m行第k個數(shù)

1.計算到m行，打印出k項

第m行有m項，m是正整數(shù)，因此k一定不會大于m，這個需求需要保存m行的數(shù)據(jù)，那么可以使用一個嵌套結(jié)構(gòu)[[],[],[]]

m=int(input('行>>>'))
k=int(input('第幾個數(shù)>>>'))
triangle=[]
for i in range(m):
    row=[1]                #所有行都以1開頭
    triangle.append(row)
    if i==0:
        continue
    for j in range(1,i):
        row.append(triangle[i-1][j-1]+triangle[i-1][j])
    row.append(1)
#print("--------------------------------")    #可以間隔開
print(triangle)
#print("--------------------------------")
print("第%d行第%d個數(shù)為：%d"%(m,k,triangle[m-1][k-1]))

輸出結(jié)果：

行>>>5
第幾個數(shù)>>>4
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
第5行第4個數(shù)為：4

2.m行k列的值，C(m-1，k-1)組合數(shù)

組合數(shù)方式：根據(jù)楊輝三角的定理，第n行的m個數(shù)(m>0且n>0)可表示為C(n-1，m-1)，即為從n-1個不同元素中取m-1個元素的組合數(shù)組合數(shù)公式：有m個不同的元素，任意取n(n≤m)個元素，記作C(m，n)，則C(m，n)=m!/(n!(m-n)!) =C(m,m-n)

m = int(input('行>>>'))
k = int(input('列>>>')) #  則C(n,r)=C(m-1,k-1)=(m-1)!/((k-1)!(m-r)!)= n!/(r!(n-r)!)
n = m - 1
r = k - 1
d = n - r
targets = []    #r, n-r, n
factorial = 1   #可以加入k為1或m的判斷，返回1
for i in range(1,n+1):
    factorial *= i
    if i == r:
        targets.append(factorial)
if i == d:
        targets.append(factorial)
if i == n:
        targets.append(factorial)
print(targets[2]//(targets[0]*targets[1]))

輸出結(jié)果：

行>>>5
列>>>4
4

只打印楊輝三角

1.基本方法

下一行是上一行所有元素兩兩相加得到，兩端再添加上1

n = int(input('>>'))
tiangle=[[1],[1,1]]              #預(yù)先定義前兩行
for i in range(2,n):
    per=tiangle[i -1]
    cur = [1]                             #創(chuàng)建新行，首位為1
    for j in range(i-1):                  #循環(huán)添加中間值
        cur.append(per[j]+per[j+1])
    cur.append(1)                         #末位添加1
    tiangle.append(cur)
print(tiangle)                            #將新生成的行添加到總列表

輸出結(jié)果：

5
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]

2.對稱法

一次性開辟出空間，先算出前一半的值，然后對稱賦值

一次性開辟出第n行所需空間然后算值替換，比循環(huán)迭代append添加更高效。每次只推算一半，時間復(fù)雜度更低

n = int(input('>>'))
triangle = [[1],[1,1]]
for i in range(2,n):
    row = [1]*(i + 1)                 #打印第n行先創(chuàng)建出n個元素列表
    pre = triangle[i - 1]
    for j in range(i//2):           #推算該行前一半的值
        val = pre[j] + pre[j + 1]
        row[j + 1] = val
        row[ - j - 2] = val               #對稱賦值
    triangle.append(row)
print(triangle)

輸出結(jié)果：

5[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]

3.單行覆蓋

在上面對稱法的基礎(chǔ)上降低空間復(fù)雜度

一次性開辟好n個長度的空間，每次推算新行時不生成新的列表，在原來的基礎(chǔ)上賦值替換。

n = int(input('>>'))
row = [1]*n                 #一次性開辟空間
for i in range(n):
    z = 1
    for j in range(i//2):
        val = z +row[j+1]    #計算出來的新值會影響后面的計算，使用臨時變量置換一下
        z = row[j+1]
        row[j+1]=val
        row[i-j-1]=val     #對稱賦值    row[j+1]=row[i-j-1]
    print(i,end='\t')
    print(row[:i+1])     #最后在總列表中截取當前計算的行長度打印出來

輸出結(jié)果：