資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
廣告