Đếm số đường đi có trọng số chính xác X và chứa ít nhất một cạnh trọng số M trong C++

Cho một cây có thể mở rộng vô hạn, biến child lưu số lượng nút con của mỗi nút, biến weight lưu trọng số liên quan đến đường đi, và biến path lưu đường đi. Nhiệm vụ là tính số lượng đường đi có tổng trọng số bằng X và có ít nhất một cạnh với trọng số M.

Ví dụ

Đầu vào: child = 4, weight = 4, path = 4

Đầu ra: Số đường đi thỏa mãn: 1

Giải thích: Nút có 4 nút con kết nối bằng 4 đường đi trọng số 4. Chỉ có một đường đi có trọng số 4 là 1 → 4, nên đếm = 1.

Đầu vào: child = 3, weight = 2, path = 4

Đầu ra: Số đường đi thỏa mãn: 4

Giải thích: Nút có 3 nút con, 4 đường đi trọng số 2. Có 4 đường đi trọng số 2: 1-1, 1-2, 2-1, 2-1 (đếm = 4).

Phương pháp sử dụng

• Nhập số lượng nút con, đường đi và trọng số vào các biến child, weight, path.
• Khai báo mảng kích thước cho trước.
• Vòng lặp FOR từ i = 0 đến kích thước mảng. Bên trong, vòng lặp FOR từ j = 0 đến j < 2 đặt arr[i][j] = -1.
• Gọi hàm total_weight() với tham số path, 0, weight, child, arr.
• Trong hàm:
  • Khai báo biến tạm count lưu kết quả.
  • Nếu path < 0 trả về 0.
  • Nếu path == 0 trả về i.
  • Nếu arr[path][i] != -1 trả về arr[path][i].
  • Vòng lặp FOR từ j = 1 đến child. Nếu j == weight gọi đệ quy total_weight(path - j, 1, weight, child, arr), ngược lại gọi total_weight(path - j, i, weight, child, arr).
  • Gán arr[path][i] = count và trả về.
• In kết quả.

Ví dụ mã nguồn

#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); 
}

Chạy mã trên cho kết quả:

Kết quả

Count of number of paths whose weight is exactly X and has at-least one edge of weight M are: 1