In Mathematics, What Is Pascal's Triangle?

The Yanghui triangle is a geometric arrangement of the binomial coefficients in the triangle. It appears in the book "Detailed Nine Chapters of the Algorithm" written by Yang Hui, a mathematician from the Southern Song Dynasty in 1261. In Europe, Pascal (1623-1662) discovered this pattern in 1654, so this table is also called Pascal's triangle. Pascal's discovery was 393 years later than Yang Hui and 600 years later than Jia Xian. ^[1]

Yang Hui triangle, yes

Premise: the number of end and end of each line is 1.

(Different from n in the figure above, here the first line is defined as n = 1)

Each number is equal to the sum of the two numbers above it.
Each line of numbers is symmetrical to the left and right and gradually increases from 1.
The number in line n has n items.
There are [(1 + n) n] / 2 numbers in the first n rows.
The number of m in the nth row can be expressed as C (n-1, m-1) , which is the number of combinations of m-1 elements from n-1 different elements.

The mth number of the nth row is equal to the n-m + 1th number, as

Northern Song Dynasty

The Yang Hui triangle is easier in programming. The most common algorithms are recursive calculations using the previous line; there are also factorial calculations that use the correspondence between the combination and the combination, but the latter is slower and the factorial is prone to overflow. The programming output is mostly similar, so there are not too many screenshots added here.

The syntax between C, C ++, C #, and Java languages is also mostly similar, so we will not implement each algorithm in these languages. To change between versions of these languages, you only need to pay attention to some simple syntax and function name changes, such as C's int yh [M] [M] should be rewritten as Java's int [] [] yh = new int [ M] [M], C # 's int [,] yh = new int [M, M]; C printf should be replaced with Java's System.out.print, C #' s Console.Write, and the smarter cout in C ++.

C++ Yang Hui triangle C ++

 #include <iostream> #include <iomanip> using namespace std; int main () {const int n = 15; const int m = 2 * n-1; int arr [n + 1] [m] = {0}; for (int i = 0; i <n; i ++) {arr [i] [n-i- 1] = 1; arr [i] [n + i -1] = 1;} for (int i = 2; i <n; i ++) {for (int j = n-i + 1; j <n-2 + i; j = j + 2) arr [i] [j] = arr [i-1] [j-1 ] + arr [i-1] [j + 1];} int p; for (int i = 0; i <n; i ++) {for (int j = 0; j <n-i-1; j ++) cout << ""; p = 1; for (int j = n-i-1; p <i + 2; j = j + 2) {cout << setw (4) << arr [i] [j] < <""; p = p + 1;} cout << endl;} return 0;}

Bash Yang Hui Triangle Bash

  #! / bin / bash
 # Usage: ./pasTrig [number], if not specified, the number is 5.
 # Fill the specified number of spaces pad () {for ((k = 0; k <$ 1; k ++)); do echo -n ''; done;}
 # Layers and old and new layers lyrs = $ {1-5}
 prev [0] = 1
 curr [0] = 1 # The first one in each subsequent line is always one, no need to repeat the assignment # execute pad $ (((lyrs-1) * 2))
 echo 1
 for ((i = 2; i <= lyrs; i ++)); do # skip 1 and have processed pad $ (((lylys-i) * 2)) # padding spaces, please note that three or more digits will not be taken into account here Number, that is, the 14th layer will be chaotic curr [i] = 1
 printf '% -4d' $ {curr [0]}
 for ((j = 1; j <i-1; j ++)); do # Extreme values at end and end have been processed, skip ((curr [j] = prev [j-1] + prev [j]))
 printf '% -4d' $ {curr [j]}
 done
 printf '% -4d \ n' $ {curr [i]} # last and newline # move prev = ($ (curr [*]})
 done

Bash outputs Yang Hui triangle and uses nl to indicate line number

