นับจำนวนเส้นทางที่มีน้ำหนักเท่ากับ X และมีน้ำหนัก M อย่างน้อยหนึ่งขอบใน C++

เราได้รับต้นไม้ที่สามารถมีระดับไม่มีที่สิ้นสุด ตัวแปรลูกที่จะเก็บจำนวนลูกที่โหนดสามารถมี น้ำหนักตัวแปรซึ่งจะเก็บน้ำหนักที่เกี่ยวข้องกับเส้นทางและเส้นทางตัวแปรที่จะเก็บเส้นทางและงานคือ เพื่อคำนวณจำนวนเส้นทางที่มีน้ำหนักเท่ากับ X และต้องมีขอบอย่างน้อยหนึ่งเส้นที่มีน้ำหนักที่กำหนด

ตัวอย่าง

ป้อนข้อมูล - เด็ก int =4 น้ำหนัก =4 เส้นทาง =4;

ผลลัพธ์ - การนับจำนวนเส้นทางที่น้ำหนักเท่ากับ X และมีน้ำหนักอย่างน้อยหนึ่งขอบ M คือ:1

คำอธิบาย - ตามที่เราได้รับกับโหนดที่มีลูก 4 คนเชื่อมต่อกับ 4 เส้นทางและมีน้ำหนัก 4 ที่เกี่ยวข้องกับเส้นทาง ดังนั้นเราจะเห็นได้ว่ามีเพียงเส้นทางเดียวที่มีน้ำหนักเท่ากับ 4 คือ 1 - 4 ดังนั้นการนับคือ 1

ป้อนข้อมูล - เด็ก int =3, น้ำหนัก =2, เส้นทาง =4;

ผลลัพธ์ - การนับจำนวนเส้นทางที่น้ำหนักเท่ากับ X และมีน้ำหนักอย่างน้อยหนึ่งขอบ M คือ:4

คำอธิบาย - ตามที่เราได้รับกับโหนดที่มีลูก 3 คนเชื่อมต่อกับ 4 เส้นทางและมีน้ำหนัก 2 ที่เกี่ยวข้องกับเส้นทาง ดังนั้นเราจะเห็นได้ว่าสามารถมีสี่เส้นทางที่มีน้ำหนักเป็น 2 คือ 1-1, 1 - 2, 2-1 และ 2-1 ดังนั้นการนับคือ 4

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้

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