杨辉三角前n行 偶数个数 与奇数个数

传送门

题意：

求出杨辉三角前n层所有偶数的个数，n最大到 1 0 50 10^{50} 1050

注意：杨辉三角有 第0层， 所以第n层，与第n行含义不同第n行 为第n-1 层，第0层  1
第1层  1 1
第2层  1 2 1
第3层  1 3 3 1
第4层  1 4 6 4 1
第5层  1 5 10 10 5 1
第6层  1 6 15 20 15 6 1
第7层  1 7 21 35 35 21 7 1
第8层  1 8 28 56 70 56 28 8 1
第9层  1 9 36 84 126 126 84 36 9 1

思路

打表找规律，发现 前n行 所有 偶数的个数公式 如下，

​ \quad (注意公式计算的结果 是 从0 层开始的 前n行的 偶数个数)

​ \quad (即 前4行 对应的 从0 层到 第 3层）

S 0 = S 1 = 0 S 2 n = 3 S n + n ( n − 1 ) 2 S 2 n + 1 = 2 S n + S n + 1 + n ( n + 1 ) 2 \quad S_0 = S_1=0 \\ \quad S_{2n}=3S_n+\frac{n(n-1)}{2} \\\quad S_{2n+1}= 2S_n+S_{n+1}+\frac{n(n+1)}{2} S0​=S1​=0S2n​=3Sn​+2n(n−1)​S2n+1​=2Sn​+Sn+1​+2n(n+1)​

​
直接 递归+记忆化(解决多组数据时递归爆内存 使用map 记录) +大数

java 大数的基础运用 https://blog.csdn.net/nefu__lian/article/details/108932598

AC代码（Java）

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.math.BigInteger;public class  Main{static BigInteger one=BigInteger.ONE;static BigInteger zero=BigInteger.ZERO;static BigInteger two=BigInteger.valueOf(2);static BigInteger three=BigInteger.valueOf(3);static Map<BigInteger, BigInteger> mp=new HashMap<BigInteger, BigInteger>();public static void main(String[] args) {Scanner in=new Scanner(System.in);BigInteger n,ans;while(in.hasNextBigInteger()){n=in.nextBigInteger();     ans=f(n.add(one));    //   n要 加1 的原因为 公式计算 前n层 ,  而题目的 第N层 对应 公式的n+1 层System.out.println(ans);}}static BigInteger f(BigInteger n) {BigInteger m,res;if(mp.get(n)!=null)return mp.get(n);if(n==one||n==zero)return zero;if(n.mod(two)==zero){m=n.divide(two);res= three.multiply(f(m)).add((m.multiply(m.subtract(one))).divide(two));		 }else {  m=n.subtract(one).divide(two);res=two.multiply(f(m)).add(f(m.add(one))).add(m.multiply(m.add(one)).divide(two));}mp.put(n,res);return res;	 }
}

思考 前n行 所有 奇数个数

[杨辉三角的性质]https://blog.csdn.net/nefu__lian/article/details/108932343

前n 行 共有多少个数字 （即前n-1层），符合等差 数列公式，公差为1

S n = n a 1 + n ( n − 1 ) 2 d = n + n 2 − n 2 = n ( n + 1 ) 2 S_n= na_1+\frac{n(n-1)}{2}d= n+\frac{n^2-n}{2}= \frac{n(n+1)}{2} Sn​=na1​+2n(n−1)​d=n+2n2−n​=2n(n+1)​ （n 为行 即n-1层）

奇数个数=总数-偶数个数

AC 代码（java）

注意这是前n行， 上面的代码时前 n 层

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.math.BigInteger;public class  Main{static BigInteger one=BigInteger.ONE;static BigInteger zero=BigInteger.ZERO;static BigInteger two=BigInteger.valueOf(2);static BigInteger three=BigInteger.valueOf(3);static Map<BigInteger, BigInteger> mp=new HashMap<BigInteger, BigInteger>();public static void main(String[] args) {Scanner in=new Scanner(System.in);BigInteger n,ans;while(in.hasNextBigInteger()){n=in.nextBigInteger();     ans=f(n);   System.out.println("前n行 偶数个数： "+ans);System.out.println("前n行 奇数个数： "+sum(n).subtract(ans));}}static BigInteger f(BigInteger n) {    //  前n行 偶数个数BigInteger m,res;if(mp.get(n)!=null)return mp.get(n);if(n==one||n==zero)return zero;if(n.mod(two)==zero){m=n.divide(two);res= three.multiply(f(m)).add((m.multiply(m.subtract(one))).divide(two));		 }else {  m=n.subtract(one).divide(two);res=two.multiply(f(m)).add(f(m.add(one))).add(m.multiply(m.add(one)).divide(two));}mp.put(n,res);return res;}static BigInteger sum(BigInteger n){   // 前n行 杨辉三角总数return n.multiply(n.add(one)).divide(two);}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！