【数学题-递推找规律】BNU 4225 杨辉三角形

【题目链接】​​click here~~​​

【题目大意】

LZM 同学比较牛， Lsy 最近也越来越生猛，他们思路快，代码速度神勇。近期惊闻此二人均要参加校赛，队里决定出些题目卡他们，因为他们的罢工给题目组留下了繁重的负担……（报复报复）

于是， XsugarX 瞄准了 LZM 不太喜欢看的数学题目以及 Lsy 猜公式的喜好，奸笑中（ ^.^ ）。这个数学问题是个比较古老的问题，有如下图的三角形被称为杨辉三角形：

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

我们记第一个 1 为第 0 行，往下依次编号。

其中三角形左右两斜边上的数字均为 1 ，其他位置均为其两肩上的数之和。

此两牛看到偶数就会觉得复杂，被卡的时间与偶数的个数成正比， XsugarX 希望能卡他们的时间越久越好。

给定任意杨辉三角的行数 n ，请输出杨辉三角中前 n行 中总共有多少偶数。

【解题思路】

其实之前一直做过类似的题，感觉是要推规律，下面给出代码

//方法一：直接模拟 times:1000ms

#include #include using namespace std;const int mod=1e7;const int maxn=3000000;long long sum[maxn+10];int main(){ int i,j; sum[0]=1,sum[1]=sum[2]=2,sum[3]=4; int res=4; for(i=4;i<=maxn;)//第i行奇数个数 { for(j=0;j>n) { printf("%lld\n",sum[n]); } return 0;}/*1 --0 11 1 --1 21 2 1 --2 21 3 3 1 --3 41 4 6 4 1 --4 21 5 10 10 5 1 --5 61 6 15 20 15 6 1 --6 91 7 21 35 35 21 7 1 --7 9*/

//方法二：进制，times:Time Limit Exceed

/*第n行里面奇数的个数等于2^K 个，k等于n二进制数里面1的个数。*/#include #include using namespace std;const int mod=1e7;const int maxn=3000000;long long sum[maxn+10];int solve(int n)//n二进制数里面1的个数{ int s=0; while(n!=0){ if(n%2==1) s++; n/=2; } return s;}void init(){ int i,j; for(i=0;i

//方法三：一边计算一边累加，times:296ms

#include #include using namespace std;const int mod=1e7;const int maxn=3000000;long long sum[maxn+10];int main(){ long long s=0,ans; int n,t; scanf("%d",&n); while(n>=0) { t=n; ans=1; while(t) { if(t%2==1) ans*=2; t/=2; } s+=n+1-ans; n--; } printf("%lld\n",s%mod); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。