python-8-算法优化练习题

第一题

• 求杨辉三角的第m行第k个元素
  • 第m行有m项，m是正整数，因此k一定不会大于m
  • 第m行的k个数可表示为C(m-1,k-1),即为从m-1个不同元素中取k-1个元素的组合数

第2(n)-1行的每个数都是奇数

第二题

• 给定一个3*3方阵，求其转置矩阵

第三题

• 给定一个矩阵，求其转置矩阵

第一题解答一

m = 5
k = 4
triangle=[]
for i in range(m):
    # 所有行都需要1开头
    row=[1]
    triangle.append(row)
    if i == 0:
        continue

    for j in range(1,i):
        row.append(triangle[i-1][j-1]+triangle[i-1][j])

    row.append(1)
print(triangle)
print("*"*10)
print(triangle[m-1][k-1])
print(‘*‘*10)

第一题解答二

根据杨辉三角的定义：第n行的m个数，可表示为C(n-1,m-1),
就是从n-1个不同元素中取m-1个元素的组合数
C(n,r)=n!/(r!(n-r)!)

# m行k列的值，C(m-1,k-1)组合数
m=9
k=5
# C(n,r)=n!/(r!(n-r)!)
# n最大
n = m-1 # m
r = k-1 # k
d = n-r
targets=[] # r,d,n
factorial=1
for i in range(1,n+1):
    factorial *= i
    # 这三个判断，不能写在一起，因为他们可能两两相等
    if i==r: 
        targets.append(factorial)
    if i==d:
        targets.append(factorial)
    if i==n:
        targets.append(factorial)
# print(targets)
print(targets[2]//(targets[0]*targets[1]))

第二题解答一

规律：对角线不动，a[i][j]=a[j][i]，而且到了对角线，就停止，去做下一行，对角线上的元素不动。

matrix=[[1,2,3],[4,5,6],[7,8,9]]
print(matrix)
count=0
temp=0
for i,row in enumerate(matrix):
    for j,col in enumerate(row):
        if i<j:
            temp,matrix[i][j],matrix[j][i]=matrix[i][j],matrix[j][i],temp
            count += 1
print(matrix)

第二题解答二

matrix=[[1,2,3,10],[4,5,6,11],[7,8,9,12],[1,2,3,4]]
length=len(matrix)
count=0
for i in range(length):
    for j in range(i):# j<i
        matrix[i][j],matrix[j][i]=matrix[j][i],matrix[i][j]
        count +=1
print(matrix)
print(count)

第三题解答一

算法1

过程就是，扫描matrix第一行，在tm的第一列从上到下添加。
然后再第二列添加。

举例，扫描第一行1,2,3，加入到tm的第一列，然后扫描第二行4，5,6，追加到tm的第二列

import datetime
matrix=[[1,2,3],[4,5,6]]
#matrix=[[1,4],[2,5],[3,6]]
tm=[]
count=0
for row in matrix:
    for i,col in enumerate(row):
        if len(tm)<i+1: # matrix有i列，就要为tm创建i行
            tm.append([])

        tm[i].append(col)
        count+=1
print(matrix)
print(tm)

因为有了append，追加的方式，就是内存当中没有新增的
所以有一点效率问题

第三题解答二

思考：

能够一次性开辟目标矩阵的内存空间？
如果一次性开辟好目标矩阵内存空间，那么原矩阵的元素直接移动到转置矩阵的对称坐标就可以了。

matrix=[[1,2,3],[4,5,6]]
# matrix=[[1,4],[2,5],[3,6]]

# 传统方法，构建占位tm
# tm = [0]*len(matrix[0])
# for i in range(len(tm)):
#     tm[i]=[0]*len(matrix)

# 列表解析式，构建占位tm
tm=[[0 for col in range(len(matrix))] for row in range(len(matrix[0]))]
count = 0


for i,row in enumerate(tm):
    for j,col in enumerate(row):
        tm[i][j]=matrix[j][i]
        count +=1

print(matrix)
print(tm)
print(count)

经过测试，矩阵越大，第二种方法效率越高。

python-8-算法优化练习题

原文：https://www.cnblogs.com/gnuzsx/p/12733370.html