首页 > 试题广场 >

杨辉三角的变形

[编程题]杨辉三角的变形

热度指数：178874 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

$\hspace{15pt}$ 定义变形的杨辉三角规则：
$\hspace{23pt}\bullet\,$ 第一行为固定的整数 $1$ ；
$\hspace{23pt}\bullet\,$ 第二行开始，每行的数字数量均比上一行多两个，且中心对称（也可以看作是在上一行的基础上首尾增加了一个数字）；每个位置上的数字是它正上方、左上角和右上角这三个数之和（如果不存在某个数，认为该数就是 $0$ ）。
$\hspace{15pt}$ 下方展示了计算的过程：
$\begin{bmatrix} 1 \end{bmatrix} \to \begin{bmatrix} {\color{grey}0} & 1 & {\color{grey}0} \\ 1 & 1 & 1 \end{bmatrix} \to \begin{bmatrix} {\color{grey}0} & {\color{grey}0} & 1 & {\color{grey}0} & {\color{grey}0} \\ {\color{grey}0} & 1 & 1 & 1 & {\color{grey}0} \\ 1 & 2 & 3 & 2 & 1 \end{bmatrix} \to \begin{bmatrix} {\color{grey}0} & {\color{grey}0} & {\color{grey}0} & 1 & {\color{grey}0} & {\color{grey}0} & {\color{grey}0} \\ {\color{grey}0} & {\color{grey}0} & 1 & 1 & 1 & {\color{grey}0} & {\color{grey}0} \\ {\color{grey}0} & 1 & 2 & 3 & 2 & 1 & {\color{grey}0} \\ 1 & 3 & 6 & 7 & 6 & 3 & 1 \end{bmatrix}$

$\hspace{15pt}$ 现在，你需要输出第 $n$ 行中第一个偶数出现的位置。从 $1$ 开始计数。

输入描述:

输入一个整数  代表询问的行数。

输出描述:

输出一个整数，代表第  行中第一个偶数出现的位置。特别地如果第  行中没有偶数，则输出 。

示例1

输入

输出

示例2

输入

输出

示例3

输入

输出

-1

算法知识视频讲解

Javascript_V8

Little-Bird

1
1,1
1,2,1
1,3,3,1
1,4,6,4,1
1,5,10,10,5,1
1,6,15,20,15,6,1
1,7,21,35,35,21,7,1
1,8,28,56,70,56,28,8,1
1,9,36,84,126,126,84,36,9,1
1,10,45,120,210,252,210,120,45,10,1

1,11,55,165,330,462,462,330,165,55,11,1

var line;
while ((line = readline())) {
console.log(fun(parseInt(line)));
}
// 每一行的第一列都是1，可以忽略
// 观察可得从第三行的第二列开始，就成奇偶的
// 那么思路就出现了

function fun(row) {
if (row == 1 || row== 2) {
return -1;
} else if (row % 2 == 1) {
return 2;
} else if (row % 4 == 0) {
return 3;
} else {
return 4;
}
}

发表于 2022-05-25 00:04:53 回复(0)

Python3

Huiru

while True:
try:
n=int(input())
if n==1 or n==2:
i=-1
elif (n-2) % 2 == 1:
i=2
elif n % 4 == 0:
i=3
else:
i=4
print(i)
except EOFError:
break

发表于 2021-08-29 11:19:19 回复(0)

Python 3

_Kuuga

把一整行都求出来看：

import sys

def yanghui(now, line = [1], n = 1):
    if n == now:
        return line
    else:
        n += 1
        nextLine = [1, 1]
        if n == 2:
            nextLine = [1, 1, 1]
        elif n > 2:
            nextLine = [1, n-1, n-1, 1]
        for i in range(2, 2 * n - 3):
            nextLine.insert(i, sum(line[i - 2:i + 1]))
        return yanghui(now, nextLine, n)
        
for i in sys.stdin:
    i = int(i.strip())
    line = yanghui(i)
    notfind = True
    for index in range(i):
        if line[index]%2 == 0:
            print(index + 1)
            notfind = False
            break
    if notfind:
        print(-1)

发表于 2021-08-04 10:01:28 回复(0)

