数据结构
网络
关系数据库管理系统 (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 次
广告