java - 在 Java 中创建一个 Hosoya 三角形

Question

因此，我尝试在 Java 中创建一个 Hosoya 三角形，但我遇到了一些数学问题。我首先制作了一个空的二维数组，其中包含用户输入的级别数:

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] 开始实际循环，这是第 3 行。我已经在 wiki 页面上看到了如何计算每个数字的方程式，但是当它尝试访问类似 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 in全部。不过我真的不确定，而且我真的不知道下一步该去哪里。旁注:作业说我只需要递归地打印三角形，但如果用递归方法构建它是最好的方法，我愿意听取任何想法。

递归的整个概念和三角形本身让我有点困惑，所以如果你能真正彻底地解释答案，我将不胜感激，我在这门课上有点努力 catch 进度。谢谢!

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 行开始，递归向上传播直到我们达到基本情况:

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];
}

请注意，此解决方案比非递归解决方案慢得多。