C 中帕斯卡三角的列印

帕斯卡三角是教授工程學的學生時的經典示例之一。它有很多種解釋。其中一種著名的解釋就是使用二項式方程。

三角形外的所有值都視為零 (0)。第一行為 0 1 0，而只有 1 出現在帕斯卡三角中，0 是不可見的。第二行是透過新增 (0+1) 和 (1+0) 獲得的。輸出被夾在兩個零之間。該過程將一直持續到達到所需級別。

可以透過二項式定理推匯出帕斯卡三角形。我們可以使用組合和階乘來實現這一點。

演算法

假設我們很清楚階乘，我們以分步方式研究繪製帕斯卡三角形的基本概念 −

START
  Step  1 - Take number of rows to be printed, n.
  Step  2 - Make outer iteration I for n times to print rows
  Step  3 - Make inner iteration for J to (N - 1)
  Step  4 - Print single blank space " "
  Step  5 - Close inner loop
  Step  6 - Make inner iteration for J to I
  Step  7 - Print nCr of I and J
  Step  8 - Close inner loop
  Step  9 - Print NEWLINE character after each inner iteration
  Step 10 - Return
STOP

虛擬碼

我們可以針對以上演算法推匯出如下虛擬碼 −

procedure pascals_triangle

   FOR I = 0 to N DO
      FOR J = 0 to N-1 DO
         PRINT " "
      END FOR

      FOR J = 0 to I DO
         PRINT nCr(i,j)
      END FOR

      PRINT NEWLINE
   END FOR

end procedure

實現

讓我們實現此程式的全部內容。我們實現階乘函式 (非遞迴) 和 ncr (組合)。

#include <stdio.h>

int factorial(int n) {
   int f;
   
   for(f = 1; n > 1; n--)
      f *= n;
      
   return f;
}

int ncr(int n,int r) {
   return factorial(n) / ( factorial(n-r) * factorial(r) );
}

int main() {
   int n, i, j;

   n = 5;

   for(i = 0; i <= n; i++) {
      for(j = 0; j <= n-i; j++)
         printf("  ");
         
      for(j = 0; j <= i; j++)
         printf(" %3d", ncr(i, j));

      printf("\n");
   }
   return 0;
}

輸出應如下所示 −

               1
             1   1
           1   2   1
         1   3   3   1
       1   4   6   4   1
     1   5  10  10   5   1