首页 > 试题广场 >

杨辉三角的变形

[编程题]杨辉三角的变形
  • 热度指数：166169 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
\hspace{15pt}定义变形的杨辉三角规则：
\hspace{23pt}\bullet\,第一行为固定的整数 1；
\hspace{23pt}\bullet\,第二行开始，每行的数字数量均比上一行多两个，且中心对称（也可以看作是在上一行的基础上首尾增加了一个数字）；每个位置上的数字是它正上方、左上角和右上角这三个数之和（如果不存在某个数，认为该数就是 0）。
\hspace{15pt}下方展示了计算的过程：
\begin{bmatrix}<br />1<br />\end{bmatrix}<br />\to<br />\begin{bmatrix}<br />{\color{grey}0} & 1 & {\color{grey}0} \\<br />1 & 1 & 1<br />\end{bmatrix}<br />\to<br />\begin{bmatrix}<br />{\color{grey}0} & {\color{grey}0} & 1 & {\color{grey}0} & {\color{grey}0} \\<br />{\color{grey}0} & 1 & 1 & 1 & {\color{grey}0} \\<br />1 & 2 & 3 & 2 & 1<br />\end{bmatrix}<br />\to<br />\begin{bmatrix}<br />{\color{grey}0} & {\color{grey}0} & {\color{grey}0} & 1 & {\color{grey}0} & {\color{grey}0} & {\color{grey}0} \\<br />{\color{grey}0} & {\color{grey}0} & 1 & 1 & 1 & {\color{grey}0} & {\color{grey}0} \\<br />{\color{grey}0} & 1 & 2 & 3 & 2 & 1 & {\color{grey}0} \\<br />1 & 3 & 6 & 7 & 6 & 3 & 1<br />\end{bmatrix}

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

输入描述:
\hspace{15pt}输入一个整数 n \left(1 \leqq n \leqq 10^9\right) 代表询问的行数。


输出描述:
\hspace{15pt}输出一个整数，代表第 n 行中第一个偶数出现的位置。特别地如果第 n 行中没有偶数，则输出 -1。
示例1

输入

4

输出

3
示例2

输入

3

输出

2
示例3

输入

1

输出

-1
算法知识视频讲解
添加回答
Python 3
bry716头像 bry716 
while True:
    try:
        n = int(input())
        s = '2324'
        if n <= 2:
            print(-1)
        else:
            print(s[(n-3)%4]) 
    except:
        break

发表于 2024-06-04 23:35:38 回复(0)
Python 3
不愿透露身份的美凌格头像 不愿透露身份的美凌格
以后看见这种n级数列，输入的n还很大就别想着dp了，直接找规律玩阴的。
发表于 2023-09-21 18:15:32 回复(0)
Python 3
在思考的芒果很忙碌头像 在思考的芒果很忙碌
while True:
    try:
        x1 = int(input())
        y = -1
        if x1 >= 3:
            a_list = []
            for i in range(x1):
                if i == 0:
                    item_list = [1]
                    a_list.append(item_list)
                elif i == 1:
                    item_list = [1, 1, 1]
                    a_list.append(item_list)
                if (i >= 2):
                    item_count = 2 * i + 1
                    item = 1
                    item_list=[]
                    for j in range(item_count):
                        if j == 0:
                            item_list.append(item)
                        elif j == item_count - 1:
                            item = 1
                            item_list.append(item)
                        else:
                            pre_list = a_list[i - 1]
                            if j==1:
                                item = pre_list[j-1] + pre_list[j]
                            elif j == len(pre_list):
                                item = pre_list[j - 2] + pre_list[j-1]
                            else:
                                item = pre_list[j - 2] + pre_list[j-1] + pre_list[j]
                            item_list.append(item)  
                    a_list.append(item_list)
            target_list=a_list[x1-1]
            for a in range(len(target_list)):
                if target_list[a] % 2 == 0:
                    print(a+1)
                    break
        else:
            print(-1)

    except:
        break
我直接把列表取出来了，调试时输出是没有问题，但是提交的时候返回内存超限，请问怎么回事呢
发表于 2023-08-10 13:20:21 回复(0)
Python 3
牛客88686544号头像 牛客88686544号
超时
k = int(input())
m = [1, 1, 1]


def sumsang(m):
    m = [0, 0] + m + [0, 0]
    s = []
    for i in range(len(m) - 2):
        s.append(m[i] + m[i + 1] + m[i + 2])
    return s


def seiko(n):
    global m
    if n == 1 or n == 2:
        print(-1)
    else:
        l = []
        for i in range(2, n):
            k = sumsang(m)
            m = k
            l = m
        for i, var in enumerate(l):
            if var % 2 == 0:
                print(i + 1)
                break


seiko(k)

发表于 2022-08-28 21:16:04 回复(0)
Python 3
牛客181231997号头像 牛客181231997号
#还想傻乎乎的求第四个元素的公式，最后直接摆烂
n=int(input())
s2=n-1
s3=(n-1)*n/2
if n==1 or n==2:
    print(-1)
elif s2%2==0:
    print(2)
elif s3%2==0:
    print(3)
else:
    print(4)
发表于 2022-08-05 10:15:00 回复(0)
Python 3
Justinshadow头像 Justinshadow 
n = int(input())
ls = [3,2,4,2]
if n < 3:
    print(-1)
else:
    print(ls[n%4])

发表于 2022-08-04 00:52:44 回复(0)
Python 3
你猜猜看^^头像 你猜猜看^^
n = int(input())
if n < 3:
    print(-1)
