开发者社区> sjf0115> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

庞果网之杨辉三角的变形

简介:
+关注继续查看

题目详情

         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 //提示:自动阅卷结束唯一标识,请勿删除或增加。



版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
VB编程:for循环输出杨辉三角-45
VB编程:for循环输出杨辉三角-45
6 0
怒刷力扣(杨辉三角)
杨辉三角是在数学二项式中会遇到,在简单的算法题中出现的频率也是很高,不过确实是个简单的算法题,快来看看吧。
26 0
【LeetCode刷题笔记】leetcode题——杨辉三角
【LeetCode刷题笔记】leetcode题——杨辉三角
37 0
VB编程:for循环输出杨辉三角
VB编程:for循环输出杨辉三角
99 0
队列练习——杨辉三角
队列练习——杨辉三角
76 0
HDOJ(HDU) 1799 循环多少次?(另类杨辉三角)
Problem Description 我们知道,在编程中,我们时常需要考虑到时间复杂度,特别是对于循环的部分。例如, 如果代码中出现 for(i=1;i
910 0
C#打印杨辉三角
重主要的方法在于: 1.初始化二维数组 2.边界赋值 3.中心值赋值 4.输出 class Program { static void Main(string[] args) { Console.
808 0
+关注
sjf0115
Stay Hungry, Stay Foolish---我们必须用谦虚者的自觉,饥饿者的渴望的求职态度,来拥抱我们的未来。
788
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载