本文主要是介绍【数学题-递推找规律】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行 中总共有多少偶数。
【解题思路】
在机房点击bnu的oj，发现首页推荐了这道题，点进去一看，原来是道数学题，好久没怎么做做数学的题了，于是就做了
其实之前一直做过类似的题，感觉是要推规律，下面给出代码
//方法一：直接模拟 times:1000ms
#include <iostream>
#include <bits/stdc++.h>
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<res&&i<=maxn;i++,j++)sum[i]=sum[j]*2;res*=2;}for(i=0; i<=maxn; i++)//第i行偶数个数sum[i]=i+1-sum[i];for(i=1; i<=maxn; i++) //前i行偶数个数sum[i]=(sum[i]+sum[i-1])%mod;long long n;while(cin>>n){printf("%lld\n",sum[n]);}return 0;
}
/*1 --0 1
1 1 --1 2
1 2 1 --2 2
1 3 3 1 --3 4
1 4 6 4 1 --4 2
1 5 10 10 5 1 --5 6
1 6 15 20 15 6 1 --6 9
1 7 21 35 35 21 7 1 --7 9
*/
//方法二：进制，times:Time Limit Exceed
/*
第n行里面奇数的个数等于2^K 个，
k等于n二进制数里面1的个数。
*/
#include <iostream>
#include <bits/stdc++.h>
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<maxn;i++){sum[i]=i+1; //第i行总共有多少元素sum[i]=sum[i]-(1<<solve(i));//第i行偶数个数}for(i=1;i<maxn;i++)sum[i]=(sum[i]+sum[i-1])%mod;
}
int main()
{int n;init();scanf("%lld",&n);printf("%lld\n",sum[n]);return 0;
}//方法三：一边计算一边累加，times:296ms
#include <iostream>
#include <bits/stdc++.h>
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;
}
这篇关于【数学题-递推找规律】BNU 4225 杨辉三角形的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
