首页 > 试题广场 >

杨辉三角的变形

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

热度指数：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

输入

输出

算法知识视频讲解

Python

丶濑尾结弦

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

发表于 2021-06-02 13:29:39 回复(0)

Python

三三不得酒吖

while True:
    try:
        a = int(input())
        l_0 = [[0 for i in range(2 * a - 1)] for i in range(a)]
        l_0[0][0] = 1
        for i in range(1,a):
            for j in range(len(l_0[0])):
                l_0[i][j] = l_0[i-1][j-2] + l_0[i-1][j-1] + l_0[i-1][j]
        for k in l_0[a-1]:
            if k % 2 == 0:
                print(l_0[a-1].index(k) + 1)
                break
        else:
            print('-1')
    except:
        break

暴力破解

发表于 2021-05-25 23:17:53 回复(0)

Python

牛客诶谁

import sys

# 计算第n列的数字，返回其数组
def func(n):
    # 初始化
    arr = [0 for i in range(2*n-1)]
    arr[n-1] = 1
    for i in range(n-1):
        # 临时存储，用于保存第j次的每项结果
        tmp_arr = [0]*(2*n-1)
        for j in range(2*n-1):
            # 第一个元素
            if j == 0:
                tmp_arr[j] = arr[j] + arr[j+1]
            # 最后一个元素
            elif j == 2*n-2:
                tmp_arr[j] = arr[j-1] + arr[j]
            # 中间元素
            else:
                tmp_arr[j] = arr[j-1] + arr[j] + arr[j+1]
        # 将第i次遍历的数据存入数组
        arr = tmp_arr
    return arr


# 找到第一个偶数
def func2(arr):
    for i in range(len(arr)):
        if arr[i] % 2 == 0:
            return i+1
    return -1

for line in sys.stdin:
    num = int(line.strip())
    print(func2(func(num)))

编辑于 2021-05-01 09:50:53 回复(0)

Python

*超凡

while True:
try:
a = int(input())
A = [[1]]*a
for i in range(1,a):
B = [1]
if i == 1:
A[i] = [1,1,1]
else:
for j in range(1, 2*i+1):
if j == 1:
B.append(int(A[i-1][j-1] + A[i-1][j]))
elif 1 < j < 2*i-1:
B.append(int(A[i-1][j-2] + A[i-1][j-1] + A[i-1][j]))
elif j == 2*i-1:
B.append(int(A[i-1][j-2] + A[i-1][j-1]))
else:
B.append(1)
A[i] = B
count = 0
for i in range(len(A[a-1])):
if A[a-1][i]%2 == 0:
print(i+1)
break
else:
count += 1
if count == len(A[a-1]):
print(-1)
except:
break

发表于 2021-04-23 18:49:53 回复(0)

Python

牛客172791552号

python硬编，有点儿顶

while True:

try:

n=int(input())

#判断-1输出情况

if n<3:
print(-1)

else:

#创建二维列表行为n，列为2n+1（比最大列多两行，防止数组越界），方便用前一行计算出后一行

m=2*n+1
a = [[0 for j in range(0,m)] for i in range(0,n)]

#初始化第一行数据

a[0][n]= 1

#循环计算其他数据

for i in range(1,n):

for j in range(n-i,m-1):

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

#判断最后一行的都一次出现的偶数，输出位置

if i==(n-1):
if a[i][j]%2==0:
print(j)
break
except:
break

编辑于 2021-04-23 00:03:46 回复(0)

Python

胜者万里也称王

while True:
try:
a=int(input())
if a<=2:
b=-1
elif a%2==1:
b=2
elif a%4==0:
b=3
else:
b=4
print(b)
except:

break

#通过判断奇偶性（2-6行），得出周期为4

发表于 2021-03-27 14:42:39 回复(0)

Python

天君添桢

while True:
try:
n = int(input().strip())
if n < 3:
print('-1')
continue
dst_matrix = [[0] * (2 * n + 1) for _ in range(n)]
for i in range(n):
dst_matrix[i][0] = 0
dst_matrix[i][1] = 1
dst_matrix[i][-1] = 0
dst_matrix[1][2] = 1
dst_matrix[1][3] = 1
for i in range(2, n):
for j in range(2, 5):
dst_matrix[i][j] = dst_matrix[i - 1][j - 2] + dst_matrix[i - 1][j - 1] + dst_matrix[i - 1][j]
for k, value in enumerate(dst_matrix[-1][2:]):
if value % 2 == 0:
print(k + 2)
break
except:
break

发表于 2021-03-23 20:36:02 回复(0)

Python

Philip25

找规律：偶数为0，奇数为1，下一行的第k个元素等于上一行的第k，k-1，k-2三个元素和

rule=[3,2,4,2]# index = 除以4的余数，元素 = 第index行第一个偶数的位置
while True:
    try:
        n=int(input())
        if n<3:%前两行特例
            print(-1)
        else:
            i=n%4
            print(rule[i]) 
    except:
        break

