Вопрос по треугольнику Pascal с использованием рекурсии - PullRequest
Новая
       26

Вопрос по треугольнику Pascal с использованием рекурсии

0 голосов
/ 30 апреля 2020

Я пытаюсь разработать программу, которая распечатывает Треугольник Pascal, используя Рекурсию. Вот мои коды: 

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

1 Ответ

2 голосов
/ 30 апреля 2020

Вы, кажется, сделали ошибку off-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 s на 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-я строка треугольника Pascal зависит от (k-2) - й ряд, что не соответствует действительности.

...