杨辉三角的变形-庞果网 （C/C++）

注：已通过测试

题目详情:

         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);

   由于 n <= 1000000000，肯定不能通过求每行的数字推出第一个偶数位置，所以我多写了几行，找规律（见下图）

     规律：

     (1). 1、2行没有偶数，返回 -1；

     (2). 奇数行第二个位置为偶数，返回 2；

     (3). 偶数行前4个位置模式重复，3 4 3 4 ... 返回 n/2 % 2 + 3。

代码实现：

int run(int x)
{
	if (x <= 2) // 1、2行都为-1
	{
		return -1;
	}
	else if (x%2 == 1) // 奇数行为 2
	{
		return 2;
	}
	// 偶数行
	return x/2 % 2 + 3;
}

    由于阿然吃饱了有事干，又优化了一下代码，把除法和取余操作用位操作实现，代码如下

int run(int x)
{
	if (x <= 2) // 1、2行都为-1
	{
		return -1;
	}
	else if (x & 1) // 奇数行为 2
	{
		return 2;
	}
	// 偶数行为 x/2 % 2 + 3
	return ((x >> 1) & 1) + 3;
}

// (x >> 1)是把x右移1位，相当于除以2，例如（6 >> 1）表示（0110 --> 0011），结果为3.

// 这个优化基本上没什么用，而且可读性很差（如果被频繁使用，倒可以考虑）

原题地址：http://hero.pongo.cn/Question/Details?ID=141&ExamID=139

杨辉三角的变形-庞果网 （C/C++）

原文：http://blog.csdn.net/chinaeran/article/details/19077229