编辑于 2021-03-17 05:37:43 回复(0)

Python

牛客486777764号

我是笨办法先把第N行数据先算出来，再找偶数。

def num(n):
    if n == 1:
        return 1
    else:
        return num(n-1) + 2

def tria(L,cen):
    n = 3
    while n<=cen:
        number = num(n)
        for i in range(1,number-2):
            if i == 1:
                L.append([])
                L[-1].append(1)
                L[-1].append(n-1)
                L[-1].append(n-1)
                L[-1].append(1)
            else:
                L[-1].insert(i,L[-2][i]+L[-2][i-1]+L[-2][i-2])
        n = n + 1

while True:
    L = [[1], [1, 1, 1]]
    list_1 = []
    try:
        cen = int(input())
        tria(L,cen)
        for j in L[cen-1]:
            list_1.append(j%2)
        if 0 not in list_1:
            print(-1)
        else:
            print(list_1.index(0) + 1)
    except:
        break

编辑于 2021-01-31 14:35:56 回复(0)

Python

JohnnyXia

def first_even(n):
    if n<=2:
        return -1
    else:
        n = (n-3)%4
        return [2,3,2,4][n]
while True:
    try:
        n = int(input())
        print(first_even(n))
    except:
        break

for first two line, there is even number;

after that, every four lines are a recycle with [2,3,2,4];

编辑于 2021-01-20 17:03:07 回复(0)

Python

UNIMel-Kent

#规律就是2324，往下写几行就明白了。

while True:

try:
n = int(input())
if n == 1 or n==2:
print('-1')
elif n%2 != 0:
print('2')
elif n%4 ==0:
print('3')
else:
print('4')
except:
break

发表于 2021-01-19 16:17:25 回复(0)

Python

大溪地渔民

# 找重复的规律，关注前四个数即可，1 表示奇数 0 表示偶数，从第三行开始，前四个数分别是
# 1 0 1 0
# 1 1 0 1
# 1 0 0 0
# 1 1 1 0


repeat = [2, 3, 2, 4]

while True:
    try:
        n = int(input())
        print(-1) if n < 3 else print(repeat[n%4-3])
    except:
        break

发表于 2020-12-21 14:17:19 回复(0)

Python

玉鱼

python暴力解法：

while True:
    try:
        n = int(input())
        if n <= 2:
            print(-1)
        else:
            prev = []
            curr = [1, 1, 1]
            for i in range(2, n):
                prev = curr
                temp = []
                for j in range(len(prev)-2):
                    temp.append((prev[j]+prev[j+1]+prev[j+2])%2)
                curr = [1] + [(prev[0]+prev[1])%2] + temp + [(prev[-2]+prev[-1])%2] + [1]
            flag = 1
            for i in range(len(curr)):
                if curr[i] == 0:
                    print(i+1)
                    flag = 0
                    break
        if flag == 1:
            print(-1)
    except:
        break

发表于 2020-12-04 11:02:31 回复(0)

Python

乐观的lishan

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

数阵特点：
每一行每个数都是上面三个数之和，例如第4行第4个数为7，
上面三个数分别为2,3,2，其和刚好为7

问：第n行第1个偶数出现的位置，不存在偶数，则输出为-1

简要分析：
因只考察奇、偶，可用1代表奇，0代表偶，又因数阵为对称图形，
只观察左半第一个为0的位置即可

                           1
                        1  1
                     1  0  1   开头为1010（第2位出现偶数）
                  1  1  0  1   开头为1101（第3位出现偶数）
               1  0  0  0  1   开头为1000（第2位出现偶数）
            1  1  1  0  1  1   开头为1110（第4位出现偶数）
         1  0  1  0  0  0  1   开头为1010（重复）
      1  1  0  1  1  0  1  1   开头为1101（重复）

