A junior asked me a Java interview question before, but the questions were not difficult. Implement the Yang Hui triangle with Java. I took some time to sort it out and found it was quite interesting, so I wanted to write it down and share it. Before writing code, let’s first clarify the following two questions.
What is Yang Hui Triangle
Yang Hui's triangle is a geometric arrangement of binomial coefficients in a triangle. It was mentioned in the "Detailed Explanation of Nine Chapters Algorithm" written by Yang Hui, a mathematician of the Southern Song Dynasty in my country in 1261. In Europe, it is called the Pascal triangle, as shown in the figure.
Yang Hui Triangle
The law of Yang Hui's triangle is the principle
1. Each number is equal to the sum of the two numbers above it.
2. Each row of numbers is symmetrical left and right, and gradually becomes larger from 1.
3. The number in line n has n terms.
4. The sum of the n-th line numbers is 2n-1.
5. The number of m in the nth row can be expressed as C(n-1, m-1), that is, the number of combinations of m-1 elements taken from n-1 different elements.
6. The mth number in line n is equal to n-m+1 number, which is one of the properties of the combined number.
7. Each number is equal to the sum of the left and right numbers of the previous line. This property can be used to write the entire Yang Hui triangle. That is, the i-th number in line n+1 is equal to the sum of the i-1th number and the i-th number in line n, which is also one of the properties of the combined number. That is, C(n+1,i)=C(n,i)+C(n,i-1).
8. The coefficients in the expansion formula of (a+b)n correspond to each item in the (n+1) line of the Yang Hui triangle in turn.
9. Connect the first number in line 2n+1, with the third number in line 2n+2, the fifth number in line 2n+3, and the sum of these numbers is the 4n+1 Fibonacci number; transfer the second number in line 2n-1 (n>1), with the fourth number in line 2n-2, and the sixth number in line 2n-2... The sum of these numbers is the 4n-2 Fibonacci number.
10. Arrange the numbers in each row and you can get the n-1 of 11 (n is the number of rows) power: 1=11^0; 11=11^1; 121=11^2... When n>5, it will not meet this property. At this time, the rightmost number "1" on the nth line should be placed in the single digit, and then align the single digit of a number on the left to ten digits......, and so on, fill the empty space with "0", and then add all the numbers together, and the number obtained is exactly to the n-1 power of 11. Taking n=11 as an example, the number of the eleventh row is: 1,10,45,120,210,252,210,120,45,10,1, and the result is 25937424601=1110.
After understanding these two points, our thinking becomes very clear. There are many ways to implement it, here I plan to use a two-dimensional array plus a double for loop to implement it.
demo code:
public class Yanghui { public static void main(String[] args) { // Create a two-dimensional array int t[][]=new int[10][]; // traverse the first layer of the two-dimensional array for (int i = 0; i < t.length; i++) { // Initialize the size of the second layer array t[i]=new int[i+1]; // traverse the second layer array for(int j=0;j<=i;j++){ // Assign the array elements on both sides to 1 if(i==0||j==0||j==i){ t[i][j]=1; }else{ // Other values are calculated by formula t[i][j]=t[i-1][j]+t[i-1][j-1]; } // Output array element System.out.print(t[i][j]+"/t"); } // Line break System.out.println(); } }}The output results in the console are as follows:
Only ten rows of Yang Hui triangle are output here. Optimize it and can be changed to dynamically obtaining the number of rows. It can also be turned into a positive triangle, just add a loop to calculate the space. Interested students can try it. ―― From Java 18th-line programmer
The above is all the content of this article. I hope it will be helpful to everyone's learning and I hope everyone will support Wulin.com more.