elif (n+1)%4 ==0:
    print(2)
elif n%4 == 0:
    print(3)
elif n%4 ==1:
    print(2)
else:
    print(4)
发表于 2022-07-06 22:14:48 回复(0)
Python 3
dk斗志昂扬头像 dk斗志昂扬 
#这题目不找规律肯定要超内存了
N = int(input())
if N < 3:
    print(-1)
elif N % 2 == 1:
    print(2)
elif N % 4 == 0:
    print(3)
else:
    print(4)

发表于 2022-07-01 04:08:44 回复(0)
Python 3
紫依依依依依头像 紫依依依依依
#内存超限制的笨方法
n = int(input())
list1 = [[0]*n for i in range(1,n+1)]
for i in range(n):
    list1[i][n-i-1] = 1
for i in range(1,n):
    list1[i][n-i] = i
    
for i in range(2,n+1):
    list1[i-1][-1] = list1[i-2][-1] + 2*(list1[i-2][-2])
    for j in range(1,n-1):
        list1[i-1][j] = list1[i-2][j] + list1[i-2][j-1] + list1[i-2][j+1]

even_num = []
for k in list1[-1]:
    if k % 2 == 0:
        even_num.append(k)
        
try:
    a = list1[-1].index(even_num[0])
    print(a+1)
except:
    print(-1)


发表于 2022-06-23 14:46:06 回复(0)
Python 3
呆吖呆yu头像 呆吖呆yu
找规律，发现除了1，2没有偶数，每隔四行首个偶数的索引是一样的，[2,3,2,4]，然后进行处理。 
def test2():
    arr = [2, 3, 2, 4]
    n = int(input())
    num = (n - 2) % 4
    if n == 1&nbs***bsp;n == 2:
        print(-1)
    else:
        print(arr[num - 1])


if __name__ == '__main__':
    test2()


发表于 2022-05-28 16:32:31 回复(0)
Python 3
牛客644087385号头像 牛客644087385号
这道题还是非常不错的，高中毕业以后就很久没有再去做这种找规律的题目了。

``` python
x = int(input())

if x <= 2:
    print(-1)
elif x % 2 == 1:
    print(2)
elif x % 4 == 0:
    print(3)
else:
    print(4)


```
发表于 2022-05-24 13:55:05 回复(0)
Python 3
牛客190952643号头像 牛客190952643号
每一道都是一个数量关系题
发表于 2022-05-13 16:38:53 回复(0)
Python 3
黄201909250935611头像 黄201909250935611
杨辉三角的打印 
a=int(input())
list1=['1']
list2=[] print(''.join(list1)) for k in range(1,a):
    str0=''.join(list1)
    list1.clear()
    str1=str0.center(len(str0)+4,'0') for i in range(len(str1)):
        list2.append(str(int(str1[i])+int(str1[i+1])+int(str1[i+2])))
        list1.append(str(int(str1[i])+int(str1[i+1])+int(str1[i+2]))) if i +2==len(str1)-1: break  str2=' '.join(list2) print(str2)
    list2.clear()

发表于 2022-04-10 11:27:52 回复(0)
Python 3
牛客919221453号头像 牛客919221453号
a=int(input())
lis=[[0 for i in range(2*(a+1)-1)] for j in range(a)]
z=int((2*(a+1)-2)/2)
lis[0][z]=1
if a<3:
    print('-1')
else:
    for i in range(1,a):
        for j in range(z-i,z+i+1):
            lis[i][j]=lis[i-1][j-1]+lis[i-1][j+1]+lis[i-1][j]
    for i in range(len(lis[a-1])):
        if lis[a-1][i]%2==0 and lis[a-1][i]!=0:
            print(i)
            break
    # import sys
# alt=[2,3,2,4] #发现规律，从第三行开始2324循环
# for line in sys.stdin:
#     n=int(line.strip())
#     if n<3:
#         print(-1)
#     if n>=3:  
#         print(alt[(n-3)%4]) #所以对4求余，映射到上面alt列表中
        

发表于 2022-04-03 23:26:02 回复(0)
Python 3
阿达新头像 阿达新 
#!/usr/bin/python

while True:
    try:
        num = int(input())
        k = []
        for i in range(num):
            k.append([])
            for j in range(num*2-1):
                k[i].append([])
                k[i][j] = 0
        k[0][0] = 1
        flag = -1
        for i in range(1,num):
            for j in range(2*i+1):
                k[i][j] = k[i-1][j-1]+ k[i-1][j] +k[i-1][j-2]
                if k[i][j]%2==0 and i == num-1:
                    flag = j+1
                    break
                else:
                    flag = -1
        print(flag)
    except:
        break
#跑了一下会超时，只有投机取巧了。。。。

发表于 2022-04-01 23:31:58 回复(0)
Python 3
#一块钱#头像 #一块钱#
就是这么离谱，刚开始用动态规划写，占用空间过大；优化后，超时，万万没想到是找规律的题。
n = int(input())
if n == 1&nbs***bsp;n == 2:
    print(-1)
elif n%2 == 0:
    if n % 4 ==0:
        print(3)
    else:
        print(4)
else:
    print(2)

发表于 2022-03-23 19:38:16 回复(0)
提交观点

问题信息

基础数学
难度：
43条回答 33542浏览

热门推荐

通过挑战的用户

查看代码

相关试题

杨辉三角的变形

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号