資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律學C++程式計算刪除所有節點所需操作的期望次數
假設我們有有向圖 G 的鄰接矩陣。在圖變為空之前，我們重複執行以下操作：從 G 中選擇一個頂點，然後擦除該頂點和所有可以透過跟隨一些邊從該頂點到達的頂點。擦除一個頂點也將擦除與其關聯的邊。我們必須找到操作執行的期望次數。
因此，如果輸入類似於
則輸出將為 1.6667，因為最初選擇頂點 A，刪除所有頂點，如果我們選擇頂點 B，刪除 B 和 C，在第二次操作中選擇 A 以刪除它，類似地，透過選擇 C 也需要 2 次操作。因此平均值為 (1+2+2)/3 = 1.6667。
步驟
為了解決這個問題，我們將遵循以下步驟 -
n := size of G for initialize i := 0, when i < n, update (increase i by 1), do: G[i, i] := 1 for initialize k := 0, when k < n, update (increase k by 1), do: for initialize i := 0, when i < n, update (increase i by 1), do: for initialize j := 0, when j < n, update (increase j by 1), do: if G[i, k] is non-zero and G[k, j] is non-zero, then: G[i, j] := 1 ans := 0 for initialize i := 0, when i < n, update (increase i by 1), do: k := 0 for initialize j := 0, when j < n, update (increase j by 1), do: if G[j, i] is non-zero, then: (increase k by 1) ans := ans + 1.0 / k return ans
示例
讓我們看一下以下實現以獲得更好的理解 -
#include <bits/stdc++.h>
using namespace std;
double solve(vector<vector<int>> G){
int n = G.size();
for (int i = 0; i < n; ++i)
G[i][i] = 1;
for (int k = 0; k < n; ++k)
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
if (G[i][k] && G[k][j])
G[i][j] = 1;
double ans = 0;
for (int i = 0; i < n; ++i){
int k = 0;
for (int j = 0; j < n; ++j)
if (G[j][i])
++k;
ans += 1.0 / k;
}
return ans;
}
int main(){
vector<vector<int>> G = { { 0, 1, 0 }, { 0, 0, 1 }, { 0, 1, 0 }};
cout << solve(G) << endl;
}輸入
{ { 0, 1, 0 }, { 0, 0, 1 }, { 0, 1, 0 } }輸出
1.66667
更新於: 2022年3月3日
109 次檢視
廣告