細谷の三角形をJavaで作成する

Question

私は細谷の三角形をJavaで作成しようとしていますが、数学の問題が出ています。私は、レベルのユーザー入力＃を持つ空の2D配列を作ることから始めました。

int[][] tri = new int[levels][]; 
    //build the empty triangle 
    for (int row =0;row< tri.length;row++){ 
     tri[row] = new int[row+1]; 
    } 

この部分は機能しています。私が抱えている問題は次の部分です。フィボナッチ数で三角形を塗りつぶしています（この配列を別の方法で作成することは助けになると思いますので、以前のコードを追加します）。私は最初の数をループの外に作り、1に設定してから、実際には第3行であるtri[2][0]でループを開始します。私は各番号を計算する方法のwikiページで方程式を見てきましたが、tri[0][1]のようなものにアクセスしようとするとインデックスを範囲外にしています。

for (int x=2;x<15;x++){ //TODO replace 15 with variable value 
     for (int y=0;y<15;y++){ 
      tri[x][y] = tri[x-1][y] + tri[x-2][y]; 
     } 

15は任意の数であるため、三角形内のすべての数字に対してループします。私は5つのレベルでテストしていますので、15つのレベルがあります。私は後でそれを修正するつもりだった。

私はたいてい、その数学と三角形の各数字間の関係を頭で囲むのに問題があります。基本的には同じhereという別の質問がありますが、回答は私にとっては意味がありませんでした.3年後に触れられていないので、私はここにいます。

昨年の回答では決して答えなかった別の質問hereがあります。正しい考えがあるかもしれないと思っています。まず、三角形の左右の辺を別の数式で作成し、別のループで、3つのすべてを作ります。私は本当に確信しています、そして、私は本当にどこに行くべきかの手がかりを持っていません。サイドノート：割り当ては、私はの三角形を再帰的に持っていなければならないと言っていますが、再帰的な方法で構築するのが最良の方法です。

再帰と三角自体の全体の考え方は私にとっては紛らわしいので、答えを本当に徹底的に説明すると本当に感謝します。私はこのクラスに追いつくのに苦労しています。 ありがとう！

Answer 1

まず、細谷の三角形のWikiページで提供されているフォーマットで数式を見るのは難しいです。

   1 
      1  1 
     2  1  2 
    3  2  2  3 
5  3  4  3  5 

---

と彼らはこのように見えるように再アレンジ：のは、最初の5行を見てみましょう

1 
1  1 
2  1  2 
3  2  2  3 
5  3  4  3  5 

---

、あなたはおそらく今のパターンを見ることができる：

starting from the 3rd row: 
    for every number in the row 
     if the number has a number above it (i.e. all except the last number in each row) 
      it's the sum of the two numbers straight above it: H(n,j) = H(n-1,j) + H(n-2,j) 
     otherwise (i.e. the last number in each row) 
      it's the sum of the two numbers above it in the left diagonal: H(n,j) = H(n-1,j-1) + H(n-2),j-2) 

を

---

再フォーマットされた数字は、図のように2D配列に格納できます。そして、私たちが行う必要があるのは、デモはWikiページに表示されるように見えるように、適切なスペースでそれをプリントアウトすることです：

public class HosoyaTriangle { 
    public static void main(String args[]) { 
     final int N = 10; 
     int[][] triangle = new int[N][N]; // this would initialize all cell elements to be 0 

     //populate the base cases for the first two rows 
     //H(0,0) = H(1,0) = H(1,1) = 1 
     triangle[0][0] = triangle[1][0] = triangle[1][1] = 1; 

     //starting from the 3rd row 
     for (int row = 2; row < N; row++) { 
      for (int col = 0; col < N; col++) { 
       if (col < row) { 
        //H(n,j) = H(n-1,j) + H(n-2,j) 
        triangle[row][col] = triangle[row - 1][col] + triangle[row - 2][col]; 
       } else { 
        //H(n,j) = H(n-1,j-1) + H(n-2),j-2) 
        triangle[row][col] = triangle[row - 1][col - 1] + triangle[row - 2][col - 2]; 
       } 
      } 
     } 
     print(triangle); 
    } 

    private static void print(int[][] matrix) { 
     final int level = matrix.length; 
     int spaceCount; 
     StringBuilder sb; 
     for (int row = 0; row < level; row++) { 
      sb = new StringBuilder(); 

      //figure out how many spaces need to be printed before  
      //printing out the first non-zero number in the row 
      spaceCount = level - row - 1; 

      //add the spaces 
      while(spaceCount-- > 0) { 
       sb.append(" "); 
      } 
      //add all the non-zero numbers in the row 
      for (int col = 0; col < level; col++) { 
       if (matrix[row][col] > 0) { 
        sb.append(String.format("%4d",matrix[row][col])); 
       } 
      } 
      System.out.println(sb.toString()); 
     } 
    } 
} 

---

出力：

     1 
        1 1 
       2 1 2 
       3 2 2 3 
      5 3 4 3 5 
      8 5 6 6 5 8 
     13 8 10 9 10 8 13 
     21 13 16 15 15 16 13 21 
    34 21 26 24 25 24 26 21 34 
    55 34 42 39 40 40 39 42 34 55 

EDIT：

あなたは再帰的な解決策を探していることを認識しました。各番号は、上記列の数によって計算される考えると、我々はフィボナッチ数列の同じロジックを使用し、N行目から開始し、再帰的に、我々は、ベースケースをヒットutilの上方に伝播することができる：

public static void main(String args[]) { 
    final int N = 10; 
    int[][] triangle = new int[N][N]; // this would initialize all cell elements to be 0 

    //only need to loop through the last row 
    //each column is calculated as a separate fibonacci sequence 
    for (int col = N - 1; col >= 0; col--) { 
     calc(N - 1, col, triangle); 
    } 
    print(triangle); 
} 

private static int calc(int row, int col, int[][] triangle) { 
    //base cases 
    if (row == 0 && col == 0 || row == 1 && col == 0 || row == 1 && col == 1 || row == 2 && col == 1) { 
     triangle[row][col] = 1; 

    } else { 
     if (col < row) { 
      //H(n,j) = H(n-1,j) + H(n-2,j) 
      triangle[row][col] = calc(row - 1, col, triangle) + calc(row - 2, col, triangle); 
     } else if (col == row) { 
      //H(n,j) = H(n-1,j-1) + H(n-2),j-2) 
      triangle[row][col] = calc(row - 1, col - 1, triangle) + calc(row - 2, col - 2, triangle); 
     } 
    } 
    return triangle[row][col]; 
} 

注この溶液こと非再帰的なものよりもずっと遅い。