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

注：已通过测试

题目详情:

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；< http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+ICAgICAoMikuIMbmyv3Q0LXatv649s671sPOqsW8yv2jrLe1u9ggMqO7PC9wPgo8cD4gICAgICgzKS4gxbzK/dDQx7A0uPbOu9bDxKPKvdbYuLSjrDMgNCAzIDQgLi4uILe1u9ggbi8yICUgMiAmIzQzOyAzoaM8L3A+CjxwPjxzdHJvbmc+tPrC68q1z9ajujwvc3Ryb25nPjwvcD4KPHA+PC9wPgo8cHJlIGNsYXNzPQ=="brush:java;">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)是按位与操作，例如（3 & 1）在二进制是（0101 & 0001），结果为1.

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

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

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

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