เราได้รับต้นไม้ที่สามารถมีระดับไม่จำกัด ตัวแปร child จะเก็บจำนวนลูกที่โหนดสามารถมีได้ ตัวแปร weight จะเก็บน้ำหนักที่เกี่ยวข้องกับเส้นทาง และตัวแปร path จะเก็บเส้นทาง และภารกิจคือการคำนวณจำนวนเส้นทางที่มีน้ำหนักเท่ากับ X และต้องมีขอบอย่างน้อยหนึ่งขอบที่มีน้ำหนักตามที่กำหนด
ตัวอย่าง
Input - int child = 4, weight = 4, path = 4;
Output - จำนวนเส้นทางที่น้ำหนักเท่ากับ X และมีขอบน้ำหนัก M อย่างน้อยหนึ่งขอบคือ: 1
คำอธิบาย - เราได้รับโหนดที่มีลูก 4 ตัว เชื่อมต่อด้วย 4 เส้นทาง และมีน้ำหนัก 4 ที่เกี่ยวข้องกับเส้นทาง ดังนั้นเราเห็นว่ามีเพียงเส้นทางเดียวที่มีน้ำหนักเป็น 4 คือ 1 - 4 ดังนั้นจำนวนนับคือ 1
Input - int child = 3, weight = 2, path = 4;
Output - จำนวนเส้นทางที่น้ำหนักเท่ากับ X และมีขอบน้ำหนัก M อย่างน้อยหนึ่งขอบคือ: 4
คำอธิบาย - เราได้รับโหนดที่มีลูก 3 ตัว เชื่อมต่อด้วย 4 เส้นทาง และมีน้ำหนัก 2 ที่เกี่ยวข้องกับเส้นทาง ดังนั้นเราเห็นว่ามีเส้นทาง 4 เส้นทางที่มีน้ำหนักเป็น 2 คือ 1-1, 1-2, 2-1 และ 2-1 ดังนั้นจำนวนนับคือ 4
แนวทางที่ใช้ในโปรแกรมด้านล่าง
- รับจำนวนลูกทั้งหมด เส้นทาง และน้ำหนักที่เกี่ยวข้องกับแต่ละเส้นทางในตัวแปร child, weight และ path ตามลำดับ
- ประกาศอาร์เรย์ขนาดที่กำหนด
- เริ่มลูป FOR จาก i = 0 ถึงขนาดของอาร์เรย์ ภายในลูป เริ่มลูป FOR อีกทีหนึ่งจาก j = 0 ถึง j < 2 แล้วตั้งค่า arr[i][j] = -1
- เรียกฟังก์ชัน total_weight() โดยส่ง path, 0, weight, child และ arr เป็นอาร์กิวเมนต์
- ภายในฟังก์ชัน
- ประกาศตัวแปรชั่วคราว count เพื่อเก็บผลลัพธ์
- ตรวจสอบ IF path < 0 แล้วคืนค่า 0
- ตรวจสอบ IF path == 0 แล้วคืนค่า i
- ตรวจสอบ IF arr[path][i] != 1 แล้วคืนค่า arr[path][i]
- เริ่มลูป FOR จาก j = 1 ถึง child ภายในลูป ตรวจสอบ 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 และ
- คืนค่า 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
