首页 > 试题广场 >

杨辉三角的变形

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

热度指数：170810 时间限制：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

算法知识视频讲解

Java

牛客935974817号

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n =in.nextInt();
        if(n==1||n==2){
            System.out.println("-1");
            return;
        }
        if(n%2!=0){
            System.out.println("2");
            return;
        }
        if(n%4!=0){
            System.out.println("4");
            return;
        }else{
            System.out.println("3");
            return;
        }

    }
}

找规律得出以上结果。

发表于 2025-04-05 17:45:39 回复(0)

Java

小煎饺子

想通过算出杨辉三角的值再求第n行第一个偶数，结果n比较大时，不是内存溢出，就是超时间，只能按结果的规律取巧了。

import java.util.Scanner;

// 从第3行开始第n行中第一个偶数出现的位置以{2,3,2,4}循环
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n=in.nextInt();
        int res=-1;
        int[] index={4,2,3,2};
        if(n>2){
            res=index[(n-2)%4];
        }
        System.out.println(res);
    }
}

发表于 2025-04-04 20:10:19 回复(0)

Java

故事与你love

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) { 
            //生成变形杨辉三角二维数组
            int row = in.nextInt();
            int column = 2 * row - 1;
            int[][] arrays = new int[row][column];
            arrays[1-1][row-1] = 1;//第一行最中间的元素赋值1
            for (int i = 1;i<row; i++){
                for(int j = 0;j < column; j++){
                    if(j-1 >=0 && j+1<column){ 
                        arrays[i][j] =arrays[i-1][j-1] + arrays[i-1][j] + arrays[i-1][j+1];}
                    if(j-1 < 0){
                        arrays[i][j] = 0 + arrays[i-1][j] + arrays[i-1][j+1];
                    }
                     if(j+1 >= column){
                        arrays[i][j] = arrays[i-1][j-1] + arrays[i-1][j] + 0;
                    }
                }
            }
            //最后一行，计算第一个偶数位置
            int count = 0;
            for(int k = 0; k < (column + 1)/2  ; k++){
                if (arrays[row-1][k] % 2 == 0){
                    System.out.println(k+1);//输出第一个偶数位置
                    break;
                }
                else{
                    count++;//没有找到则记数
                }
            }
            if(count == (column + 1)/2 ){
                System.out.println(-1);
            }
            
     
        }
    }
}

正常逻辑没问题，到10000时耗尽堆内存了，它奶奶的

发表于 2025-02-27 00:03:48 回复(0)

Java

那个渔

import java.util.Scanner;

//杨辉三角，会超时，用递归，咋整呢

public class Main {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

//row行，col列

int row = sc.nextInt();

int col = 2 * row - 1;

int[][] arr = new int[row][col];

//对第n行的数进行遍历

for (int i = 0; i < col; i++) {

int sum = getSum(arr, row - 1, i);

if (sum % 2 == 0) {

System.out.println(i + 1);

return;

}

System.out.println(-1);

}

//求二维数组第几行几列的值，递归

public static int getSum(int[][] arr, int row, int col) {

if (row == 0 && col == arr.length - 1) {

return 1;

}

//有上一行

if (row - 1 >= 0) {

//有左上角

if ( col - 1 >= 0) {

//有左上角有右上角

if (col + 1 < arr[0].length) {

return getSum(arr, row - 1, col - 1) + getSum(arr, row - 1, col) + getSum(arr,

row - 1, col + 1);

}

} else {

//没有左上角有右上角

if (col + 1 < arr[0].length) {

return getSum(arr, row - 1, col) + getSum(arr, row - 1, col + 1);

}

} else {

return 0;

}

return getSum(arr, row - 1, col - 1) + getSum(arr, row - 1, col) + getSum(arr,

row - 1, col + 1);

}

发表于 2025-02-03 17:08:43 回复(0)

Java

Sen🍓🍀

n=10000时二维数组OOM

找规律

发表于 2025-01-27 22:34:02 回复(0)

Java

认真的芝士在敲键盘

import java.util.Scanner;

// n 1 2 3 4 5 6 7 8 9 10 11 ……

//index -1 -1 2 3 2 4 2 3 2 4 2 ……

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

// 注意 hasNext 和 hasNextLine 的区别

while (in.hasNextInt()) { // 注意 while 处理多个 case

int a = in.nextInt();

if ( a <= 2) {// 1 2

System.out.println(-1);

} else if (a % 4 == 0) {// 4 8

System.out.println(3);

} else if (a % 4 == 1 || a % 4 == 3) { // 3 5 7 9 11

System.out.println(2);

} else if (a % 4 == 2) {// 6 10

System.out.println(4);

}

发表于 2024-09-12 15:51:13 回复(0)

Java

牛客499848474号

投机取巧

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int a = in.nextInt();

if(a <= 2){

System.out.println(-1);

}else if(a % 2 == 1){

System.out.println(2);

}else if(a % 4 == 0){

System.out.println(3);

}else{

System.out.println(4);

}

发表于 2024-08-21 11:35:24 回复(0)

Java

爱吃香菜的小确幸在投简历

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int row = in.nextInt();
        if (row == 1 || row == 2){
            System.out.println(-1);
        }else if ((row & 1) == 1){//奇数
            System.out.println(2);
        }else if ((row & 2) == 2){//偶数但不是4的倍数
            System.out.println(4);
        }else
            System.out.println(3);//4的倍数
    }
}

发表于 2024-07-07 11:24:59 回复(0)

Java

牛客76365361号

这可是简单题，都在找规律……

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int a = in.nextInt();
            if (a < 3) {
                System.out.println("-1");
                return;
            }
            if((a & 1) == 1) {
                System.out.println("2");
                return;
            }
            if((a & 2) == 2) {
                System.out.println("4");
                return;
            }
            System.out.println("3");
            return;
        }
    }
}

