การนับคู่เมื่อบุคคลสามารถจับคู่ได้มากที่สุดหนึ่งคู่ใน C++

เราได้รับโดยไม่มี N ของผู้เข้าร่วมการแข่งขันเขียนโค้ด เป้าหมายคือการหาหมายเลข ของคู่ที่เป็นไปได้เมื่อบุคคลสามารถจับคู่กับอีกคนหนึ่งได้มากที่สุด ดังนั้นคู่หนึ่งจึงมีผู้เข้าร่วมไม่เกิน 2 คน ผู้เข้าร่วมสามารถมีส่วนร่วมคนเดียวได้เช่นกัน

เราสามารถแก้ไขได้โดยใช้การทำซ้ำโดยที่ pairs=

• count=1 เมื่อ n=0 หรือ 1 ( เหลือเพียงคนเดียว )

• ถ้าคนยังโสด n ลดลงเหลือ n-1

  • ตอนนี้สำหรับคนจับคู่ที่เหลือ =n-2

    count=makePairs(p-1) + (p-1)*makePairs(p-2);

มาทำความเข้าใจกับตัวอย่างกัน

ป้อนข้อมูล − คน=3

ผลผลิต − นับวิธีสร้างคู่ − 4

คำอธิบาย −

If three persons are a,b,c then ways of pairing could be:
(a,b), (c) → c remained single
(a,c), (b) → b remained single
(b,c), (a) → a remained single
(a),(b),(c) → all remained single
Total ways = 4

ป้อนข้อมูล − คน=2

ผลผลิต − นับวิธีสร้างคู่ − 2

คำอธิบาย −

I persons are a,b then ways of pairing could be −
(a,b) → both paired
(a),(b) → both remained single
Total ways = 2

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

• เราใช้บุคคลจำนวนเต็มเพื่อเก็บจำนวนผู้เข้าร่วม

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

• นับเริ่มต้นเป็น 0

• ถ้า p=0 หรือ 1 วิธีเดียวคือ 1 ที่จะยังคงเป็นโสด

• คนอื่นสามารถเลือกที่จะโสด จากนั้นที่เหลือ (p-1) จะค้นหาคู่โดยใช้ (p1)*makePairs(p-2)

• ค่าสุดท้ายของการนับจะถูกส่งกลับเป็นไม่ ของวิธีการจับคู่ในตอนท้าย

ตัวอย่าง

#include<iostream>
using namespace std;
int makePairs(int p){
   int count=0;
   // Base condition
   if (p==0 || p==1)
      { count=1; }
   else
      { count=makePairs(p-1) + (p-1)*makePairs(p-2); }
   return count;
}
int main(){
   int persons = 5;
   cout <<"Number of ways to make pair ( or remain single ):"<<makePairs(persons);
   return 0;
}

ผลลัพธ์

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

Number of ways to make pair ( or remain single ): 26