在java中創建一個Hosoya的三角形

Question

所以我試圖在Java中創建一個Hosoya的三角形，並且我遇到了一些數學問題。我已經開始製作一個空的2D陣列，它有用戶輸入級別：

int[][] tri = new int[levels][]; 
    //build the empty triangle 
    for (int row =0;row< tri.length;row++){ 
     tri[row] = new int[row+1]; 
    } 

這部分是功能性的。我遇到的問題是在下一部分，我嘗試用斐波那契數字填充三角形（我添加了前面的代碼塊，因爲我想可能以不同的方式構建這個數組會有所幫助）。我試着在循環之外做出前幾個數字，並將它們設置爲1，然後開始實際循環在tri[2][0]，這是第三行。我已經在維基頁面上看到了如何計算每個數字的方程式，但是當它嘗試訪問像tri[0][1]之類的東西時，我一直在拋出索引超出邊界的錯誤。

for (int x=2;x<15;x++){ //TODO replace 15 with variable value 
     for (int y=0;y<15;y++){ 
      tri[x][y] = tri[x-1][y] + tri[x-2][y]; 
     } 

15只是一個任意數字，所以它會循環每個數字在三角形。我一直在測試5個級別，所以15個作品。我打算稍後解決這個問題。

我大部分時間只是在圍繞它的數學和三角形中的每個數字之間的關係方面遇到麻煩。還有另一個問題基本上是相同的here但是給出的答案對我來說並沒有什麼意義，並且在3年之內它沒有被觸及，所以我在這裏。

還有另外一個問題here從去年開始沒有答案，我在想也許他們有正確的想法：也許我應該先用不同的數學建立三角形的左右兩邊，然後填寫中間與一個單獨的循環，總共3。但我確實很不確定，而且我真的不知道下一步該去哪裏。附註：作業說我只需要打印三角形遞歸，但如果用遞歸方法構建它將是我願意聽到任何想法的最佳方式。

遞歸的整體思想和三角形本身讓我感到困惑，所以如果你真正徹底地解釋了答案，我會非常感激，我在這個課堂上奮力追趕。 謝謝！

Answer 1

首先，很難看到Hosoya三角形Wiki頁面提供的格式。我們採取的第一個5行：

   1 
      1  1 
     2  1  2 
    3  2  2  3 
5  3  4  3  5 

---

，並重新安排他們看起來像這樣：

1 
1  1 
2  1  2 
3  2  2  3 
5  3  4  3  5 

---

，你也許可以看到現在的格局：

starting from the 3rd row: 
    for every number in the row 
     if the number has a number above it (i.e. all except the last number in each row) 
      it's the sum of the two numbers straight above it: H(n,j) = H(n-1,j) + H(n-2,j) 
     otherwise (i.e. the last number in each row) 
      it's the sum of the two numbers above it in the left diagonal: H(n,j) = H(n-1,j-1) + H(n-2),j-2) 

---

重新格式化的數字可以存儲在二維數組中，如圖所示。那麼我們需要做的就是這樣它看起來像演示的Wiki頁面上顯示有適當的空間將其打印出來：

public class HosoyaTriangle { 
    public static void main(String args[]) { 
     final int N = 10; 
     int[][] triangle = new int[N][N]; // this would initialize all cell elements to be 0 

     //populate the base cases for the first two rows 
     //H(0,0) = H(1,0) = H(1,1) = 1 
     triangle[0][0] = triangle[1][0] = triangle[1][1] = 1; 

     //starting from the 3rd row 
     for (int row = 2; row < N; row++) { 
      for (int col = 0; col < N; col++) { 
       if (col < row) { 
        //H(n,j) = H(n-1,j) + H(n-2,j) 
        triangle[row][col] = triangle[row - 1][col] + triangle[row - 2][col]; 
       } else { 
        //H(n,j) = H(n-1,j-1) + H(n-2),j-2) 
        triangle[row][col] = triangle[row - 1][col - 1] + triangle[row - 2][col - 2]; 
       } 
      } 
     } 
     print(triangle); 
    } 

    private static void print(int[][] matrix) { 
     final int level = matrix.length; 
     int spaceCount; 
     StringBuilder sb; 
     for (int row = 0; row < level; row++) { 
      sb = new StringBuilder(); 

      //figure out how many spaces need to be printed before  
      //printing out the first non-zero number in the row 
      spaceCount = level - row - 1; 

      //add the spaces 
      while(spaceCount-- > 0) { 
       sb.append(" "); 
      } 
      //add all the non-zero numbers in the row 
      for (int col = 0; col < level; col++) { 
       if (matrix[row][col] > 0) { 
        sb.append(String.format("%4d",matrix[row][col])); 
       } 
      } 
      System.out.println(sb.toString()); 
     } 
    } 
} 

---

輸出：

     1 
        1 1 
       2 1 2 
       3 2 2 3 
      5 3 4 3 5 
      8 5 6 6 5 8 
     13 8 10 9 10 8 13 
     21 13 16 15 15 16 13 21 
    34 21 26 24 25 24 26 21 34 
    55 34 42 39 40 40 39 42 34 55 

編輯：

意識到您正在尋找遞歸解決方案。給定每個數字是由數字中的行計算上述情況，我們可以採用斐波納契序列的相同的​​邏輯和從第N行開始，並遞歸地向上傳播的util我們打基例：

public static void main(String args[]) { 
    final int N = 10; 
    int[][] triangle = new int[N][N]; // this would initialize all cell elements to be 0 

    //only need to loop through the last row 
    //each column is calculated as a separate fibonacci sequence 
    for (int col = N - 1; col >= 0; col--) { 
     calc(N - 1, col, triangle); 
    } 
    print(triangle); 
} 

private static int calc(int row, int col, int[][] triangle) { 
    //base cases 
    if (row == 0 && col == 0 || row == 1 && col == 0 || row == 1 && col == 1 || row == 2 && col == 1) { 
     triangle[row][col] = 1; 

    } else { 
     if (col < row) { 
      //H(n,j) = H(n-1,j) + H(n-2,j) 
      triangle[row][col] = calc(row - 1, col, triangle) + calc(row - 2, col, triangle); 
     } else if (col == row) { 
      //H(n,j) = H(n-1,j-1) + H(n-2),j-2) 
      triangle[row][col] = calc(row - 1, col - 1, triangle) + calc(row - 2, col - 2, triangle); 
     } 
    } 
    return triangle[row][col]; 
} 

注意，此溶液比非遞歸的要慢得多。