社区首页 >专栏 >【每周一坑】杨辉三角形

【每周一坑】杨辉三角形

Crossin先生

发布于 2018-04-17 03:57:59

1.4K00

代码可运行

文章被收录于专栏：Crossin的编程教室Crossin的编程教室

运行总次数：0

代码可运行

杨辉三角形，也称帕斯卡三角，其定义为：顶端是 1,视为(row0).第1行(row1)(1&1)两个1,这两个1是由他们上头左右两数之和 (不在三角形内的数视为0).依此类推产生第2行(row2):0+1=1;1+1=2;1+0=1.第3行(row3):0+1=1;1+2=3; 2+1=3;1+0=1. 循此法可以产生以下诸行，如下图所示。

了解完背景知识之后，来看看对应的题目，定义一个函数 yanghui() ，传入正整数参数 M、N，分别代表杨辉三角形第 M 行，左起第 N 个数字（M,N 都从 0 开始计算）。入超出范围则返回 invalid query 。

示例代码：

def yanghui(m,n):
    '''
    >>>yanghui(1,1)
    1
    >>>yanghui(3,2)
    3
    >>>yanghui(1,4)
    invalid query
    '''

附加题：

生成杨辉三角形。

定义一个函数 generate_yh() 传入整数参数 M < 1000，生成前 M 行杨辉三角形。示例代码：

def generate_yh(m):
    '''
    generate_yh(3):
    1
    1 1
    1 2 1
    '''

【神奇的九宫格】解答

上一期题目提交的答案不算多，可能是由于这个题目偏难，使用暴力解法仅仅能算出 9 宫格，16 宫格的时候已经无能为力了。

在给出正确的答案之前，我们先了解一个名词 “幻方” ，百度百科定义：幻方（Magic Square）是一种将数字安排在正方形格子中，使每行、列和对角线上的数字和都相等的方法。

N 阶幻方的解题思路是其分为三种情况：N为奇数、N为4的倍数、N为其它偶数(4n+2的形式）。针对不同的情况有不同的解法，其详细说明见百度百科的【幻方】词条。

首先是 N 为奇数时：

将1放在第一行中间一列；
从2开始直到n×n止各数依次按下列规则存放，按 45°方向行走，如向右上，每一个数存放的行比前一个数的行数减1，列数加1
如果行列范围超出矩阵范围，则回绕。例如1在第1行，则2应放在最下一行，列数同样加1;
如果按上面规则确定的位置上已有数，或上一个数是第1行第n列时，则把下一个数放在上一个数的下面。

def oddN(n):
    # 构造二维列表
    lst = [[0 for i in range(n)] for i in range(n)] 
    # 初始化列表位置
    x,y = 0,n//2
    for num in range(1,n*n+1):
        lst[x][y] = num
        xa,ya = x-1,y+1
        # 回绕情况
        if xa < 0:
            xa = n-1
        if ya > n-1:
            ya = 0
        # 占位情况
        if lst[xa][ya] != 0:
            x = x + 1
            if x > n-1:
                x = 0
        else:
            x,y = xa,ya    return lst

lst = oddN(3)for row in lst:
    print(row)

当 N 为 4 的倍数时：采用对称元素交换法。首先把数1到n×n按从上至下，从左到右顺序填入矩阵。然后将方阵的所有N×N子方阵中的两对角线上位置的数关于方阵中心作对称交换，即a(i,j）与a(n-1-i,n-1-j）交换，所有其它位置上的数不变。

def fourN(n):
    # 初始化列表
    lst = [[i+j for i in list(range(1,n*n+1))[::n]] for j in range(n)]
    # 交换对角线位置
    for i in range(n//2):
        lst[i][i],lst[n-1-i][n-1-i] = lst[n-1-i][n-1-i],lst[i][i]
        lst[i][n-1-i],lst[n-1-i][i] = lst[n-1-i][i],lst[i][n-1-i]
    return lst

lst = fourN(8)
for row in lst:
    print(row)

当n为非4倍数的偶数（即4n+2）时：首先把大方阵分解为4个奇数子方阵。按上述奇数阶幻方给分解的4个子方阵对应赋值上左子阵最小（i），下右子阵次小（i+v），下左子阵最大（i+3v），上右子阵次大（i+2v) 即4个子方阵对应元素相差v，其中v=n*n/4 四个子矩阵由小到大排列方式为 ① ③ ④ ② 然后作相应的元素交换：a(i,j)与a(i+k,j)在同一列做对应交换，(jn-t),a(t,0)与a(t+k,0)；a(t,t)与a(t+k,t)两对元素交换，其中k=n//2，t=(n-2)//4 。

详细图解可见：

https://en.wikipedia.org/wiki/Strachey_method_for_magic_squares

# 累加子矩阵
def acc(p,lst):
    # print(lst)
    for row in lst:
        for index in range(len(row)):
            row[index] += p
        
    return lst
def fourNplus2(n):
    m = n//2
    A,B,C,D = oddN(m),oddN(m),oddN(m),oddN(m)
    B = acc(m**2,B)
    C = acc(m**2*2,C)
    D = acc(m**2*3,D)    
    for row_index in range(len(A)):
        A[row_index].extend(C[row_index])
        D[row_index].extend(B[row_index])
    # 合并子矩阵
    matrix = A+D
    t = (n-2)//4
    # 列交换
    for col_index in range(len(matrix[0])):
            if col_index < t or col_index > n-t:
                for row_index in range(len(matrix)//2):
                    matrix[row_index][col_index] , matrix[row_index+m][col_index] = \
matrix[row_index+m][col_index],matrix[row_index][col_index]    
    # 交换特殊位置
    matrix[t][0],matrix[m+t][0] = matrix[m+t][0],matrix[t][0]
    matrix[t][t],matrix[m+t][t] = matrix[m+t][t],matrix[t][t]
    return matrix

lst = fourNplus2(6)
for row in lst:
    print(row)