C# Yang Hui triangle C #

  class Program
 {
 public int yanghui (int value)
 {
 if (value <3) return 1;
 int [,] arry = new int [value, value];
 Console.WriteLine ("The array is:");
 for (int i = 0; i <value; i ++)
 {
 string str = "";
 str = str.PadLeft (value-i);
 Console.Write (str);
 for (int j = 0; j <= i; j ++)
 {
 if (i == j || j == 0)
 arry [i, j] = 1;
 else
 arry [i, j] = arry [i-1, j-1] + arry [i-1, j];
 Console.Write (arry [i, j] + "");
 }
 Console.WriteLine ();
 }
 }

 static void Main (string [] args)
 {
 Program p = new Program ();
 Console.WriteLine ("Please enter an array value:");
 if (p.yanghui (Convert.ToInt16 (Console.ReadLine ())))
 Console.WriteLine ("The input value must be greater than 3");
 Console.Readkey ();
 }

 }

C Yang Hui triangle C

The following code is written in standard C language, and can be compiled by various C compilers including MSVC (including VC6) and GCC.

This algorithm uses only the row and column positions and the value on the left:

  / * yh-rt1.c-time and space optimization algorithm * /
 #include <stdio.h>
 #include <stdlib.h>
 int main ()
 {
 int s = 1, h; // value and height int i, j; // loop count scanf ("% d", & h); // number of input layers printf ("1 \ n"); // output first Each 1
 for (i = 2; i <= h; s = 1, i ++) // number of rows i from 2 to the height {
 printf ("1"); // first 1
 for (j = 1; j <= i-2; j ++) // Column position j bypasses the first and starts the loop directly // printf ("% d", (s = (i-j) / j * s) );
 printf ("% d", (s = (i-j) * s / j));
 printf ("1 \ n"); // last one, newline}
 getchar (); // pause and wait for return 0;
 }

Pyramid and diamond output are not enabled by default Right-angle triangles are evaluated by default. You can adjust isosceles triangles and rhombus outputs by using annotated switches or by using the compiler's -D definition switch. If you find it complicated, you can read the code that is not enabled because it does not meet the ifdef conditions according to the use of define.

This algorithm creates a two-dimensional array and finds the current row based on the value of the previous row. When printing again in reverse, the program uses the previously calculated values, saving time for repeated iterations.

  / * yh-2d.c-2D array iteration * /
 #include <stdio.h>
 #define M 10 // Number of rows // #define PYRAMID // Pyramid, will be filled with extra spaces // #define REVERSE // Reverse again and get diamond int main (void)
 {
 int a [M] [M], i, j; // two-dimensional array and loop variable, a [row] [column]
 for (i = 0; i <M; i ++) // each line {
 #ifdef PYRAMID
 for (j = 0; j <= Mi; j ++) printf ("");
 #endif // end of filling for (j = 0; j <= i; j ++) // assignment print printf ("% 4d", (a [i] [j] = (i == j || j == 0 )? 1: // Set 1 at the end
 a [i-1] [j] + a [i-1] [j-1])); // use previous line to calculate printf ("\ n");
 }
 #ifdef REVERSE
 for (i = M-2; i> = 0; i--)
 {
 #ifdef PYRAMID
 for (j = 0; j <= M-i; j ++) printf ("");
 #endif // end of filling for (j = 0; j <= i; j ++) printf ("% 4d", a [i] [j]); // directly use the previously obtained value printf ("\ n" );
 }
 #endif // End of diamond getchar (); // Pause waiting}

This one is written using a large array, and the style is closer to the VC6 code on the textbook.

  / * yh-rt3.c-more violent array * /
 #include <stdio.h>
 #include "string.h"
 int main ()
 {
 int a [10000]; // Container, we know from n * (n + 1) / 2 <= 10000, n <= 141
 int b, CR, i; // b is the current number of lines, CR is the number of lines to be displayed, i is the number of loops printf ("Please enter the number of lines to display (3 ~ 141):");
 scanf ("% d", & CR);
 YHSJ (CR);
 a [1] = a [2] = 1; // The first two lines are small and all are 1, so printf ("% d \ n", a [1]);
 printf ("% d% d \ n", a [1], a [2]);
 for (b = 3; b <= CR; b ++) // Judging from the third line {
 for (i = b; i> = 2; i--) // add a [i] = a [i] + a [i-1]; Array of values defaults to 0
 for (i = 1; i <= b; i ++) // Display loop printf ("% d", a [i]);
 printf ("\ n"); // newline}
 return 0;
 }

