题目详情
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
* 题号: 杨辉三角的变形
* 来源:http://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 //提示:自动阅卷结束唯一标识,请勿删除或增加。
分享到:
相关推荐
使用C++对杨辉三角变形的思考过程及代码实现,作为一个程序员,数学学得好能提升程序的效率。
杨辉三角算法杨辉三角算法杨辉三角算法杨辉三角算法杨辉三角算法杨辉三角算法杨辉三角算法杨辉三角算法杨辉三角算法杨辉三角算法杨辉三角算法杨辉三角算法杨辉三角算法
杨辉三角形的特点是两个腰上的数字都为1,其它位置上的数字是其上一行中与之相邻的两个整数之和。所以在打印过程中,第i行上的元素要由第i-1行中的元素来生成。 Input 第1行为一个整数t(1≤t≤10...杨辉三角的每一行。
利用队列打印杨辉三角利用队列打印杨辉三角利用队列打印杨辉三角利用队列打印杨辉三角利用队列打印杨辉三角利用队列打印杨辉三角利用队列打印杨辉三角利用队列打印杨辉三角利用队列打印杨辉三角利用队列打印杨辉三角...
c语言实现杨辉三角 数据结构资源 c语言实现杨辉三角 数据结构资源 c语言实现杨辉三角 数据结构资源
以上三角形的数阵,第一行只有一个数1, 以下每行的每个数,是恰好是它上面的数,左上的数和右上数等3个数之和(如果不存在某个数,认为该数就是0)。 求第n行第一个偶数出现的位置。如果没有偶数,则输出-1。例如...
java实现杨辉三角 杨辉三角.java用java实现杨辉三角的程序
实现杨辉三角形的C++代码,基础编程实例
杨辉三角C++编程杨辉三角C++编程杨辉三角C++编程杨辉三角C++编程
杨辉三角(VB6.0代码编写)杨辉三角使用Tab函数,演示如何在Picture控件上显示杨辉三角形。
python实现打印杨辉三角,简洁明了注释清晰下载可以直接运行
Java SE程序 杨辉三角Java SE程序 杨辉三角Java SE程序 杨辉三角Java SE程序 杨辉三角Java SE程序 杨辉三角Java SE程序 杨辉三角Java SE程序 杨辉三角Java SE程序 杨辉三角Java SE程序 杨辉三角Java SE程序 杨辉三角...
杨辉三角,是二项式系数在三角形中的一种几何排列 每个数等于它上方两数之和。 每行数字左右对称,由1开始逐渐变大。 第n行的数字有n项。 第n行数字和为2n-1。 第n行的m个数可表示为 C(n-1,m-1),即为从n-1个...
经典的杨辉三角小程序。经典的杨辉三角小程序。经典的杨辉三角小程序。
洋哥刚写出来的新鲜代码,通过java中for循环与两个数组的调用,实现杨辉三角算法,供大家分享交流
在网页中用js输出 杨辉三角 Untitled-1.html
杨辉三角ppt课件(20页).pdf
queue.h头文件:循环队列的实现,操作包括初始化队列、入队、检查是否为空、出队、检查是否为满。源.cpp:利用两个队列打印出杨辉三角。
杨辉三角c++程序杨辉三角c++程序杨辉三角c++程序杨辉三角c++程序杨辉三角c++程序杨辉三角c++程序杨辉三角c++程序杨辉三角c++程序杨辉三角c++程序杨辉三角c++程序
杨辉三角前100行