Everyone knows that the use of array array is outputting Yang Hui triangle is a relatively easy task, and it can be found on many textbooks, and the calculation speed is faster, but there is a disadvantage that when the order is relatively large, it needs to occupy More storage space. Below I tried to output Yang Hui Triangle with a non-array method
1. Use formula
I learned high school mathematics, we know that there is formula (A B) n = c0n A0BN ... CKN AKBN-K ... CNN AnB0
Each element of Yang Hui Triangle can calculate CKN AKBN-K by formula. With this formula, we can quickly write the program.
/ ************************************************** **
* Use the formula to output Yang Hui triangle
* Programming: zheng 2004.10.27
* Program compiled in BCB6.0
*********************************************************** * /
#include "stdio.h"
Static Long Factorial (long n)
{// of the step
Return n == 0 || n == 1? 1: n * Factorial (N-1);
} // Factorial
Static Long getElem (long n, long k)
{// Use the formula to calculate the row line of Yang Hui triangles, elements of col columns
Return Factorial (n) / (Factorial (N-K) * Factorial (k));
} // getlem
Void Output (long n)
{// Output Yang Hui triangle, n is the step of Yang Hui triangle
Int row, col;
For (row = 0; row <= N; ROW )
{
For (COL = 0; col <= row; col )
Printf ("% 5LD", getlem (row, col));
Printf ("/ n");
} // for
} // Output
2. Use recursive
Observe the following Yang Hui triangle (you can also use the above nature, derived by mathematics)
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
We can get the nature of the following (in fact, the method we use the array is also useful)
1. The elements on the boundary are 1
2. Any element in the middle is the two adjacent elements of his previous line.
If we use f (n, k) to represent the kth element of the Nth line of the Yanghui triangle, the properties of the upper surface can be expressed
f (n, k) = 1 (k = 0 or n = k)
f (n, k) = f (n-1, k-1) f (n-1, k)
which is
CKN = 1 (k = 0 or n = k)
CKN = CK-1N-1 CKN-1
With the nature of the above, we can easily write the following procedures.
/ ************************************************** *** Use recursive output Yang Hui triangle
* Programming: zheng 2004.10.27
* Program compiled in BCB6.0
*********************************************************** * /
#include "stdio.h"
Static Long Factorial (long n)
{// of the step
Return n == 0 || n == 1? 1: n * Factorial (N-1);
} // Factorial
Static Long getElem (long n, long k)
{// uses recursive calculation of the elements of the row of Yang Hui triangles, columns
IF (k == 0 || n == k) Return 1;
Else Return getElem (N-1, K-1) getElem (N-1, K);
} // getlem
Void Output (long n)
{// Output Yang Hui triangle, n is the step of Yang Hui triangle
Int row, col;
For (row = 0; row <= N; ROW )
{
For (COL = 0; col <= row; col )
Printf ("% 5LD", getlem (row, col));
Printf ("/ n");
} // for
} // Output
