生成帕斯卡三角形的最佳方法（提到了两种方法）

Question

我有一个Java编程作业。

我通过制作nCr（http://en.wikipedia.org/wiki/Combination）函数来实现它，然后使用双重循环通过打印输出来创建三角形。

但是，该作业要求创建一个不均匀的二维数组，然后通过添加前一行中的两个数字来填充该数组，然后将其打印出来。

我知道我必须按照作业要求完成任务，但我有一点小感觉（至少对于小三角形而言），我所实现的方法更好。

哪种方法更好？

- Portablejim

Answer 1

我认为应该使用作业要求的方法更好。你的方法需要多次乘法来计算三角形的每个元素。这个数字将随着你需要计算的每一行三角形而增加。

然而，作业的方法只需要对三角形的每个元素进行一次加法运算。

- Andrew Cooper

Answer 2

如果我理解你的问题，你正在尝试比较生成帕斯卡三角形的两种方法：

1. 运行一个nCr函数来填充三角形中的每个单元格。
2. 通过简单的加法填充每个单元格，在一次遍历中生成三角形。

第二种方法似乎更好。我有什么遗漏吗？即使在nCr函数中使用记忆化，这些调用也会产生开销。

- Ray Toal

---

使用组合数nCr时，我根本不会生成数组。 - Portablejim

啊，我现在明白了。我一定是看错了。但是，我认为对于每个单元格来说，两次查找和一次加法几乎总是胜利的。你的任务可能要求你将整个三角形保存在内存中，但实际上你只需要保存最后两行。随着n和k的值越来越大，nCr函数的常数会增长。这种情况在增量方法中不会发生。 - Ray Toal

Answer 3

使用递归：

/*使用递归*/
class RecursivePascal {
    public static void main(String args[]) {
        int n = 100;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                //System.out.print(i+","+j+" ");
                System.out.print(pascal(i, j) + " ");
            }
            System.out.println();
        }
    }

    static int pascal(int i, int j) {
        if (j == 0)
            return 1;
        else if (j == i)
            return 1;
        else {
            return pascal(i - 1, j - 1) + pascal(i - 1, j);
        }
    }
}

使用简单逻辑：

/*使用逻辑*/
class p {
    public static void main(String args[]) {
        int one[] = {1};
        int n = 13;
        System.out.println("1");
        for (int j = 0; j < n; j++) {
            int two[] = new int[one.length + 1];
            int twoCounter = 0;
            for (int i = 0; i < one.length; i++) {
                if (i == 0) {
                    two[twoCounter++] = one[i];
                    System.out.print(one[i] + " ");
                }
                if (i != 0) {
                    two[twoCounter++] = one[i] + one[i - 1];
                    System.out.print((one[i] + one[i - 1]) + " ");
                }
                if (i == one.length - 1) {
                    two[twoCounter++] = one[i];
                    System.out.print(one[i] + " ");
                }
            }
            System.out.println();
            one = two;
        }
    }
}

- Esann