「楊輝三角」という問題は1261年前の北宋時代に楊輝という数学者が発見しました。

1: 1
2: 1 1
3: 1 2 1
4: 1 3 3 1
5: 1 4 6 4 1
6:1 5 10 10 5 1

下の数=上の隣接の二つの数の和。

実際の規則は(X+Y)のN乗の係数です。

例えば、(X+Y)の0乗は1       ->      1

     (X+Y)の1乗はX+Y      ->  1 1

     (X+Y)の2乗はXX+2XY+YY      ->  1 2 1

     (X+Y)の3乗はXXX+3XXY+3XYY+YYY  ->  1 3 3 1

「楊輝三角」を出力する問題は中国のC言語試験によく見えます。

カテゴリー: ニュース

9件のコメント

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:42

適当に書いてみた。

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

結果

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
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1

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 17:54

いぢめか……orz 切れてるとこだけ。

    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:39

これはどうですか?

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();
    }
  }
}

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
以下略

zuoy · 2007-07-19 22:05

改良しました。もっと短くなります。

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

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

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();
		}
	}
}

コメントを残す

メールアドレスが公開されることはありません。