99
庞果网之杨辉三角的变形
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)
【解析】
经过分析得出的结论如下：
1.前两行没有偶数可直接返回-1
2.一下每四行一个周期，2,3,2,4进行变换。
3.假设当前行为n，n%4 = 0 偶数位置为 3
n%4 = 1 偶数位置为 2
n%4 = 2 偶数位置为 4
n%4 = 3 偶数位置为 2
【代码】
/*********************************
* 日期：2013-11-24
* 作者：SJF0115
* 题号: 杨辉三角的变形
* 来源：https://hero.pongo.cn/Question/Details?ID=141&ExamID=139
* 结果：AC
* 来源：庞果网
* 总结：
**********************************/
#include <iostream>
#include <stdio.h>
#include <malloc.h>
#include <string.h>
using namespace std;
int run(int n){
//前两行直接返回-1
if(n <= 2){
return -1;
}
else{
int index = n % 4;
if(index == 1 || index == 3){
return 2;
}
else if(index == 0){
return 3;
}
else if(index == 2){
return 4;
}
}
}
int main() {
int n;
while(scanf("%d",&n) != EOF){
printf("%d\n",run(n));
}//while
return 0;
}
【解法2】（转载）
这是道找规律题，不可能通过计算每层的数据来求，规律如下：
（1）第n层有2n-1个数，且关于第n个数对称；
（2）有第（1）得每行的中间数为奇数（x+x+奇数=奇数)；
（3）前两行没有偶数，返回-1
感觉上面3条规律没啥用～
（4）每行的第1个数是1，每行的第2个数等于n-1（通过0+1+前一行的第二个数得到）
通过（4）我们就解决了奇数行的第一个偶数位置，为2
（5）这条规律主要是解决偶数行的问题，这条规律我不是看出来的，是多写了几层发现的，然后归纳证明了下：
现在将奇数写作1，偶数写作0，x代表省略不考虑，不影响计算结果的奇偶性
第4行数据： 1 1 0 1 x --第一个偶数出现的位置是3
第5行....： 1 0 0 0 x
第6行....： 1 1 1 0 x --第一个偶数出现的位置是4
第7行....： 1 0 1 0 x
第8行....：1 1 0 1 x --第一个偶数出现的位置是3
同时前4个数据的奇偶状态又回到了第4行，而且每行前4个数据的计算只跟上行的前4个数据有关。
到此偶数行的问题也解决了，下面是代码，已通过pongo的测试：
#include <stdio.h>
#include <iostream>
#include <string>
using namespace std;
class Test {
public:
static int run (int x)
{
int res=-1;
if(x<=2) res=-1;
else if(1==x%2)
res=2;
else res=3+(x-4)/2%2;
return res;
}
};
//start 提示：自动阅卷起始唯一标识，请勿删除或增加。
int main()
{
cout<<Test::run(42)<<endl;
}
//end //提示：自动阅卷结束唯一标识，请勿删除或增加。
最后更新：2017-04-03 14:54:25