C語言實現楊輝三角前n行（低時間復雜度）

楊輝三角定義

楊輝三角，是二項式系數在三角形中的一種幾何排列，初中的時候我們學過它的每一個數都是上一行兩個數之和，如圖

已知楊輝三角行數

如果我們已知要求的楊輝三角的行數，則可以列出一個二維數組，根據其特性求出每個位置的值

未知楊輝三角行數

但是如果行數是未知量，則這種方法就不能使用了

在高中知識里面，我們學過楊輝三角的每一行的排列恰好為二項式的系數，忘記二項式的可以在下面復習一下，知道的可以直接看下方代碼

楊輝三角二項式特性

與楊輝三角聯系最緊密的是二項式乘方展開式的系數規律，即二項式定理。例如在楊輝三角中，第3行的三個數恰好對應著兩數和的平方的展開式的每一項的系數，第4行的四個數恰好依次對應兩數和的立方的展開式的每一項的系數，即$(a+b{)}^3=a^3+3a^{2}b+3a{b}^2+b^3$，以此類推。
所以根據二項式定理，第n行的m個數可表示為$C_{n?1}^{m?1}$，即為從n-1個不同元素中取m-1個元素的組合數
而二項式中$C_n^m=\frac{n!}{m!?(n?m)!}$,在程序過程中可以簡化這一步驟降低時間復雜度，每一項都可以通過前一項得出，即$C_n^m=C_n^{m?1}?\frac{n?m+1}{m}$，由此可以得出下面的程序

#include<stdio.h>int main () {int x,y;//分別為楊輝三角的x行,第y個;int temp;//求某行某個的值時,暫存該行上一個的值int n;//保存輸入的行數scanf("%d",&n);//輸出要輸出的楊輝三角行數printf("1\n"); //輸出第一行for(x=2;x<=n;x++,temp=1){//從第二行開始每行輸出printf("1 ");//輸出每一行的開頭for(y=2;y<x;y++){//根據二項式定理,第x行第y項等于第y-1項乘以x-y+1,再除以y-1 printf("%d ",temp=temp*(x-y+1)/(y-1));}printf("1\n");}return 0;}

得出結果

總結

以上是生活随笔為你收集整理的C语言输出杨辉三角前n行（低时间复杂度）的全部內容，希望文章能夠幫你解決所遇到的問題。

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