面接の問題――楊輝三角

「楊輝三角」という問題は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言語試験によく見えます。

Written by: zuoy on 2007 年 7 月 18 日

Last Modified on 2009 年 3 月 22 日

Trackback:

読者からの反応 (9 件)

squld より:

2007 年 7 月 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 年 7 月 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 年 7 月 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 年 7 月 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 年 7 月 19 日 18 時 02 分

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

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

zuoy より:

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

結果

zuoy より:

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

Blog (320)

面接の問題――楊輝三角

読者からの反応 (9 件)

コメントをどうぞ