IAMLEUNGWEI

import java.util.Scanner;
//杨辉三角规律                                    行号    第一个偶数在该行第几个
//                    1                           1             -1
//                1   1   1                       2             -1
//            1   2   3   2   1                   3              2
//         1  3   6   7   6   3   1               4              3
//      1  4  10  16  19  16  10  4  1            5              2
//   1  5  15 30  45  51  45  30  15 5  1         6              4
//
//  首个偶数在该行第几个的规律： -1 -1 （2 3 2 4）···（2 3 2 4）

public class MainHJ53 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] res = new int[]{2,3,2,4};
        while(sc.hasNext()){
            int n = sc.nextInt();
            System.out.println(res[(n+1)%4]);
        }
    }
}

发表于 2021-03-29 16:58:07 回复(0)

C/C++

人海追风

好家伙，找规律，面向答案编程？

#include<iostream>
#include<vector>
using namespace std;


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

发表于 2021-03-10 17:44:30 回复(0)

tigg_ZZ

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        Main a = new Main();
        while (scanner.hasNext()){
            int row = Integer.parseInt(scanner.nextLine());
            System.out.println(a.firstEven(row));
        }
    }
    public int firstEven(int row){
        if ((row == 1 || row == 2)){
            return -1;
        }
        int result = row % 2 != 0 ? 2 : (row % 4 == 0 ? 3 : 4);
        return result;
    }
}

发表于 2021-01-15 14:15:25 回复(0)

牛勇

/* 本题观察数据有规律可循
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 5 15 30 45 51 45 30 15 5 1
1 6 21 50 90 126 141 126 90 50 21 6 1
1 7 28 77 161 266 357 393
1 8 36 112
1 9 45 156
*/
#include <iostream>
using namespace std;
int main(void)
{
long long num=0;
while(cin>>num)
{
if(num<=2)//不存在偶数
cout<<"-1"<<endl;
else
{

if(num%2!=0)//奇数行第一个偶数肯定为第二个值
{
cout<<"2"<<endl;
}
else
{ //如果是偶数行，该行数如果整除2后的值为偶数则输出3，否则输出4
if((num/2)%2==0)
cout<<"3"<<endl;
else
cout<<"4"<<endl;

}
}

}
return 0;
}

发表于 2020-06-18 18:03:49 回复(0)

C/C++

WZ_Dale

按照题目意思，可以发现第n行有2n -1个元素，第i,j元素等于上一行第j -2,j -1,j三列元素之和，每一行的第一列和最后一列都为1。

#include <iostream>
#include <vector>
using namespace std;
int main(){
    int n;
    while(cin >> n){
        vector<vector<int>> vv(n);
        for(int i = 0; i < n; ++i){
            vv[i].resize(i * 2 + 1, 1);
        }
        for(int i = 2; i < n; ++i){
            for(int j = 1; j < i * 2; ++j){
                if(j == 1){
                    vv[i][j] = vv[i - 1][j - 1] + vv[i - 1][j];
                }
                else if(j == i * 2 - 1){
                    vv[i][j] = vv[i - 1][j - 2] + vv[i - 1][j - 1];
                }
                else{
                    vv[i][j] = vv[i - 1][j - 2] + vv[i - 1][j - 1] + vv[i - 1][j];
                }
            }
        }
        int i = 0;
        for(; i < (n - 1) * 2 + 1; ++i){
            if(vv[n - 1][i] % 2== 0){
                cout << i + 1 << endl;
                break;
            }
        }
        if(i == (n - 1) * 2 + 1){
            cout << -1 << endl;
        }
    }
    return 0;
}

发表于 2020-06-12 16:57:37 回复(0)

markinLi

