首页 > 试题广场 >

杨辉三角的变形

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

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

以上三角形的数阵，第一行只有一个数1，以下每行的每个数，是恰好是它上面的数、左上角数和右上角的数，3个数之和（如果不存在某个数，认为该数就是0）。

求第n行第一个偶数出现的位置。如果没有偶数，则输出-1。例如输入3,则输出2，输入4则输出3，输入2则输出-1。

数据范围： $1 \le n \le 10^9 \$

输入描述:

输入一个int整数

输出描述:

输出返回的int值

示例1

输入

输出

算法知识视频讲解

Python3

牛客714862239号

开始写了俩循环到10000的时候就爆掉了，然后观察每个都是2，4，2，3交替出现的，所以直接ifprint

import sys

num = int(input().strip())

if num == 1:

print("-1")

elif num ==2:

print(-1)

elif num%4 ==1:

print(2)

elif num%4 ==2:

print(4)

elif num%4 ==3:

print(2)

elif num%4 ==0:

print(3)

之前是这样写的

#import sys

#num = int(input().strip())

# first1 = [1]

# def deal(list1):

# listNew = []

# for i in range(len(list1)+1):

# if i == 0:

# listNew.append(1)

# elif i == len(list1):

# listNew.append(list1[i-2]*2 +list1[i-1])

# elif i ==1:

# listNew.append(list1[i-1] +list1[i])

# else:

# listNew.append(list1[i-2]+list1[i-1]+list1[i])

# return listNew

# for i in range(num-1):

# first1 = deal(first1)

# index = 0

# for i in first1:

# index += 1

# if i%2==0:

# break

# elif index == len(first1):

# index = 0

# break

# if index !=0:

# print(index)

# else:

# print('-1')

编辑于 2024-04-24 19:48:46 回复(0)

Python3

牛客781494221号

num = int(input())
# 找规律：可以发现偶数出现在每一行的第几位为 2 4 2 3 
# 这就成了周期问题
result = [2, 4, 2, 3]
if num >= 3:
    print(result[num % 4 - 1])
else:
    print(-1)

发表于 2023-10-31 20:33:55 回复(1)

Python3

RionaZhang

import sys

def triangle(row):
    n = row

    if n <= 2:
        print(-1)
    
    else:
        if n%2 != 0: #odd
            print(2)

        elif n%2 == 0 and n%4 == 0:
            print(3)
            
        else:
            print(4)
            
    return

triangle(int(input()))

发表于 2023-10-30 23:35:24 回复(0)

Python3

牛客478833509号

N = int(input())
if N <= 2:
    print(-1)
else:
    if N % 2 == 0 and N % 4 == 0:
        print(3)
    elif N % 2 == 1:
        print(2)
    else:
        print(4)

发表于 2023-09-18 13:29:46 回复(0)

Python3

牛客561675659号

j结果：内存超限。您的程序使用了超过限制的内存。代码是正确的

import sys

for line in sys.stdin:

#1、将三角形数阵看作是一个N*(2N-1)的矩阵，空的位置用0填充

#2、输入的数是矩阵的行数，可以得到每行的元素个数为2N-1个

#3、第一行只有中间位置的那个数为：1

#4、从第二行开始，计算每个位置的元素是多少。list[i][j]=list[i-1][j-1]+list[i-1][j]l+ist[i-1][j+1]

#如果j-1<0,越界list[i-1][j-1]=0;同理j+1>2n-2,右边越界list[i-1][j+1]=0

a = line.strip()

n=int(a)

list1=[[0 for _ in range(2*n-1)] for _ in range(n)]

ind=(2*n-1)//2

list1[0][ind]=1

for i in range(1,n):#确定行

#确定列

for j in range(2*n-1):

if j-1<0:

list1[i-1][j-1]=0

if (j+1)>=2*n-1:

list1[i][j]=list1[i-1][j-1]+list1[i-1][j]

if(j+1)<2*n-1:

list1[i][j]=list1[i-1][j-1]+list1[i-1][j]+list1[i-1][j+1]

#输出

flag=1

for kk in list1[n-1]:

if kk%2==0:

flag=0

print(list1[n-1].index(kk)+1)

break

if flag :print(-1)

#print(list1)

发表于 2023-08-30 14:27:49 回复(0)

Python3

韩不信

n = int(input())
#奇数行永远是第二位偶数位，偶数行（4、8... 为第三位） （6、10...为第四位） 即偶数行为第3位，奇数行为第4位
if(n <= 2):
    print(-1)
