Chúng tôi được cung cấp một cây có thể có các cấp vô tận, một biến con sẽ lưu trữ số lượng nút con mà một nút có thể có, một trọng số thay đổi sẽ lưu trữ trọng số liên quan đến đường dẫn và một đường dẫn biến sẽ lưu trữ đường dẫn và nhiệm vụ là để tính số lượng đường đi có trọng số bằng X và phải có ít nhất một cạnh có trọng số đã cho.
Ví dụ
Đầu vào - int con =4, weight =4, path =4;
Đầu ra - Đếm số đường đi có trọng lượng chính xác là X và có ít nhất một cạnh trọng số M là:1
Giải thích - Như chúng ta đã đưa ra với nút có 4 nút con được kết nối với 4 đường dẫn và có trọng số là 4 được liên kết với đường dẫn. Vì vậy, chúng ta có thể thấy rằng chỉ có thể có một đường dẫn với trọng số là 4, tức là 1 - 4 do đó số lượng là 1.
Đầu vào - int con =3, weight =2, path =4;
Đầu ra - Đếm số đường đi có trọng lượng chính xác là X và có ít nhất một cạnh trọng số M là:4
Giải thích - Như chúng ta đã đưa ra với nút có 3 nút con được kết nối với 4 đường dẫn và có trọng số là 2 liên kết với đường dẫn. Vì vậy, chúng ta có thể thấy rằng có thể có bốn đường dẫn với trọng số là 2, tức là 1-1, 1 - 2, 2-1 và 2-1, do đó, số lượng là 4.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
- Nhập tổng số phần tử con, đường dẫn và trọng số liên quan đến từng đường dẫn trong biến con, trọng số và đường dẫn tương ứng.
- Khai báo một mảng có kích thước đã cho.
- Bắt đầu vòng lặp FOR từ i đến 0 cho đến hết kích thước của một mảng. Bên trong vòng lặp, bắt đầu một vòng lặp FOR khác từ j đến 0 cho đến khi j nhỏ hơn 2 và sau đó đặt arr [i] [j] là -1.
- Bây giờ, hãy gọi hàm total_weight () bằng cách chuyển đường dẫn, 0, weight, child và arr làm đối số cho hàm.
- Bên trong hàm,
- Khai báo số lượng biến tạm thời để lưu trữ kết quả.
- Kiểm tra đường dẫn IF nhỏ hơn 0 rồi trả về 0
- Kiểm tra đường dẫn IF bằng 0 rồi trả về i
- Kiểm tra IF arr [path] [i] không bằng 1 rồi trả về arr [path] [i]
- Bắt đầu vòng lặp FOR từ j đến 1 cho đến con. Bên trong vòng lặp, hãy kiểm tra IF j bằng weight hơn set count dưới dạng lệnh gọi đệ quy tới hàm total_weight () bằng cách chuyển path-j, 1, weight, child và arr cho hàm dưới dạng đối số.
- Ngoài ra, hãy đặt số đếm dưới dạng lệnh gọi đệ quy tới hàm total_weight () bằng cách chuyển đường dẫn-j, i, weight, child và arr cho hàm dưới dạng đối số.
- Đặt arr [path] [i] làm số đếm và
- Trả về arr [path] [i]
- in kết quả.
Ví dụ
#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);
} Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Đầu ra
Count of number of paths whose weight is exactly X and has at-least one edge of weight M are: 1