我想开发一个使用递归法打印出帕斯卡三角的程序。这是我的代码。
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
你似乎犯了一个偏离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);
}
或者,您可以通过替换掉以下内容来修正您的代码 k
与 k-1
s:
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)行,这是不对的。