Using java to realize Yang Hui triangle example code

Before, a younger student asked me a Java interview question, which was not difficult. Using java to realize Yang Hui triangle. I spent some time sorting it out and found it very interesting, so I wanted to write it down and share it. Before writing code, let's clarify the following two problems.

What is Yang Hui triangle

Yang Hui triangle is a geometric arrangement of binomial coefficients in a triangle. It was mentioned in the detailed nine chapter algorithm written by mathematician Yang Hui of the Southern Song Dynasty in 1261. In Europe, it is called Pascal triangle, as shown in the figure.

Yang Hui triangle

The law of Yang Hui triangle is the principle

1. Each number is equal to the sum of the two numbers above it.

2. The numbers in each line are symmetrical left and right, and gradually increase from 1.

3. The number in line n has n items.

4. The sum of the numbers in line n is 2N-1.

5. The number of m in line n can be expressed as C (n-1, m-1), that is, the combined number of M-1 elements from n-1 different elements.

6. The m-th number in line n is equal to the N-M + 1 number, which is one of the properties of combinatorial numbers.

7. Each number is equal to the sum of the left and right numbers in the previous line. This property can be used to write the whole Yang Hui triangle. That is, the i-th number in line n + 1 is equal to the sum of the i-1st number and the i-th number in line n, which is also one of the properties of combinatorial numbers. That is, C (n + 1, I) = C (n, I) + C (n, i-1).

8. The coefficients in the expansion of (a + b) n correspond to each term in row (n + 1) of Yang Hui triangle in turn.

9. Connect the first number in line 2n + 1 with the third number in line 2n + 2 and the fifth number in line 2n + 3. The sum of these numbers is the fourth Fibonacci number; Add the 2nd number in line 2n (n > 1), the 4th number in line 2N-1 and the 6th number in line 2n-2... The sum of these numbers is the 4th Fibonacci number.

10. Arrange the numbers in each row, We can get the N-1 power of 11 (n is the number of rows): 1 = 11 ^ 0; 11 = 11 ^ 1; 121 = 11 ^ 2... When n > 5, this property will not be met. At this time, put the rightmost number "1" in row n in one bit, and then align the one bit of a number on the left to ten... And so on, and use "0" for the empty bit Make up, then add up all the numbers, and the number is exactly the N-1 power of 11. Taking n = 11 as an example, the number of the eleventh row is 1,10,45120210252,1, and the result is 25937424601 = 1110.

After knowing these two points, our thinking is very clear. There are many ways to implement it. Here I intend to use two-dimensional array and double for loop to implement it.

Demo code:

The results output on the console are as follows:

Only ten lines of Yang Hui triangle are output here. After optimization, you can get the number of rows dynamically. It can also become a positive triangle, just add a loop to calculate the space. Interested students can try Eighteen line program from Java

The above is the whole content of this article. I hope it will be helpful to your study, and I hope you can support programming tips.