資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學使用 C++ 統計權重恰好為 X 且至少有一條邊權重為 M 的路徑數量
給定一棵可以有無限層級的樹，變數 child 儲存節點可以擁有的子節點數量，變數 weight 儲存與路徑關聯的權重，變數 path 儲存路徑，任務是計算權重等於 X 且至少有一條邊權重為 M 的路徑的數量。
例如
輸入 - int child = 4, weight = 4, path = 4;
輸出 - 權重恰好為 X 且至少有一條邊權重為 M 的路徑數量為：1
解釋 - 給定一個具有 4 個子節點的節點，它們透過 4 條路徑連線，每條路徑的權重為 4。因此，只有一條權重為 4 的路徑，即 1-4，所以計數為 1。
輸入 - int child = 3, weight = 2, path = 4;
輸出 - 權重恰好為 X 且至少有一條邊權重為 M 的路徑數量為：4
解釋 - 給定一個具有 3 個子節點的節點，它們透過 4 條路徑連線，每條路徑的權重為 2。因此，可以有四條權重為 2 的路徑，即 1-1, 1-2, 2-1 和 2-1，所以計數為 4。
下面程式中使用的演算法如下
- 分別輸入子節點總數、路徑總數和與每條路徑關聯的權重到變數 child、weight 和 path 中。
- 宣告一個給定大小的陣列。
- 從 i=0 開始迴圈到陣列大小。在迴圈內，從 j=0 開始迴圈到 j<2，然後將 arr[i][j] 設定為 -1。
- 現在呼叫函式 total_weight()，並將 path、0、weight、child 和 arr 作為引數傳遞給函式。
- 在函式內部：
- 宣告一個臨時變數 count 來儲存結果。
- 如果 path 小於 0，則返回 0
- 如果 path 等於 0，則返回 i
- 如果 arr[path][i] 不等於 1，則返回 arr[path][i]
- 從 j=1 開始迴圈到 child。在迴圈內，如果 j 等於 weight，則將 count 設定為對函式 total_weight() 的遞迴呼叫，並將 path-j、1、weight、child 和 arr 作為引數傳遞給函式。
- 否則，將 count 設定為對函式 total_weight() 的遞迴呼叫，並將 path-j、i、weight、child 和 arr 作為引數傳遞給函式。
- 將 arr[path][i] 設定為 count，並且
- 返回 arr[path][i]
- 列印結果。
示例
#include <bits/stdc++.h>
using namespace std;
#define size 4
#define col 4
int total_weight(int path, int i, int weight, int child, int arr[size + 1][col]) {
int count = 0;
if (path < 0) {
return 0;
}
if (path == 0) {
return i;
}
if (arr[path][i] != -1) {
return arr[path][i];
}
for (int j = 1; j <= child; j++) {
if (j == weight) {
count += total_weight(path - j, 1, weight, child, arr);
} else {
count += total_weight(path - j, i, weight, child, arr);
}
}
arr[path][i] = count;
return arr[path][i];
}
int main() {
int child = 4, weight = 4, path = 4;
int arr[size + 1][col];
for (int i = 0; i <= size; i++) {
for (int j = 0; j < 2; j++) {
arr[i][j] = -1;
}
}
cout << "Count of number of paths whose weight is exactly X and has at-least one edge of weight M are: " << total_weight(path, 0, weight, child, arr);
}如果我們執行上面的程式碼，它將生成以下輸出：
輸出
Count of number of paths whose weight is exactly X and has at-least one edge of weight M are: 1
更新於：2021年1月29日
瀏覽量 133 次
廣告