【每周一坑】杨辉三角形

杨辉三角形，也称帕斯卡三角，其定义为：顶端是 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)

答案也可参考：

@FisherC：

https://github.com/FisherCh/Homework/blob/master/cossing.py

@FreedomLy：

https://gist.github.com/Felon03/bfd4e9c21768b31db45ec30b385f3c9b

赞 (0)

相关推荐