杨辉三角的变形

杨辉三角

杨辉三角大家都熟悉，二项式n次方展开式的系数可排列成一个三角形的数表，成为杨辉三角。形似：

1

     1   1

  1   2   1

1  3   3  1

输出杨辉三角的代码：

import java.util.*;
public class Yanghui{
	public static void main(String args[]){
		Scanner scan = new Scanner(System.in);
		int n = Integer.parseInt(scan.next());
		int mat[][] = new int[n][];
		//
		int i,j = 0;
		for(i=0;i<n;i++){
			mat[i] = new int[i+1];
			mat[i][0] = 1;
			mat[i][i] = 1;
			for(j = 1;j < i; j++){
				mat[i][j] = mat[i-1][j-1]+mat[i-1][j];
			}
		}
		for(i = 0;i < mat.length;i++){
			for(j = 0; j<n-i;j++){
				System.out.print(" ");
			}
			for(j = 0;j<mat[i].length;j++){
				System.out.print(mat[i][j]+" ");
			}
			System.out.println();
		}
	}
}

题目：

         1

     1   1  1

  1  2   3  2  1

1  3  6   7  6  3  1

以上三角形的数阵，第一行只有一个数1， 以下每行的每个数，是恰好是它上面的数，左上的数和右上数等3个数之和（如果不存在某个数，认为该数就是0）。

求第n行第一个偶数出现的位置。如果没有偶数，则输出-1。例如输入3,则输出2，输入4则输出3。

输入n(n <= 1000000000)

开始的思路就是：将所有的数字都保存到二维数组中，然后在数组的最后一行开始寻找第一个偶数。

代码如下：

public class Test
{
	public static int run(int n)
	{
		int result = -1;
		int mat[][] = new int[n][];
		int i, j, k =0;
		for(i = 0;i < n;i++ ){
			mat[i] = new int[2*(i+1)-1];
			mat[i][0] = 1;
			for(j = 1; j< 2*(i+1)-1;j++){
				//left part
				if(j<=i){
					if(j-2<0){//针对第二列，第二列的元素没有左上角
						if(j < mat[i-1].length){
							mat[i][j] = mat[i-1][j]+mat[i-1][j-1];
						}else{//针对第二行 1  1  1
							mat[i][j] = mat[i-1][j-1];
						}
					}else{
						mat[i][j] = mat[i-1][j]+mat[i-1][j-1]+mat[i-1][j-2];
					}
					k = j;
				}else{
				//right part
					mat[i][j] = mat[i][--k];
				}
				
			}
		}
		//search
		
		for(j = 0; j < mat[n-1].length;j++){
			if(mat[n-1][j]%2 == 0){
				result = j+1;
				break;
			}
		}
		return result;
	}
	
	public static void main(String []args)
	{
		System.out.println(run(1));
	}
}

无奈修改了半天，还是超时，突然看到题目上有一个上线【1000000000】，才明白过来这样把每个数字都求出来必然会超时。

    最后想了半天还是没想起来好办法。只好求助与强大的百度了。看到网友的答案之后才发下原来如此的简单。

唉。思维一点都不活跃。只怪自己脑子没有转过来圈啊！！！谨记谨记！

具体答案参见下面几篇博文。

http://blog.csdn.net/SunnyYoona/article/details/16917447

http://blog.csdn.net/ToYueXinShangWan/article/details/15021313

http://blog.csdn.net/xhu_eternalcc/article/details/14390617

http://blog.csdn.net/jenly121/article/details/14521287

英雄会-----杨辉三角-----杨辉三角的变形

原文：http://blog.csdn.net/crazy1235/article/details/19783731