关于使用递归的帕斯卡三角形的问题

问题描述 投票:0回答:1

我想开发一个使用递归法打印出帕斯卡三角的程序。这是我的代码。

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 84 36 9 1。

1 9 36 84 126 126 84 36 9 1

而不是。

1 10 45 120 210 252 210 120 45 10 1

java arrays recursion pascals-triangle
1个回答
2
投票

你似乎犯了一个偏离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);
}

或者,您可以通过替换掉以下内容来修正您的代码 kk-1s:

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)行,这是不对的。

© www.soinside.com 2019 - 2024. All rights reserved.