找出给定特殊矩阵的行列式的 Python 程序
假设,我们有一棵树有n个顶点,其中每个顶点的标签从1到n。树的根标签为1,每个顶点的权重为wi。现在形成了一个nxn矩阵A其中A(x,y)=Wf(x,y)wheref(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给出为=
这个矩阵的行列式是24。
示例
让我们看看以下实现以获得更好的理解-
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