#include <stdio.h>
(737)#include <stdlib.h>
// 奇数+奇数=偶数 奇数+偶数=奇数
// 偶数+偶数=偶数
// 奇+奇+奇 = 奇
// 偶+偶+偶 = 奇
// 这种方法也可以得出当前值
#define N (1000) // 不符合题意n <= 1000000000，但是通过了所有示例
int dp[N][N + 4] = { 0 };
int main(void)
{
	int n = 0;
	
	while (scanf("%d",&n)!=EOF)
	{
		
        //int dp[n+3][n+3];
		for (int i = 0; i <= n; i++)
		{
			dp[i][0] = 0; //偶数
			dp[i][1] = 1; //奇数
		}
		for (int i = 1; i <= n; i++)
		{
			for (int j = 2; j <= i+2; j++)
			{
				dp[i][j] = dp[i - 1][j - 2] + dp[i - 1][j - 1] + dp[i - 1][j];
				if (dp[i][j] == 2)
					dp[i][j] = 0;
				else if (dp[i][j] == 3)
					dp[i][j] = 1;
			}
		}
		for (int i = 1; i <= n; i++)
		{
			if (dp[n-1][i] == 0)
			{
				printf("%d\n", i);
				break;
			}
		}
	}
    return 0;
}

发表于 2020-02-23 19:53:27 回复(0)

小陈也只是想要一个实习罢了

//找规律的过程稍微麻烦了一点，注意边界条件，然后n-1那些条件再做的时候可能还是会看不懂
//大意提示：存储一半的表，然后根据计算公式由上一行得到下一行的值
#include<iostream>
using namespace std;
int main(){
    int n;
    while(cin>>n){
        if(n==1||n==2){
            cout<<"-1"<<endl;
        }
        else{
            int** a=new int*[n];
            for(int i=0;i<n;i++)
                a[i]=new int[n];
            for(int i=0;i<n-1;i++)
                a[0][i]=0;
            a[0][n-1]=1;
            for(int i=1;i<n;i++){
                for(int j=0;j<n-i-1;j++)
                    a[i][j]=0;
                a[i][n-i-1]=1;
                for(int j=n-i;j<n-1;j++)
                    a[i][j]=a[i-1][j-1]+a[i-1][j]+a[i-1][j+1];
                a[i][n-1]=2*a[i-1][n-2]+a[i-1][n-1];
            }
            bool judge=1;
            for(int i=0;i<n;i++)
                if(a[n-1][i]%2==0){
                    cout<<i+1<<endl;
                    judge=0;
                    break;
                }
            if(judge)
                cout<<"-1"<<endl;
        }
    }
}

发表于 2020-01-07 22:46:07 回复(0)

OrientObjectPro

#include<iostream>
#include<string>
#include<vector>
using namespace std;

int my_***(int n)
{
int result=-1;
vector<vector<int>> vec(n);
for(int i=0;i<n;i++)
{
vec[i].resize(2*i+3);
vec[i][0]=vec[i][2*i+2]=0;
vec[i][1]=vec[i][2*i+1]=1;
}
for(int i=1;i<vec.size();i++)
{
for(int j=2;j<vec[i].size()-2;j++)
{
vec[i][j]=vec[i-1][j]+vec[i-1][j-1]+vec[i-1][j-2];
}
}


for(int i=2;i<vec[n-1].size()-2;i++)
{
if(vec[n-1][i]%2==0)
{
result=i;
break;
}
}
return result;
}

int main()
{
int N;
while(cin>>N)
{

cout<<my_***(N)<<endl;
}
return 0;
}

发表于 2019-05-07 13:40:01 回复(0)

Tendō·Pein

 #include<iostream>
#include<vector>
using namespace std;
int f(int a,int b)
{
    if(a<1||b<1||b>a)
        return 0;
    else if(b==1)
        return 1;
    else if(a!=b)
    {
        return f(a-1,b-1)+f(a-1,b-2)+f(a-1,b);
    }
    else if(a==b)
        return f(a-1,b-1)+2*f(a-1,b-2);
    else 
        cout<<"err";
    return 0;
}

int main()
{
    int a;
    
    while (cin >> a)
    {
        int flag = 0;
        for (int i = 1; i <= a; i++)
        {
            if (!(f(a, i) & 1))
            {
                cout << i << endl;
                flag = 1;
                break;
            }
        }
        if (flag ==0)
        cout << -1 << endl;
    }
    return 0;
}

发表于 2018-08-07 16:33:44 回复(1)

Java

