99
技術社區[雲棲]
龐果網之楊輝三角的變形
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
* 題號: 楊輝三角的變形
* 來源：https://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 //提示：自動閱卷結束唯一標識，請勿刪除或增加。
最後更新：2017-04-03 14:54:25