杨辉三角

杨辉三角

问题描述：每一行的首尾两数均为1；第k行共k个数，除首尾两数外，其余各数均为上一行的肩上两数的和，如图：

问题分析：通过观察杨辉三角的第i行有i个元素（二维数组的下三角 ），并且a[i][1] = 1,a[i][j] = 1(i==j)。递推关系可得：a[i][j] = a[i-1]a[j-1]+a[i-1][j]
问题的解决：

• 我们可以用二维数组的下三角来模拟杨辉三角值的初始化
• 控制打印输出。

private static void triangle(int n) {
		int i, j, k;
		int triangle[][] = new int[n + 1][n + 1];
		for (i = 1; i <= n; i++) {
			for (j = 1; j <= i; j++) {
				if (j == 1 || i == j) {
					//第一列和对角线初始化为1；
					triangle[i][j] = 1;
				} else {
					triangle[i][j] = triangle[i - 1][j - 1]
							+ triangle[i - 1][j];
				}
			}
		}
//打印输出
		for (i = 1; i <= n; i++) {
			// 这里的系数3，和后面的格式输出中的6呈正好要是2倍关系，因为上一排的数字正好在下一排量个数的正中位置。
			for (k = 1; k < (3 * n + 1) - 3 * i; k++) {
				// 输出每排前面的空格
				System.out.print(" ");
			}
			for (j = 1; j <= i; j++) {
				// 元素左对齐，占6个字符
				System.out.printf("%6d", triangle[i][j]);
			}
			System.out.println();
		}
	}

评论

1 楼 clarkhuang 2012-10-09  

呵呵