M870RushB

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        
        System.out.println(res(num));
    }
    
    public static int res(int num){
        if(num == 1 || num == 2){
            return -1;
        }
        
        num -= 2;
        if(num%2 == 1){
            return 2;
        }
        if(num%2 == 0 && num%4 != 0){
            return 3;
        }
        if(num%2 == 0 && num%4 == 0){
            return 4;
        }
        return 0;
    }
}

找规律

发表于 2022-04-21 10:38:54 回复(0)

Java

LSur

import java.util.Scanner;

/**
 * @author Yuliang.Lee
 * @version 1.0
 * @date 2021/9/22 17:59
 * 杨辉三角的变形：
              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。

 * 示例：
    输入:
        4
        2
    输出：
        3
        -1
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int rowNum = in.nextInt();
            // 定义二维数组
            int colNum = 2 * rowNum - 1;
            int[][] arr = new int[rowNum][colNum];
            // 初始化首行
            for (int i = 0; i < colNum; i++) {
                arr[0][i] = 0;
                if (i == colNum / 2) {
                    arr[0][i] = 1;
                }
            }
            // 填充数组
            for (int i = 1; i < rowNum; i++) {
                for (int j = 0; j < colNum; j++) {
                    if (j == 0) {
                        arr[i][j] = arr[i-1][j] + arr[i-1][j+1];
                    } else if (j == colNum - 1) {
                        arr[i][j] = arr[i-1][j-1] + arr[i-1][j];
                    } else {
                        arr[i][j] = arr[i-1][j-1] + arr[i-1][j] + arr[i-1][j+1];
                    }
                }
            }
            // 找最后一行的数字中第一次出现偶数的位置
            int result = -1;
            for (int j = 0; j < colNum; j++) {
                if (arr[rowNum - 1][j] != 0 && arr[rowNum - 1][j] % 2 == 0) {
                    result = j + 1;
                    break;
                }
            }
            System.out.println(result);
        }
    }
}

发表于 2021-09-22 18:43:24 回复(0)

Continue

import java.util.*;
 
public class Main{
    public static void main(String[] args){
 		Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            int n = in.nextInt();
            if(n<=2)
                System.out.println(-1);
            else if(n%2==1){
                System.out.println(2);
            }else{
                if(n%4==0)
                	System.out.println(3);
                else
                    System.out.println(4);
            }
        }
        in.close();
    }
}

发表于 2016-04-08 15:33:01 回复(12)

VagrantYang

记录了自己的ac代码，欢迎pull request
https://github.com/SpecialYy/HUAWEI_Programming.git

package com.special.spet;
import java.util.Scanner;
/** 
* 杨辉三角变形
* 注意每一行的规律，每一行有2 * i - 1个数，中间的数位于第i个位置
* 从第1行开始（而不采用第0行）方便后面的计算
* map[i][j] = map[i - 1][j - 1] + map[i - 1][j - 2] + map[i - 1][j]
* 注意若采用上式，在算map[i][1]直接赋值，否则map[i - 1][j - 2]会数组越界
* 判断第几位是偶数时，只需循环到中间位置即可，因为每一行的数是对称的。
* @author special
* @date 2017年11月22日 下午11:15:13
*/
public class Pro52 {
    public static int getFirstPlaceEven(int n){
        int[][] map = new int[n + 1][2*n];
        map[1][1] = 1;
        for(int i = 2; i <= n; i++){
            map[i][1] = 1;
            for(int j = 2; j <= 2 * i - 1; j++)
                map[i][j] = map[i - 1][j - 1] + map[i - 1][j - 2] + map[i - 1][j];
        }
        for(int i = 1; i <= n; i++)
            if(map[n][i] % 2 == 0)
                return i;
        return -1;
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner input = new Scanner(System.in);
        while(input.hasNext()){
            int n = input.nextInt();
            int firstEven = getFirstPlaceEven(n);
            System.out.println(firstEven);
        }
    }
}

编辑于 2017-11-23 09:22:13 回复(4)

当艾已成往事1996

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

发表于 2016-07-08 20:11:35 回复(3)

joykechen