发表于 2024-06-29 12:02:58 回复(0)

Java

牛客625422543号

尝试过两轮无果：

1、构造n行的二维数组存储，但那个10000行的用例会OOM。

2、递归表达(i,j)位置的数，只求第n行的每个数，找到偶数为止。但因为方法递归到底还是等于在栈空间中构造了一遍完整的三角，要么超时要么栈溢出。

3、换个思路，题目只关心是不是偶数，又没说要求算出来，于是找规律，3分钟找到了... O(1)算法秒杀。

发表于 2024-06-17 11:28:06 回复(0)

Java

fake_lok666

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

// 注意 hasNext 和 hasNextLine 的区别

int length = in.nextInt();

if(length<=2){

System.out.println("-1");

}else if(length%2 == 1){

System.out.println("2");

}else{

if((length/2)%2==0){

System.out.println("3");

}else{

System.out.println("4");

}

发表于 2024-06-04 10:15:15 回复(0)

Java

无梦0

可以跑通用例，但其实并不符合要求。暴力破解的，虽然没有oom，有个异常值是手动推导的：

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int len = in.nextInt();
        if (len > 2 && len % 2 == 1) {
            System.out.println(2) ;
            return;
        }
        if (len > 500) {
            System.out.println(3) ;
            return;
        }

        int[] old = new int[1];
        int[] ne = new int[1];
        ne[0] = 1;
        //组织树
        for (int i = 2; i <= len; i++) {
            old = ne;
            ne = new int[i * 2 - 1];
            for (int j = 0; j < ne.length; j++) {
                int s1 = j - 2;
                int s2 = j - 1;
                int s3 = j;
                int sum = 0;
                if (s1 >= 0 && s1 <= old.length - 1) {
                    sum = sum + old[s1];
                }
                if (s2 >= 0 && s2 <= old.length - 1) {
                    sum = sum + old[s2];
                }
                if (s3 >= 0 && s3 <= old.length - 1) {
                    sum = sum + old[s3];
                }
                if (i > 0) {
                    // System.out.print(sum + " ") ;
                }

                ne[j] = sum;
            }
            if (i > 0) {
                // System.out.println("") ;
            }

        }

        for (int i = 0; i < ne.length; i++) {
            if (ne[i] % 2 == 0) {
                System.out.println(i + 1) ;
                return;
            }
        }
        System.out.println(-1) ;
    }


}

编辑于 2024-04-08 15:02:58 回复(0)

Java

黑客永不服输

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

// 注意 hasNext 和 hasNextLine 的区别

