数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究Python程序用于查找给定特殊矩阵的行列式
假设我们有一棵有n个顶点的树，每个顶点从1到n标记。树的根节点标记为1，每个顶点的权重为wi。现在形成一个nxn矩阵A，其中A(x,y) = Wf(x, y)，其中f(x, y)是顶点x和y的最近公共祖先。我们需要找到矩阵A的行列式。矩阵的边、权重和顶点总数作为输入给出。
因此，如果输入类似于input_array = [[1, 2], [1, 3], [1, 4], [1, 5]]，weights = [1, 2, 3, 4, 5]，vertices = 5，则输出将为24。
矩阵A给出如下：
| 1 | 1 | 1 | 1 | 1 |
| 1 | 2 | 1 | 1 | 1 |
| 1 | 1 | 3 | 1 | 1 |
| 1 | 1 | 1 | 4 | 1 |
| 1 | 1 | 1 | 1 | 5 |
该矩阵的行列式为24。
为了解决这个问题，我们将遵循以下步骤：
- w := 一个空列表
- 对于范围从0到vertices的i，执行：
- 将weights[i]和一个新列表添加到w中
- 对于每个i、item，枚举input_array，执行：
- p := item[0]
- q := item[1]
- 在w[p - 1, 1]的末尾插入q - 1
- 在w[q - 1, 1]的末尾插入p - 1
- det := 1
- stack := 一个包含元组(0, 0)的栈
- 当stack不为空时，执行：
- i, weights := 从栈中删除顶部元素
- det := (det * (w[i, 0] - weights)) mod (10^9 + 7)
- 对于w[i][1]中的t，执行：
- 将包含(t,w[i,0])的元组添加到栈中
- 对于w[i][1]中的每个t，执行：
- 从w[t,1]中删除i
- 返回det
示例
让我们看看以下实现以更好地理解：
def solve(input_array, weights, vertices): w = [[weights[i],[]] for i in range(vertices)] for i, item in enumerate(input_array): p,q = item[0], item[1] w[p - 1][1].append(q - 1) w[q - 1][1].append(p - 1) det = 1 stack = [(0,0)] while stack: i, weights = stack.pop() det = (det * (w[i][0] - weights)) % (10**9 + 7) stack += [(t,w[i][0]) for t in w[i][1]] for t in w[i][1]: w[t][1].remove(i) return det print(solve([[1, 2], [1, 3], [1, 4], [1, 5]], [1, 2, 3, 4, 5], 5))
输入
[[1, 2], [1, 3], [1, 4], [1, 5]], [1, 2, 3, 4, 5], 5
输出
24
更新于: 2021年5月18日
403 次浏览
广告