第3到n行输出为"2324"....,以4为周期的重复
'''
# 解法1：找规律法（运行时间14ms）
# while True:
#     try:
#         n = int(input())
#         if n <= 2:
#             print(-1)
#         else:
#             remain = (n-2) % 4    
#             if remain == 1:
#                 print(2)
#             elif remain == 2:
#                 print(3)
#             elif remain == 3:
#                 print(2)
#             elif remain == 0:
#                 print(4)       
#     except:
#         break
        
        
# 解法2：直接查询法（运行时间112ms）
# 获取数阵第n行,第i个数,1<=i<=2n-1
def get_num(n, i):
    if i > n:
        i = 2*n-i
    if n <= 2:
        num = 1
    else:
        if i == 1:
            num = 1
        elif i == 2:
            num = get_num(n-1, 2) + get_num(n-1, 1)
        else:
            num = get_num(n-1, i-1) + get_num(n-1, i-2) + get_num(n-1, i)
    return num

# 查看前10行数阵
# for n in range(1, 10):
#     for i in range(1,2*n):
#         print(get_num(n,i), end=" ")
#     print("")

while True:
    try:
        n = int(input())
        # 前两行不存在偶数
        if n <= 2:
            print(-1)
        else:
            for i in range(1,2*n):
                # 依次判断当前值是否为偶数
                if get_num(n, i) % 2 ==0:
                    print(i)
                    break
    except:
        break

编辑于 2020-11-13 21:22:00 回复(0)

Python

公子i吃鱼

题目给的n的范围10000000000，我觉得就是在提醒我们。这个题找规律解决。否则，十有***会超时

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

发表于 2020-09-29 14:43:52 回复(3)

Python

牛客902100313号

while True:
try:
n = int(input())
list1 = []
list1.append([0,0,1,0,0])
if n > 1:
for i in range(1,n):
list1.append([0 for x in range(0,2*i+5)])
for j in range(2,2*(i+1)+1):
list1[i][j] = int(list1[i-1][j-2] + list1[i-1][j-1] + list1[i-1][j])
list2 = list1[n-1]
del list2[0]
del list2[0]
t = 0
for i in range(0,n):
if (list2[i] % 2) == 0:
print(i+1)
break
else:
t += 1
if t == n:
print(-1)
except:
break

发表于 2020-09-15 02:16:53 回复(0)

Python

牛客luckylulu

① 初始化二维数组并定义。

② 将杨辉三角形分为两部分赋值，以第 i 行第 i 个元素为中界，第 i 行前半部分元素与后半部分元素顺序正好相反。

③遍历第 i 行元素的值求第一个偶数出现的位置。

import sys
for line in sys.stdin:
    n = int(line)

    # 定义二维数组

    # N = [[0]*10 for i in range(10)]
    yanghui_triaang = [[0]*(2*n-1) for i in range(n)]

    yanghui_triaang[0][0] = 1
    yanghui_triaang[1][0], yanghui_triaang[1][1], yanghui_triaang[1][2] = 1, 1, 1
    # print(yanghui_triaang)
    if n == 0&nbs***bsp;n == 1:
        print(-1)
    else:
        for i in range(2, n):
            # 将杨辉三角形劈成一半，前半与后半顺序正好相反
            for j in range(n):
                if j == 0:
                    yanghui_triaang[i][j] = 1
                elif j == 1:
                    yanghui_triaang[i][j] = 1 + yanghui_triaang[i-1][j]
                else:
                    yanghui_triaang[i][j] = yanghui_triaang[i-1][j-2]+yanghui_triaang[i-1][j-1]+yanghui_triaang[i-1][j]

        for i in range(2, n):
            for j in range(i, 2*i+1):
                yanghui_triaang[i][j] = yanghui_triaang[i][j - (j-i)*2]


    # print(yanghui_triaang)


    # 输入n
    # 输出第N行第一个偶数的位置，若没有则输出-1
    flag = False
    for ele in yanghui_triaang[n-1]:
        if ele % 2 == 0:
            flag = True
            print(yanghui_triaang[n-1].index(ele)+1)
            break

    if flag == False:
        print(-1)

发表于 2020-09-10 19:27:16 回复(0)

Python

kite97

while True:
    try:
        row = int(input())
        if row == 1&nbs***bsp;row == 2:  print(-1)
        elif row % 2:  print(2)
        elif row % 4:  print(4)
        else:  print(3)
    except:
        break

手动模拟，算一算，有规律的，不用计算整个的三角形。

发表于 2020-09-02 17:23:09 回复(1)

Python

小明找工作

# python 3 递归
# case 通过率60%
def calculate(i,j):
    if i==1:
        return 1
    elif j<=0&nbs***bsp;j>2*i+1:
        return 0
    else:
        return calculate(i-1,j-2)+calculate(i-1,j-1)+calculate(i-1,j)

while True:
    try:
        n=int(input())
        if n==1:
            print(-1)
        for i in range(1,n+1):
            if calculate(n,i)%2==0:
                print(i)
                flag=1
                break
        if flag!=1:
            print(-1)
    except:
         break

动态规划代码-python3

## python 3 动态规划 
def dP(n):
    li=[[0 for j in range(n+1)] for i in range(n+1)]
    for i in range(1,n+1): # 因为不能使用numpy模块，只能使用for循环赋值。
        li[i][1]=1
    for i in range(1,n+1):
        for j in range(2,n):
            li[i][j]=li[i-1][j-2]+li[i-1][j-1]+li[i-1][j]
    #print(li)
    for i in range(1,n):
        if li[n][i]%2==0:
            flag=1
            break
    #print(i)
    return i if flag==1 else -1

while True:
    try:
        n=int(input())
        if n==1:
            print(-1)
        print(dP(n))
    except:
         break

编辑于 2020-09-01 20:26:19 回复(1)