[编程题]iNOC产品部-杨辉三角的变形

编程基础 • 2025-01-04 14:40 • 阅读 42

Talk is cheap, show me the code.

一、问题描述

 1 1 1 1 1 2 3 2 1

1 3 6 7 6 3 1

1 4 10 16 19 16 10 4 1

以上三角形的数阵，第一行只有一个数1，以下每行的每个数，是恰好是它上面的数，左上角数到右上角的数，3个数之和（如果不存在某个数，认为该数就是0）。求第n行第一个偶数出现的位置。如果没有偶数，则输出-1。例如输入3,则输出2，输入4则输出3。输入n(n <= )

输入描述：

输入一个int整数

输出描述：

输出返回的int值

输入例子：

输出例子：

二、问题解法

两种思路，一种是找规律，前两行没有偶数，直接返回-1，后面所有奇数行第2位都是偶数，直接返回2，所有偶数行中能被4整除的直接返回3，所有偶数行中不能被4整除的直接返回4。这个解法需要对杨辉三角特点归纳一下，但如果找到规律解题就很快。

#include <iostream> using namespace std; int main() { int n; while(cin >> n) { if(n <= 2) cout << -1 << endl; if(n%2 == 1) cout << 2 << endl; else if(n%2 == 0) { if(n%4 == 0) cout << 3 << endl; else cout << 4 << endl; } } return 0; }

另一种思路是直接遍历第n行中每个数，当找到第一个偶数时返回序号，这个需要对杨辉三角的计算过程比较熟悉，递归的结束条件一定要控制好。

#include <iostream> using namespace std; int f(int a, int b) { if(a == 1 && b == 1) return 1; if(b <= 0) return 0; if(b > (2*a-1)) return 0; return (f(a-1,b-2)+f(a-1,b-1)+f(a-1,b)); } int main() { int n; while(cin >> n) { bool flag = false; for(int i = 2; i < 2*n-1;i++) { if(f(n, i)%2 == 0) { flag = true; cout << i << endl; break; } } if(!flag) cout << "-1" << endl; } return 0; }

今天的文章 [编程题]iNOC产品部-杨辉三角的变形分享到此就结束了，感谢您的阅读。

[编程题]iNOC产品部-杨辉三角的变形

一、问题描述

二、问题解法

相关推荐