home

หน้าแรก
 Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

นับจำนวนวิธีในการแบ่งชุดเป็น k ชุดย่อยใน C++

ให้ตัวเลขสองตัว e และ p เป้าหมายคือการนับจำนวนวิธีที่เราสามารถแบ่งองค์ประกอบ e ของชุดออกเป็นพาร์ติชั่น/ชุดย่อยได้

ตัวอย่าง

อินพุต

e=4 p=2

ผลลัพธ์

Count of number of ways to partition a set into k subsets are: 7

คำอธิบาย

If elements are: a b c d then ways to divide them into 2 partitions are: (a,b,c)−(d), (a,b)−(c,d), (a,b,c)−(d), (a)−(b,c,d), (a,c)−(b,d), (a,c,d)−(b), (a,b,d)−(c). Total 7 ways.

อินพุต

e=2 p=2

ผลลัพธ์

Count of number of ways to partition a set into k subsets are: 1

คำอธิบาย

If elements are: a b then ways to divide them into 2 partitions are:
(a)− (b). Total 1 way only.

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

ในแนวทางนี้ เราจะใช้แนวทางการเขียนโปรแกรมแบบไดนามิก การคำนวณที่ใช้ในโซลูชันจะเป็นแบบเรียกซ้ำเสมอ หากเราแบ่งองค์ประกอบออกเป็นพาร์ติชั่น p แล้ว −

  • หากองค์ประกอบ e-1 สามารถแบ่งออกเป็น p พาร์ติชั่นได้หลายวิธี (e-1,p) จากนั้นเราสามารถใส่องค์ประกอบปัจจุบันลงในพาร์ติชั่น p ตัวใดตัวหนึ่งในรูปแบบ p*ways(e-1,p)

  • หากองค์ประกอบ e-1 ถูกแบ่งออกเป็น p-1 พาร์ติชันด้วยวิธีต่างๆ (e-1,p-1) ดังนั้นการวาง 1 องค์ประกอบใน 1 พาร์ติชันที่แยกจากกันจะมี 1*วิธี(e-1,p-1) วิธีทั้งหมดจะ bep*ways(e-1,p)+ways(e-1,p-1) วิธีการนี้จะกลายเป็นแบบเรียกซ้ำ -

นับจำนวนวิธีในการแบ่งชุดเป็น k ชุดย่อยใน C++

ดังที่แสดงไว้ข้างต้น การคำนวณซ้ำจะทำได้ เพื่อหลีกเลี่ยงปัญหานี้ เราจะใช้วิธีการเขียนโปรแกรมแบบพลวัต

  • รับตัวแปร องค์ประกอบ และพาร์ติชั่นเป็นอินพุต

  • ฟังก์ชัน partition_k(อิลิเมนต์ int, พาร์ติชั่น int) รับทั้งตัวแปรและคืนค่าจำนวนวิธีที่จะแบ่งชุดออกเป็น k ชุดย่อย

  • ใช้อาร์เรย์ 2 มิติ arr[elements + 1][partition + 1] เพื่อเก็บค่าของ way(e,p) ใน arr[e][p].

  • ใช้ a for loop จาก i=0 ถึง i=elements ให้ตั้งค่า arr[i][0] =0 เนื่องจากจำนวนพาร์ติชั่นคือ 0 จากนั้นจึงค่อย way(i,0)=0

  • อีกครั้งโดยใช้ for ลูปจาก j=0 ถึง i=partitions ให้ตั้งค่า arr[0][j] =0 เนื่องจากจำนวนองค์ประกอบคือ 0 จากนั้นจึงวิธี(0,i)=0

  • ตอนนี้สำรวจ arr[][] โดยใช้สองลูปจาก i=1 ถึง i<=elements และ j=1 ถึง j<=i และเติมค่าการพักผ่อน

  • สำหรับองค์ประกอบเดียว วิธี=1 หรือสำหรับการแบ่งองค์ประกอบ x ออกเป็น x พาร์ติชั่น มีเพียง 1 วิธีเท่านั้น ดังนั้นให้ตั้งค่า arr[i][j] =1 ในกรณีที่ i==j หรือ j==1

  • มิฉะนั้น ให้ตั้งค่า temp_1 =arr[i-1][j−1] และ temp_2 =arr[i-1][j] และอัปเดต arr[i][j] =j * temp_2 + temp_1

  • ในตอนท้ายของลูปทั้งหมดเราจะมี arr[elements][partition] เป็นวิธีทั้งหมด

  • ส่งคืน arr[elements][partition] เป็นผลลัพธ์

ตัวอย่าง

#include<iostream>
using namespace std;
int partition_k(int elements, int partition){
   int arr[elements + 1][partition + 1];
   for(int i = 0; i <= elements; i++){
      arr[i][0] = 0;
   }
   for(int j = 0; j <= partition; j++){
      arr[0][partition] = 0;
   }
   for(int i = 1; i <= elements; i++){
      for (int j = 1; j <= i; j++){
         if (j == 1 || i == j)
         { arr[i][j] = 1; }
         else{
            int temp_1 = arr[i−1][j−1];
            int temp_2 = arr[i−1][j];
            arr[i][j] = j * temp_2 + temp_1;
         }
      }
   }
   return arr[elements][partition];
}
int main(){
   int elements = 4;
   int partition = 2;
   cout<<"Count of number of ways to partition a set into k subsets are: "<<partition_k(elements, partition);
   return 0;
}

ผลลัพธ์

หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -

Count of number of ways to partition a set into k subsets are: 7