首页 > 试题广场 >

杨辉三角的变形

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

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

牛客523572873号

本想用递归算出第k行，发现超时了，涉及奇偶还得是要找规律

# import sys
# sys.setrecursionlimit(100000) #这里设置为十万 
# def func(n):
#     if n == 1:
#         return [1]
#     elif n == 2:
#         return [1,1,1]
#     else:
#         tmp = [0] + func(n-1) + [0]
#         res = []
#         for i in range(n-1):
#             res.append(sum(tmp[i:i+3]))
#         return [1] + res + res[:-1][::-1] + [1]

# li = func(int(input()))
# res = 0
# tag = -1
# for x in range(len(li)):
#     if li[x] % 2 == 0:
#         tag = 0
#         res = x + 1
#         break

# print(tag + res)




# 1 3 6 7   : J J O J  此时n=3
# 1 4 10 14 : J O O O
# 下一行：     J J J O
# 下一行：     J O J O
# 下一行：     J J O J   后续循环。。。

n = int(input())

def func(n):  # 这里n等于行数-1
    if n in [0, 1]:
        return -1
    elif n%2 == 0:
        return 2 
    else:
        return ((n-3)//2)%2 + 3
print(func(n-1))

发表于 2024-11-19 20:32:13 回复(0)

Python3

求实习的代码渣渣很贪吃

import sys

只问奇偶，奇数为1，偶数为0，三数相加的结果可列举，可以确定的是第n行前两个数为 1 n-1，所以奇偶确定，之后再按奇偶找规律即可

n=int(input())

if n==1 or n==2:

print(-1)

elif (n-1)%2==0:

print(2)

elif n%4==0:

print(3)

else:

print(4)

发表于 2024-09-15 18:31:22 回复(0)

Python3

等offer251

头铁死磕超时

n=int(input())
# n=3
li=[[1]]
for i in range(1,n):
    tmp=[0]+li[-1]+[0]
    letmp=li[-1]+[0,0]
    ritmp=[0,0]+li[-1]

    ro=[tmp[j]+letmp[j]+ritmp[j] for j in range(len(tmp))]
    li.append(ro)
# print(li[-1])
flag=-1
for i,v in enumerate(li[-1]):
    if v%2==0:
        flag=i+1
        break
print(flag) 
# print(li)

n=int(input())
# n=3
li=[1]

for i in range(1,n):
    tmp=[0]+li+[0]
    letmp=li+[0,0]
    ritmp=[0,0]+li

    li=[tmp[j]+letmp[j]+ritmp[j] for j in range(len(tmp))]
    # li.append(ro)
    # li=li[-2:]
# print(li[-1])
flag=-1
for i,v in enumerate(li):
    if v%2==0:
        flag=i+1
        break
print(flag) 
# print(li)

def genLi():
    li = [1]
    yield li
    pa = [0, 0]
    while True:
        li = pa + li + pa
        liNew = [li[i] + li[i+1] + li[i+2] for i in range(len(li) - 2)]
        li = liNew
        yield li
gen = genLi()
# n = 500
n=int(input())
for _ in range(n):
    resLi = next(gen)
flag=-1
for i,v in enumerate(resLi):
    if v%2==0:
        flag=i+1
        break
print(flag)

发表于 2024-06-16 11:20:31 回复(0)

Python3

野蛮的代码渣渣在写日记

遇到简单的题我重拳出击，2行代码解决

a = int(input())

print(-1 if a <= 3 else (2 if (a - 3) % 4 in (0, 2) else (3 if (a - 3) % 4 == 1 else 4)))

发表于 2024-05-10 16:37:57 回复(0)

Python3

J丶x

n = int(input())

# # 定义一个函数，求第n行，第k个数字：

# def num(n, k):

# if n == 1 and k == 1:

# return 1

# if k == 0 or k == -1 or k == -2:

# return 0

# if k > 2 * n - 1:

# return 0

# return num(n - 1, k - 2) + num(n - 1, k - 1) + num(n - 1, k)

# for k in range(1, 2 * n - 1, 1):

# if num(n, k) % 2 == 0:

# print("%d" % k)

# break

# else:

# print("-1")

"""

以上代码运行超时！

发现规律：

在每一行偶数出现位置为：

-1

……

【-1 -1】,【2 3 2 4】循环

"""

result_list = [2, 3, 2, 4]

if n == 1 or n == 2:

print("-1")

else:

n = n + 2

print("%d" % result_list[n % 4 - 1])

发表于 2024-05-03 16:28:18 回复(0)

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)

提交观点

问题信息

基础数学

难度：

35条回答 1889收藏 33184浏览

通过挑战的用户

查看代码

帅阿衰

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

杨辉三角的变形

输入描述:

输出描述:

输入

输出

头铁死磕超时

问题信息

热门推荐

通过挑战的用户

相关试题