Javaでパスカルの三角形を生成する方法

11/14/2018

パスカルの三角形では、各行の値は、前の行の値の合計です。 使用可能な値がない場合は、値が使用されます。 n [k] = n-1 [k-1] + n-1 [k]のJava表記法を用いる。 最初の行には値1が含まれます。

パスカルの三角形は、2 forループを使用して最初の要素で先頭から始まります。

次のJavaファイルを作成します。

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class InterviewPascalTriangle {

    protected List<List<Integer>> generatePascalTriangle(int nbRows){
	// 入力検証
	if ( nbRows < 0 )
	    throw new IllegalArgumentException( "行数は負数にすることはできません。" );
	
	// 返すオブジェクト
	List<List<Integer>> toReturn = new LinkedList<List<Integer>>();

	// 前の行を保存します。
	List<Integer> previousRow = Collections.emptyList();

	// すべての行を処理する
	for( int i = 0 ; i <= nbRows ; i++ ){
	    // 現在の行を作成する
	    List<Integer> currentRow = new LinkedList<Integer>();
	    toReturn.add( currentRow );

	    // 以前の値を定義する
	    int previousValue = 0;
	    // すべての値をループする
	    for(int c : previousRow){
		currentRow.add( c + previousValue );
		
		// 現在の値を前の値に設定する
		previousValue = c;
	    }


	    // 最後の値を追加する
	    currentRow.add( 1 );
	    
	    // 現在の行を保存します。
	    previousRow = currentRow;
	}
	
	return toReturn;
    }
    
   public static void main(String[] argv) throws Exception {
	InterviewPascalTriangle t = new InterviewPascalTriangle();

	
	List<List<Integer>> res = t.generatePascalTriangle(7);
	
	System.out.println( "結果：" );
	String tmp = res.get( res.size() -1 ).toString();
	
	int max = (int) tmp.length();
	
	for(List<Integer> c : res ){
	    String toDisplay = c.toString();
	    int padding = ( max - toDisplay.length()) / 2 ;
	    StringBuilder sb = new StringBuilder();
	    for(int i=0; i < padding; i++){
		sb.append( " " );
	    }
	    
	    sb.append( toDisplay );
	    
	    System.out.println( sb.toString() );
	}

    }



}

出力は次のようになります。

結果：
            [1]
           [1, 1]
         [1, 2, 1]
        [1, 3, 3, 1]
      [1, 4, 6, 4, 1]
    [1, 5, 10, 10, 5, 1]
  [1, 6, 15, 20, 15, 6, 1]
[1, 7, 21, 35, 35, 21, 7, 1]

パスカルの三角形の行には、0からnの番号が付けられます。 最初の行には値1のみが含まれます。

参考文献：

Pascal's triangle

最近のコメント