Java 練習題(二)：巴斯卡（Pascal）三角形

最近希望花點時間，重新訓練自己解題的能力，故找了一些經典的題目進行練習。
解法不一定是最有效率、最低複雜度、最佳效能的，完全是依照自己的想法做！

---

巴斯卡三角形長得如下：
             1
           1    1
        1    2    1
    1     3    3    1
  1    4    6    4    1
1............................1

從上圖可以觀察到，從第三層開始，每層的最左、右邊的值為1，其他的第M層第N值為第M-1層的第N-1 + N 的和。

假設題目要求：給任一數字N，印出巴斯卡三角形中第N層的數列。
構想：使用迴圈從3 to N，依序計算出每層的數列，使用兩個Array，一個用來儲存上一層的值、一個用來儲存第N層的值。程式碼如下：

	static ArrayList<Integer> numInLevelN = new ArrayList<Integer>();
	public static void main(String[] args) {
	// TODO Auto-generated method stub
	int number = 0;
	Scanner scanner = new Scanner(System.in);
	System.out.println("Enter a number: ");
	number = scanner.nextInt();
	if (number == 1) {
	numInLevelN.add(1);
	} else if (number == 2) {
	numInLevelN.add(1, 1);
	} else {
	numInLevelN = calculate(number);
	}
	System.out.print("numbers in this level = ");
	for(int i = 0; i < nums.size(); i++) {
	System.out.print(numInLevelN.get(i) + ", ");
	}
	}
	private static ArrayList<Integer> calculate(int number) {
	// TODO Auto-generated method stub
	ArrayList<Integer> p0 = new ArrayList<Integer>(); // level 0
	p0.add(1);
	ArrayList<Integer> p1 = new ArrayList<Integer>(); // level 1
	p1.add(1);
	p1.add(1);
	ArrayList<Integer> res = new ArrayList<Integer>();
	for (int i = 3; i <= number; i++) {
	for (int index = 0; index < i; index++) {
	if (index == 0) {
	res.add(0, 1);
	} else if (index == i - 1) {
	res.add(i - 1, 1);
	} else {
	res.add(index, p1.get(index - 1) + p1.get(index));
	}
	}
	p1.clear();
	p1.addAll(res);
	res.clear();
	}
	return p1;
	}

view raw Pascal hosted with ❤ by GitHub