This version uses queued output.

  #include <stdio.h>
 #include <stdlib.h>
 #define EMPTY 1
 #define OFLOW 2
 #define INVAL 3
 #define MAX_Q 100
 typedef int DataType; // data type selection typedef struct {DataType elem [MAX_Q]; int front, rear;} LinkQ;
 // queue and check macro #define InitQ (Q) LinkQ Q; Q.front = Q.rear = -1;
 #define _EQ (Q, e) Q.elem [(Q.rear = (Q.rear + 1)% MAX_Q)] = e
 #define EnQ (Q, e) if ((Q.rear + 1)% MAX_Q == Q.front) Exit (OFLOW, "Overflow"); _EQ (Q, e)
 #define DeQ (Q, e) e = Q.elem [(Q.front = (Q.front + 1)% MAX_Q)]
 #define Front (Q) Q.elem [(Q.front + 1)% MAX_Q]
 // exit int Exit (int err, char msg []) {puts (msg); exit (err); return err;}
 int main (void) {
 int n = 1, i, j, k, t;
 InitQ (Q);
 printf ("please enter a number:");
 scanf ("% d", & n);
 if (n <= 0) {
 printf ("ERROR! \ n");
 exit (INVAL);
 }
 for (i = 0; i <n; i ++) printf ("");
 puts ("1"); EnQ (Q, 1); EnQ (Q, 1);
 for (i = 1; i <n; i ++) {
 for (k = 0; k <ni; k ++) printf ("");
 EnQ (Q, 1);
 for (j = 0; j <i; j ++) {
 DeQ (Q, t);
 printf ("% 3d", t);
 EnQ (Q, t + Front (Q));
 }
 EnQ (Q, 1);
 DeQ (Q, t);
 printf ("% d \ n", t);
 }
 return 0;
 }

Visual Basic Yang Hui triangle Visual Basic

  Private Sub Form_Click ()
 N = InputBox ("", "", 5)
 ReDim a (N + 1, N + 1), b (N + 1, N + 1)
 Cls
 k = 8
 For I = 1 To N
 Print String ((N-I) * k / 2 + 1, "");
 For J = 1 To I
 a (I, 1) = 1
 a (I, I) = 1
 a (I + 1, J + 1) = a (I, J) + a (I, J + 1)
 b (I, J) = Trim (Str (a (I, J)))
 Print b (I, J); String (k-Len (b (I, J)), "");
 Next J
 Print
 Next I
 End Sub

Click the window, enter the number of lines after the input box pops up, and press OK to print Yang Hui triangle on the form

SQL Yang Hui Triangle SQL

  -Use the combined calculation formula and factorial to calculate the Yang Hui triangle, which easily overflows for large numbers.
 create function Factorial (@count int) returns int as begin
 declare @ret int, @index int
 set @ret = 1-initial value is 1
 set @index = 1
 while (@index <= @count) begin
 set @ret = @ret * @index
 set @index = @index + 1
 end
 return (@ret)
 end
 create function Combination (@num int, @ count int) returns int as begin
 declare @up int, @ L1 int, @ R1 int, @ ret int
 set @up = dbo.Factorial (@count)
 set @ L1 = dbo.Factorial (@num)
 set @ R1 = dbo.Factorial (@count-@num)
 set @ret = @up / (@ L1 * @ R1)
 return (@ret)
 end
 create function PrintRow (@num int) returns nvarchar (100) as begin
 declare @i int
 declare @str nvarchar (100)
 set @str = ''
 set @i = 1
 while (@i <@num) begin
 set @str = @str + replace (str (dbo.Combination (@ i, @ num)), '', '') + ','
 set @i = @i + 1
 end
 return (@str)
 end
 create proc PasTrigLines (@num int) as begin-main program declare @i int
 set @i = 1
 while (@i <= @num) begin
 if (@i = 0) print 1 + ','
 else if (@i = 1) print '1,1,'
 else print '1,' + dbo.PrintRow (@i) + '1,'
 set @i = @i + 1
 end
 end
 exec PasTrigLines 10-ten

