时间戳

首页 > 解决方案 > 使用递归打印帕斯卡三角形

java - 使用递归打印帕斯卡三角形

问题描述

我正在尝试开发一个使用递归打印出帕斯卡三角形的程序。这是我的代码：

public class PascalTriangle {
    public static int[] computePT(int k) {
        int[] pt = new int[k + 1];
        if (k == 0) {
            pt[0] = 1;
            return pt;
        } else {
            int[] ppt = computePT(k - 1);
            pt[0] = pt[k] = 1;
            for (int i = 1; i < ppt.length; i++) {
                pt[i] = ppt[i - 1] + ppt[i];
            }
        }
        return pt;
    }
}

public class PascalTriangleDriver {
    public static void main(String args[]) {
        int k = 10;

        int arr[] = PascalTriangle.computePT(k);

        for (int i = 0; i < arr.length; i++)
            System.out.print(arr[i] + " ");

        System.out.println();
    }
}

代码运行完美，但是我的问题是我想修改我的PascalTriangle代码（而不是PascalTriangleDriver代码），例如，当k=10它打印出来时：

1 9 36 84 126 126 84 36 9 1

代替：

1 10 45 120 210 252 210 120 45 10 1

标签： javaarraysrecursionpascals-triangle

解决方案

您似乎犯了一个偏离 1 的错误。解决此问题的一种简单方法是编写另一种方法，使用以下方法调用您的原始方法k-1：

// this is your original method, just renamed:
private static int[] computePTImpl(int k) {
    int[] pt = new int[k + 1];
    if (k == 0) {
        pt[0] = 1;
        return pt;
    } else {
        int[] ppt = computePT(k - 1);
        pt[0] = pt[k] = 1;
        for (int i = 1; i < ppt.length; i++) {
            pt[i] = ppt[i - 1] + ppt[i];
        }
    }
    return pt;
}

// you will call this method:
public static int[] computePT(int k) {
    return computePT(k - 1);
}

或者，您实际上可以通过将ks替换为 s 来修复您的代码k-1：

public static int[] computePT(int k) {
    int[] pt = new int[k]; // note the change
    if (k == 1) { // note the change
        pt[0] = 1;
        return pt;
    } else {
        int[] ppt = computePT(k - 1);
        pt[0] = pt[k - 1] = 1; // note the change
        for (int i = 1; i < ppt.length; i++) {
            pt[i] = ppt[i - 1] + ppt[i];
        }
    }
    return pt;
}

请注意，我们不会更改递归调用，因为如果我们这样做了，我们会说k帕斯卡三角形的第 - 行取决于k-2第 - 行，这是不正确的。

推荐阅读