else:
    if(n%2 == 1):
        print(2)
    elif((n // 2) % 2 == 1):
        print(4)
    else:
        print(3)

发表于 2023-06-27 15:16:10 回复(0)

Python3

牛客705621987号

a = int(input())

if a==1 or a==2:

print(-1)

else:

if a%2==1:

print("2")

elif a%4==0:

print("3")

else:

print("4")

发表于 2023-06-13 11:40:34 回复(0)

Python3

AlfredP

n=int(input().strip())
res=2 if n%2==1 else (3 if n%4==0 else 4)
if n<3:
    print(-1)
else:
    print(res)

发表于 2023-04-25 09:47:20 回复(0)

Python3

strongnine

# 看题目找规律:
# 第 5 行:             [1, 4, 10, 16, ...] 第 2 个
# 第 6 行:          [1, 5, 15, 30, ...] 第 4 个
# 第 7 行:       [1, 6, 21, ...] 第 2 个 
# 第 8 行:    [1, 7, 28, ...] 第 3 个
# 第 9 行: [1, 8, ...] 第 2 个
# ...
# 于是不同行的偶数出现的位置为:
#     [-1, -1, 2, 3, 2, 4, 2, ...]
# 我们大胆猜想, 从第 2 个开始: 
#        2, 3, 2, 4, 2, 3, 2, 4, ....
# 这样的顺序出现, 即:
#     1. 1 + 2 * n => 2; 
#     2. 4 * n => 3; 
#     3. 2 + 4 * n => 4;
# 这样的猜想是有道理的. 首先题目所给的数据范围是 [1, 10^9]
# 即便是使用 O(n) 的时间复杂度, 也肯定会超时, 
# 而看起来这题目又没有二分的方法去做, 所以肯定是找规律. 
# 代码如下:
def solution(x: int) -> int:
    if x < 3: return -1
    if x % 2 == 1: return 2
    if x % 4 == 0: return 3
    if x % 4 == 2: return 4

if __name__ == "__main__":
    n = int(input().strip())
    print(solution(n))

发表于 2023-04-06 22:51:56 回复(0)

Python3

华黑子

def yung(n: int):
    if n == 1:
        return [[1]]
    else:
        y = [[0] * (2 * n - 1)] * n
        y[0][n-1]=1
        for i in range(1,n):
            y[i][n - i - 1], y[i][i - n] = 1, 1
            for j in range(n - i, n + i - 1):
                y[i][j] = y[i - 1][j - 1] + y[i - 1][j] + y[i - 1][j + 1]
        return y

我这个生成杨辉三角的函数为什么结果不对呢，有没有大佬帮看下

发表于 2023-04-06 11:06:46 回复(1)

Python3

牛客739829953号

n = int(input())

if n <= 2:

s = -1

else:

if n % 2 == 1:

s = 2

elif n % 2 == 0:

if (n // 2) % 2 == 0:

s = 3

elif (n // 2) % 2 == 1:

s = 4

print(s)

发表于 2023-03-31 11:55:31 回复(0)

Python3

夜微凉轻悲伤

# 找规律

row = int(input())

if row == 1 or row == 2:

print(-1)

if row>=3:

if row-3 == 0 or (row-3)%4 == 0:

print(2)

elif row-4 == 0 or (row-4)%4 == 0:

print(3)

if row-5 == 0 or (row-5)%4 == 0:

print(2)

if row-3 == 0 or (row-6)%4 == 0:

print(4)

发表于 2023-03-28 19:20:35 回复(0)

Python3

再多看一眼就会爆炸

纯纯找规律。。。

#-1 -1 2 3 2 4 2 3 2 4
a=int(input())
if a <=2:
    print(-1)
else:
    if (a-2)%4 == 1&nbs***bsp;(a-2)%4 == 3:
        print(2)
    if (a-2)%4 == 2:
        print(3)
    if (a-2)%4 == 0:
        print(4)

发表于 2023-03-08 06:56:17 回复(0)

Python3

牛客368065820号

n = int(input())
print(-1 if n <= 2 else [2, 3, 2, 4][(n - 3) % 4])

发表于 2023-02-03 21:08:01 回复(1)

Python3

想转码的机械师

#dp一本正经的（傻不拉几的）写了杨辉三角改版，输入10000报错，因为内存超了没办法。一看评论变成找规律题（脑经急转弯）！

#新手就当学习了哈哈哈

a=int(input())

dp=[[0 for i in range(2*a+1)] for i in range(a)]

for i in range(a):

if i==0:

dp[i][a]=1

else:

for j in range(1,2*a):

dp[i][j]=dp[i-1][j-1]+dp[i-1][j]+dp[i-1][j+1]

for i in range(1,2*a):

m=dp[a-1][i]

if m%2==0:

n=i

break

else:

n=-1

print(n)

发表于 2023-01-20 01:09:48 回复(0)

Python3

Knorth-小柯北

找规律，因为第一个数字永远是1，奇数行第二个永远是偶数，然后再看偶书行的第一个偶数在哪里；

这里用1代表奇数0代表偶数花了10行的图，发现0要么出现在3的位置要么出现在4的位置，4行一组循环出现，有规律；

n = int(input())

if n == 1&nbs***bsp;n == 2 :
    print(-1)
elif n % 2 == 1 :
    print(2)
else :
    if (n-2)%4 == 0 :
        print(4)
    else :
        print(3)

发表于 2022-09-29 08:48:55 回复(0)

Python3

秦***121

笨办法把第n列算出来依然不能通过所有示例，看了一下好像当n=10000就输出不了

def fun(n):

lst=[]

if n==1:

return [1]

else:

lst1=[0]+[0]+fun(n-1)+[0]+[0]

for i in range(len(lst1)-2):

lst+=[lst1[i]+lst1[i+1]+lst1[i+2]]

return lst

while True:

try:

n=int(input())

num=0

for i in fun(n):

if i%2==0:

print(fun(n).index(i)+1)

break

else:

num+=1

if num==len(fun(n)):

print(-1)

except:

break

发表于 2022-09-16 20:33:41 回复(2)

Python3

Andy锅锅

刚开始浪费了大量时间在找数之间的关系，看了评论区才恍然大悟，还是经验不足啊

while True:
    try:
        n = int(input())
        s = [2, 3, 2, 4] # 第一个偶数出现的位置循环，用列表s存储起来
        if n <= 2:
            print(-1) # 排除特殊情况
        else:
            i = (n-2) % 4
            print(s[i-1]) # 注意列表索引从0开始
    except:
        break

发表于 2022-09-13 20:29:11 回复(0)