Yang Hui triangle language

From the example that comes with easy language.

The following is the full text.

  .Version 2
 .Assembly startup window assembly. Assembly variable Pascal triangle order, integer,,, Pascal triangle line number. Assembly variable Pascal triangle, text type,,, Pascal triangle formed. Subroutine __start window_create Finished 'Using algorithm: Recursive call' Problem: Find Pascal (Yang Hui) triangle 'Problem description: Take Pascal (Yang Hui) triangle of order N and display' Problem analysis:
 'Use the recursive method to take N layers of Pascal triangles and display them.  The numbers on the triangle boundary are all 1, and each number inside is the sum of the two numbers above it.
 'Suppose f (row, col) represents the col element of the row row of the Yang Hui triangle, then: f (row, col) = 1 (col = 1 or row = col), which is the stopping condition of recursion.  f (row, col) = f (row-1, col-1) + f (row-1, col), which is the sum of two adjacent elements in the previous row.  Call the solution recursively.
 'Remarks:
 .Subroutine_Calculate Graphic Button_ Clicked. Number of local variable rows, integer,,, Pascal triangle rows. Number of local variable columns, integer,,, Pascal triangle columns. Local variable query returns, integer, ,, The result of the message box edit box 2. content = ""
 Pascal triangle = ""
 'Judgment of the entered value. Judgment start (Edit box 1. Content = "")
 Message box ("Input error!", 0,)
 'When the value is too large, give a prompt. Judgment (to the value (edit box 1. Contents)> 20)
 Inquiry return = information box ("The value you entered is too large. The program will not respond for a while while processing the data. Do you want to continue?", #YESbutton + #Ask icon, "Ask:")
 .If true (request returns = #YESbutton)
 'If OK, call Pascal's triangle. Pascal's triangle ()
 .If true end ', the Pascal triangle is called when the data is small. Judgment (Edit box 1. Content  "" and to the value (Edit box 1. Content)  20)
 Pascal Triangle ()
 Default. Judgment is over. Subroutine finds Pascal triangle. Number of local variable rows, integer,,, Pascal triangle rows. Number of local variable columns, integer,,, Pascal triangle columns. The total number of Pascal triangle rows required. Pascal Triangle order = to the value (edit box 1. content)-1
 Variable loop first (0, Pascal's triangle order, 1, number of rows)
 Variable loop head (0, number of rows, 1, number of columns)
 'Take the Pascal triangle element to the current line Pascal triangle = Pascal triangle + to the text (Take Pascal triangle elements (number of rows + 1, number of columns + 1)) + ","
 Variable loop tail ()
 Pascal Triangle = Take the left side of the text (Pascal Triangle, take the length of the text (Pascal Triangle)-1) + #Newline character 'No need to go to the end to add a line break. Variable loop tail ()
 'Display result edit box 2. Content = Pascal triangle. Subroutine takes Pascal triangle elements, integer type,, Subroutine for taking elements in Pascal triangle. Number of parameter rows, integer type,, Number of Pascal triangle rows. Number of parameter columns, integer Type,, Pascal triangle number of columns. If (number of columns = 1 or number of rows = number of columns)
 'The outer two elements of each line are 1
 Back (1)
 Otherwise, the rest is the sum of the (number of rows-1) and (number of rows) elements of the previous row returned (take Pascal triangle elements (number of rows-1, number of columns-1) + take Pascal triangle elements (number of rows- 1, number of columns))
 If it ends

Java Yang Hui triangle Java

  public class TriangleArray
 {
 public static void main (String [] args)
 {
 final int NMAX = 10;

 // allocate triangular array
 int [] [] odds = new int [NMAX + 1] [];
 for (int n = 0; n <= NMAX; n ++)
 odds [n] = new int [n + 1];

 // fill triangular array
 for (int n = 0; n <odds.length; n ++)
 for (int k = 0; k <odds [n] .length; k ++)
 {
 / *
 * compute binomial coefficient n * (n-1) * (n-2) * ... * (n-k + 1) / (1 * 2 * 3 * ... * k)
 * /
 int lotteryOdds = 1;
 for (int i = 1; i <= k; i ++)
 lotteryOdds = lotteryOdds * (n-i + 1) / i;

 odds [n] [k] = lotteryOdds;
 }

 // print triangular array
 for (int [] row: odds)
 {
 for (int odd: row)
 System.out.printf ("% 4d", odd);
 System.out.println ();
 }
 }
 }

PHP Yang Hui Triangle PHP

  <? php
 / * The default output is ten lines. The number of output lines can be changed by using T (value). * /
 class T {
 private $ num;
 public function __construct ($ var = 10) {
 if ($ var <3) die ("The value is too small!");
 $ this-> num = $ var;
 }
 public function display () {
 $ n = $ this-> num;
 $ arr = array ();
 // $ arr = array_fill (0, $ n + 1, array_fill (0, $ n + 1,0));
 $ arr [1] = array_fill (0,3,0);
 $ arr [1] [1] = 1;
 echo str_pad ("& nbsp;", $ n * 12, "& nbsp;");
 printf ("% 3d", $ arr [1] [1]);
 echo "<br/>";
 for ($ i = 2; $ i <= $ n; $ i ++) {
 $ arr [$ i] = array_fill (0, ($ i + 2), 0);
 for ($ j = 1; $ j <= $ i; $ j ++) {
 if ($ j == 1)
 echo str_pad ("& nbsp;", ($ n + 1- $ i) * 12, "& nbsp;");
 printf ("% 3d", $ arr [$ i] [$ j] = $ arr [$ i-1] [$ j-1] + $ arr [$ i-1] [$ j]);
 echo "& nbsp; & nbsp;";
 }
 echo "<br/>";
 }
 }
 }
 $ yh = new T (); // $ yh = new T (quantity);
 $ yh-> display ();
 ?>

The only way to output an array is as follows:

  <? php
 $ max = 10;
 $ L = [1];
 var_dump ($ L);
 $ L = [1,1];
 var_dump ($ L);
 $ n = 2;
 while ($ n <= $ max-1) {
 $ oldL = $ L;
 $ L [$ n] = 1;
 $ n ++;
 for ($ i = 1; $ i <count ($ oldL); $ i ++) {
 $ L [$ i] = $ oldL [$ i-1] + $ oldL [$ i];
 }
 var_dump ($ L);
 }
 ?>

Python Yang Hui triangle Python

It is more convenient to implement with less code as follows:

  #-*-coding: utf-8-*-
 #! / usr / bin / env python
 def triangles ():
 L = [1]
 while True:
 yield L
 L = [sum (i) for i in zip ([0] + L, L + [0])]

This method uses list generation, which is difficult to understand. Here is another method:

  def triangles ():
 ret = [1]
 while True:
 yield ret
 for i in range (1, len (ret)):
 ret [i] = pre [i] + pre [i-1]
 ret.append (1)
 pre = ret [:]

Another version without generator:

  def YangHui (num = 10):
 LL = [[1]]
 for i in range (1, num):
 LL.append ([(0 if j == 0 else LL [i-1] [j-1]) + (0 if j == len (LL [i-1]) else LL [i-1] [j ]) for j in range (i + 1)])
 return LL