while (in.hasNextInt()) { // 注意 while 处理多个 case

int a = in.nextInt();

int[] wb = function(a);

boolean find = false;

for (int i = 0; i < wb.length; i++) {

if (wb[i] % 2 == 0) {

System.out.println(i + 1);

find = true;

break;

}

if (find == false) {

System.out.println(-1);

}

private static int[] function(int a) {

if (a == 1) {

return new int[]{1};

} else if (a == 2) {

return new int[]{1, 1};

}

else if(a==3){

return new int[]{1,2,3};

}else {

int t = (2 * a - 1) / 2 + 1;

int[] res = new int[t];

int[] arr = function(a - 1);

for (int i = 0; i < res.length; i++) {

if (i == 0) {

res[i] = 1;

} else if (i == 1) {

res[i] = arr[0] + arr[1];

} else if (i == res.length-1) {

res[i] = arr[i - 2] * 2 + arr[i - 1];

} else {

res[i] = arr[i - 2] + arr[i - 1] + arr[i];

}

return res;

}

}我本地编译没问题，但是为什么在OJ系统里面说我OutOfMemoryError: Java heap space了

编辑于 2024-03-29 13:56:14 回复(0)

Java

牛客700990974号

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

// 注意 hasNext 和 hasNextLine 的区别

while (in.hasNextInt()) { // 注意 while 处理多个 case

// 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

// 会超时

// int lineNum = in.nextInt();

// if (lineNum < 3) {

// System.out.println(-1);

// continue;

// }

// List<Integer> rowList = new ArrayList<Integer>();

// List<Integer> preRowList = new ArrayList<Integer>();

// preRowList.add(1);

// for (int row = 1; row < lineNum; row++) {

// rowList.add(1);

// for (int col = 1; col < row * 3 + 1; col++) {

// int num = 0;

// num += col - 2 >= 0 && col - 2 < preRowList.size() ? preRowList.get(col - 2) :0;

// num += col - 1 >= 0 && col - 1 < preRowList.size() ? preRowList.get(col - 1) :0;

// num += col >= 0 && col < preRowList.size() ? preRowList.get(col) :0;

// rowList.add(col, num);

// if (row == lineNum - 1 && (num & 1) == 0) {

// System.out.println(col + 1);

// break;

// }

// preRowList = rowList;

// rowList = new ArrayList<>();

// }

// 找规律

// 1 2 3 4 5 6 7 8 9 10 11 12

// -1 -1 2 3 2 4 2 3 2 4 2 3

int lineNum = in.nextInt();

if (lineNum < 3) {

System.out.println(-1);

continue;

}

if ((lineNum & 1) == 1) // 奇数

System.out.println(2);

else if (lineNum % 4 == 0) // 4的倍数

System.out.println(3);

else

System.out.println(4); // 偶数但不是4的倍数

}

发表于 2023-12-11 14:40:04 回复(0)

Java

徐墨耀

就是一个找规律的题目，如果模仿杨辉三角就是会导致运行时间超出限制。

下面这段代码是模拟杨辉三角，然后去寻找偶数，但是测试用例10000会超时。

import java.util.ArrayList;
import java.util.Scanner;

public class T53 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int n = sc.nextInt();
            if (n <= 2) {
                System.out.println("-1");
                return;
            }
            if (n % 2 != 0) {
                System.out.println("2");
                return;
            }
            int flag = 3;
            ArrayList<Integer> reference = new ArrayList<>();
            reference.add(1);
            reference.add(2);
            reference.add(3);
            reference.add(2);
            reference.add(1);
            while (true) {
                ArrayList<Integer> current = new ArrayList<>();
                int length = 2 * (flag+1) - 1;
                //对当前行数据生成
                for (int i = 1; i <= length; i++) {
                    if (i == 1 || i == length) {
                        current.add(1);
                        continue;
                    }
                    if (i == 2) {
                        current.add(reference.get(0) + reference.get(1));
                        continue;
                    }
                    if (i == length - 1) {
                        current.add(reference.get(reference.size() - 1) + reference.get(reference.size() - 2));
                        continue;
                    }
                    current.add(reference.get(i - 3) + reference.get(i - 2) + reference.get(i - 1));
                }
                reference = current;
                flag++;
                if (flag == n) {
                    break;
                }
            }
            for (int i = 0; i < reference.size(); i++) {
                if (reference.get(i) % 2 == 0) {
                    System.out.println(i + 1);
                    return;
                }
            }
        }

    }
}

发表于 2023-11-29 14:59:44 回复(0)

Java

Kili_66

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int [] m = {2, 3, 2, 4};
        System.out.println(n >= 3 ? m[(n - 3) % 4] : -1);
    }
}

发表于 2023-11-25 15:21:06 回复(1)

Java

