面接の問題――楊輝三角

squld · 2007-07-19 12:11

パスカルが発見したんだと思っていたのですが、パスカルより前に研究してた人がいるんですね。

パスカルの三角形 – Wikipediaによると

最古の文献は、紀元前450年頃にインドの数学者ピンガラ(Pingala)によって書かれたとされている。
中国では13世紀に数学者の楊輝がこの三角形を研究しており、同国内ではこの三角形は「楊輝の三角形」と呼ばれている。
パスカルは1655年に発表した『Traité du triangle arithmétique』の中でこの三角形について言及している。

javaで解いてみました。

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

public class PascalsTriangle {
	public static void main(String[] args) {
		List tList = new ArrayList();
		for (int i = 1; i <= 101; i++) {
			calculateNext(tList);
			display(i, tList);
		}
	}

	private static void calculateNext(List aList) {
		BigInteger tLeftNumber = new BigInteger("1");
		for (int i = 1; i < aList.size(); i++) {
			tLeftNumber = aList.set(i, tLeftNumber.add(aList.get(i)));
		}
		aList.add(new BigInteger("1"));
	}

	private static void display(int tStep, List aList) {
		System.out.print(tStep);
		System.out.print(" : ");
		for (BigInteger tNumber : aList) {
			System.out.print(tNumber);
			System.out.print(' ');
		}
		System.out.println();
	}
}

結果

1 : 1
2 : 1 1
3 : 1 2 1
4 : 1 3 3 1
以下略

35段目でintegerの最大値(約21億)を超えてしまいました。

mori · 2007-07-19 17:52

おぉう…　結果がががが pre のなかに……　そして途中で切れてる！
でもソース見ると切れてないぞ……？　その上要らない＜/pre＞が入ってるぞ……？

もう一回投稿してみる。　駄目だったら諦めだぜ！

package seraph.pascalTriangle;

public class PascalTriangle {
    public static void main(String[] args){
	for(int i=0; i< 10; i++){
	    printLine(i);
	}
    }

    static void printLine(int i){
	for(int j=0;j<=i;j++){
	    System.out.print(combination(i,j));
	    System.out.print(" ");
	}

	System.out.println();
    }

    static long combination(int n, int i){
	if(i==0) return 1;

	int i2 = n-i;
	if(i2 < i){
	    i = i2;
	}

	long tResult = 1;
	for(int j=0;j
まぁ、このコードはオーバーフローが速く訪れるので微妙ですが。
				

									
			

mori · 2007-07-19 18:02

駄目だこりゃ。　”＜”記号直後に何かあると、ブラウザがタグとして認識しちゃうんだな。

見苦しいので、消せたら消しておいてください。

zuoy · 2007-07-19 19:47

ごめん、使い方がよくわかりません。「pre」を忘れました。

public class PascalsTriangle {
  public static void main(String[] args) {
    int tIndex = 5;
    int[][] tTrignle = new int[tIndex][tIndex];

    tTrignle[0][0] = 1;
    System.out.print(tTrignle[0][0]);
    System.out.println();

    for (int tI = 1; tI < tIndex; tI++) {
      for (int tJ = 0; tJ <= tI; tJ++) {
        if (tJ == 0) {
          tTrignle[tI][0] = 1;
          System.out.print(tTrignle[tI][0]);
          continue;
        }
        tTrignle[tI][tJ] = tTrignle[tI - 1][tJ - 1] + tTrignle[tI - 1][tJ];
        System.out.print(" " + tTrignle[tI][tJ]);
      }
      System.out.println();
    }
  }
}

結果

1
1 1
1 2 1
1 3 3 1
以下略

squld · 2007-07-19 23:35

さらに1行縮めた。Javaだとこれぐらいが限界か・・・。

public class PT {
	public static void main(String[] args) {
		int N = 10;
		int[] tVector = new int[N * 2];
		tVector[N] = 1;

		for (int j = 1; j <= N; j++) {
			for (int i = 1; i < N * 2 - 1; i++) {
				tVector[i] = tVector[i + 1] + (tVector[0] = tVector[i]);
				System.out.print(tVector[0] == 0 ? "" : tVector[0] + " ");
			}
			System.out.println();
		}
	}
}