华为OJ平台——杨辉三角的变形

 1 import java.util.Scanner;
 2 
 3 /**
 4  * 杨辉三角的变形
 5  *第一行为1，后面每一行的一个数是其左上角到右上角的数的和，没有的记为0
 6  *                        1
 7  *                    1    1    1
 8  *                1    2    3    2    1
 9  *            1    3    6    7    6    3    1
10  *        1    4    10    16    19    16    10    4    1
11  *    1    5。。。
12  *求第x行的第一个偶数是第几个
13  *
14  */
15 public class YangHui {
16 
17     public static void main(String[] args) {
18         Scanner cin = new Scanner(System.in) ;        
19         int line = cin.nextInt() ;
20         cin.close();
21                 
22         System.out.println(run(line)) ;
23         
24     }
25     
26     /**
27      * 计算返回值
28      * @param x
29      * @return
30      */
31     public static  int run(int x){
32         if(x == 1 || x == 2){
33             return -1 ;
34         }
35         //每一行的第一个数为1，第二个数为n-1；第三个数为 n*(n-1)/2
36         if(x%2 == 1){
37             return 2 ;
38         }else if(x*(x-1)%4 == 0){
39             return 3 ;
40         }
41         //若前三个均不是偶数，则从第四个数开始计算，由于是对称的的，所以判断到第x行的第x个数就可以了
42         for(int i = 4 ; i <= x ; i++){
43             int res = cal(x,i) ;
44             if(res%2 == 0){
45                 return i ;
46             }
47         }
48         return -1 ;
49      }
50     
51     /**
52      * 传入n,i表示第n行的第i个，返回其值，递归的方法求解
53      * @param n
54      * @param i
55      * @return
56      */
57     public static int cal(int n, int i){
58         if(i > n){
59             return cal(n,2*n-i) ;
60         }
61         if(n == 2 && i > 0){
62             return 1 ;
63         }
64         if(i == 1){
65             return 1 ;
66         }
67         if(i <= 0){
68             return 0 ;
69         }        
70         int res ;
71         res = cal(n-1,i) + cal(n-1,i-1) + cal(n-1,i-2) ;
72         return res ;
73     }
74 
75 }