Fox_man

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {

//方法1；直接开辟二维数组进行赋值遍历，超内存且超时

public static int solve(int n){

int m = 2*n-1;

int[][] arr = new int[n][m];

//初始化第一层(因为int型默认值为0，所以为赋值的地方就为0)

arr[0][m/2] = 1;

int left=0;

int right=0;

int up=0;

//开始遍历

for(int i=1;i<n;i++){

for(int j=0;j<m;j++){

if(j-1 >= 0){

left = arr[i-1][j-1];

}

if(j+1<m){

right = arr[i-1][j+1];

}

up = arr[i-1][j];

arr[i][j] = left+up+right;

}

left = up = right = 0;

}

for(int j=0;j<m;j++){

if(arr[n-1][j]%2==0)

return j+1;

}

return -1;

}

//方法2：开辟两个一维数组，交替遍历赋值，不超内存，但超时

public static int solve2(int n){

int m = 2*n-1;

int[] pre = new int[m];

int[] now = new int[m];

int[] tmp;

//初始化第一层

pre[m/2] = 1;

int left=0;

int right=0;

int up=0;

//开始循环赋值，

for(int i=1;i<n;i++){

for(int j=0;j<m;j++){

if(j-1>=0){

left = pre[j-1];

}

if(j+1<m){

right = pre[j+1];

}

up = pre[j];

now[j] = left+up+right;

}

left = up = right = 0;

//交换上下层

tmp = now;

now = pre;

pre = tmp;

}

//最后一层遍历赋值之后，由于交换了引用，最后一层其实在pre上

for(int j=0;j<m;j++){

if(pre[j]%2==0)

return j+1;

}

return -1;

}

//方法3：寻找规律，可以发现，从第3行开始，偶数出现的位置依次为 2,3,2,4

//且这个规律呈现周期性，即从第7行开始，偶数出现的位置也依次是：2，3，2，4，故可以直接计算

public static int solve3(int n){

if(n==1 || n==2){

return -1;

}

if(n%4==3 || n%4==1){

return 2;

}

if(n%4==0){

return 3;

}

if(n%4==2){

return 4;

}

return -1;

}

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

// 注意 hasNext 和 hasNextLine 的区别

while (in.hasNextInt()) { // 注意 while 处理多个 case

int n = in.nextInt();

System.out.println(solve3(n));

}

发表于 2023-03-05 14:33:06 回复(0)

Java

zzloveyou

这种解*** n = 10000时会导致OOM 如何优化？

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int N = in.nextInt();
            int[][] dp = new int[N + 1][2 * N];
            dp[1][1] = 1;
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= 2 * N - 1; j++) {
                    for (int k = j - 2; k <= j; k++) {
                        if (k < 1 || k > (2 * (i - 1) - 1)) {
                            continue;
                        }
                        dp[i][j] += dp[i - 1][k]; 
                    }
                }
            }
            int ans = -1;
            for (int m = 1; m <= 2 * N - 1; m++) {
                if (dp[N][m] % 2 == 0) {
                    ans = m;
                    break;
                }
            }
            System.out.println(ans);
        }
    }
}

发表于 2023-02-05 01:53:48 回复(4)

Java

、前

oom了，不按出题人想的找规律就不行，感觉构建完整的杨辉三角难度大些

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();
        int[][] arrray = new int[n][2*n-1];
        for(int i=0;i<n;i++){
            arrray[i][0] = 1;
        }
        for(int i = 1;i<n;i++){
            for(int j=1;j<(2*(i+1)-1);j++){
                if(j==1){
                    arrray[i][j]=0+1+arrray[i-1][j];
                }else if(j>=2){
                    arrray[i][j]=arrray[i-1][j-2]+arrray[i-1][j-1]+arrray[i-1][j];
                }
                
            }
        }
        int flag = -1;
        for(int i = 0;i<2*n-1;i++){
            if(arrray[n-1][i]%2==0){
                flag=i+1;
                break;
            }
        }
        System.out.print(flag);

    }


}


// 1 
// 1 1 1
// 1 2 3 2 1
// 1 3 6 7 6 3 1


// a[i][j]=a[i-1][j-2]+a[i-1][j-1]+a[i-1][j]
// 2n-1

发表于 2023-01-07 21:14:28 回复(2)

Java

UnYee

/*其实就是个找规律题*/

import java.util.Scanner;

public class Main {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n=sc.nextInt();
if(n>=3){
if((n-1)%2==0){
System.out.print("2");
}else{
if(n%4==0){
System.out.print("3");
}else{
System.out.print("4");
}
}
}else{
System.out.print("-1");
}
}
}

发表于 2022-08-30 16:39:03 回复(0)

提交观点

问题信息

基础数学

难度：

52条回答 2012收藏 33904浏览

通过挑战的用户

查看代码

帅阿衰

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

杨辉三角的变形

输入描述:

输出描述:

输入

输出

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题