作者:翟天保Steven
版权声明:著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处
题目描述:
以上三角形的数阵,第一行只有一个数1,以下每行的每个数,是恰好是它上面的数,左上角数到右上角的数,3个数之和(如果不存在某个数,认为该数就是0)。
求第n行第一个偶数出现的位置。如果没有偶数,则输出-1。例如输入3,则输出2,输入4则输出3。
输入n(n <= 1000000000)
本题有多组输入数据,输入到文件末尾,请使用while(cin>>)等方式读入
输入描述:
输入一个int整数
输出描述:
输出返回的int值
示例:
输入:
4 2
输出:
3 -1
解题思路:
本题两种解题思路。
- 第一种就是常规求解,见代码一。输入k行,按照杨辉三角的规律创建k行的三角数阵,然后在第k行寻找首次出现偶数的下标即可。
- 第二种就是找规律求解,见代码二。分析后可知,前两行为-1,从第三行开始有2324的循环,所以当行数为奇数,结果就为2;当行数被4整除,结果为3;其他就为4。
测试代码:
代码一:
#include <iostream>
#include <string>using namespace std;int main()
{int num;while(cin>>num){int row=num;int col=2*num-1;int L[row][col];for(int j=0;j<col;++j){L[0][j]=0;}L[0][row-1]=1;for(int i=1;i<row;++i){for(int j=1;j<col-1;++j){L[i][j]=L[i-1][j-1]+L[i-1][j]+L[i-1][j+1];}L[i][0]=L[i-1][0]+L[i-1][1];L[i][col-1]=L[i-1][col-1]+L[i-1][col-2];}int id=0;bool getresult=false;for(int j=0;j<col;++j){if(L[row-1][j]%2==0){cout<<j+1<<endl;getresult=true;break;}}if(!getresult)cout<<"-1"<<endl;}return 0;
}
代码二:
#include<iostream>
using namespace std;
int main(){int num;while(cin>>num){if(!num||num==1||num==2) cout<<-1<<endl;else if(num&1) cout<<2<<endl;else if(num%4) cout<<4<<endl;else cout<<3<<endl;}return 0;
}