//思路：1.找规律，发现，如果用数组表示的话，第1行的1并不是在最左边，而是在第n个元素位置（n代表行号）
//	   2.第n行的元素的第一个和最后一个是要提前赋值为1.其他行的元素，除第一个外，按照公式
//		a[i][j]=a[i][j-1]+a[i][j]+a[i][j+1];
#include<iostream>
#include<vector>
using namespace std;
void printYH(int n)
{
    
    vector<vector<int> >a(n,vector<int>(2*n-1,0));
    a[0][n-1]=a[n-1][0]=a[n-1][2*n-2]=1;
    if(n<2)
    {
        cout<<"-1"<<endl;
        return ;
    }
    for(int i=1;i<n;++i)
        for(int j=1;j<2*n-2;++j)
            a[i][j]=a[i-1][j]+a[i-1][j-1]+a[i-1][j+1];
    for(int i=0;i<2*n-1;++i)
        if(a[n-1][i]!=0 && (a[n-1][i]%2==0))
        {
            cout<<i+1<<endl;
            return ;
        }
    return ;                    
}
int main()
{
    int n;
    while(cin>>n)
    {
        printYH(n);
	}
    return 0;
}

编辑于 2017-05-06 15:46:05 回复(7)

我不是董皓宇。

最简单的方法就是找规律

1. 第二行，前三个数字为奇数，所以，它下面的的一行（第三行）第二个数必定为偶数

2. 第三行前三个数为奇偶奇，所以，第四行一定为奇奇偶，所以第五行一定为奇偶偶，

3. 第六行为奇奇奇，显然，第六行与第二行相同，都为三个奇数。可以定为一次循环。

4. 除去第1，2行，后面为循环。即得结果如下：

int main()
{
    int n;
    while(cin>>n)
    {
        if(n <= 2)
            cout<<-1<<endl;
        else if((n-2) % 4 == 0)
            cout<<4<<endl;
        else if(n % 2 == 1)
            cout<<2<<endl;
        else
            cout<<3<<endl;
    }
}

编辑于 2019-11-25 14:21:35 回复(2)

编程菜

JAVA看规律
import java.util.*;
public class Main{
	public static void main(String[] args){
		Scanner cin=new Scanner(System.in);
		while(cin.hasNext()){
			int n=cin.nextInt();
			if(n<=2)
				System.out.println(-1);
			else if(n%2==1)
				System.out.println(2);
			else if(n%4==0)
				System.out.println(3);
			else 
				System.out.println(4);
		}
		cin.close();
	}
}






第一种方法是看规律
#include<iostream>
using namespace std;
int main()
{
	int n;
	while(cin>>n){
		if(n<=2)cout<<"-1"<<endl;
		else if(n%2==1)cout<<"2"<<endl;
		else if(n%4==0)cout<<"3"<<endl;
		else cout<<"4"<<endl;
	}
	return 0;
}
第二种方法是货真价实的干
#include<iostream>
using namespace std;
int main()
{
	int n;
	while(cin>>n){
		if(n<=0)return 0;
		int i,j,k,Num=-1;
		int **a=new int *[n];
		for(i=0;i<n;i++)
		a[i]=new int[2*n-1];
		for(j=0;j<n;j++)
		for(k=0;k<2*n-1;k++)
		a[j][k]=0;
		a[0][n-1]=1;
		a[n-1][0]=1;
		a[n-1][2*n-2]=1;
		for(i=1;i<n;i++)
		for(j=1;j<2*n-2;j++)
		a[i][j]=a[i-1][j-1]+
		a[i-1][j]+a[i-1][j+1];
		for(j=0;j<2*n-1;j++)
		if(a[n-1]!=0&&a[n-1][j]%2==0)
		{
			Num=j+1;
			break;
		}
		cout<<Num<<endl;
	}
	return 0;
}

编辑于 2016-07-24 15:57:03 回复(3)

提交观点

问题信息

基础数学

难度：

481条回答 2130收藏 37060浏览

通过挑战的用户

查看代码

帅阿衰

2023-01-08 10:48:50
牛客79375...

2022-11-05 18:25:40
芊樱烛渊

2022-10-29 22:21:04
Theonly...

2022-10-28 23:55:58
牛客70572...

2022-10-28 13:54:48