首先说的是庞果网挺好的,暑假时候做的上面蓝港在线的一道题目,前几天蓝港的打来电话要简历了,不过我还在读研中,并且最近很忙,主要还是技术太搓,所以到现在还没将简历发过去。
下面是庞果网这周的题目---杨辉三角的变形:
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)
函数头部:
C/C++:
int run(int n);
------------------------------------------------------------------------
这是道找规律题,不可能通过计算每层的数据来求,规律如下:
(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 //提示:自动阅卷结束唯一标识,请勿删除或增加。
简单但需要耐心!