Đếm các cặp khi một người có thể tạo thành nhiều nhất một cặp trong C ++

Chúng tôi được cung cấp với N không. của những người tham gia cuộc thi viết mã. Mục đích là để tìm ra không. trong số các cặp có thể có khi một người có thể ghép đôi với nhiều nhất một người khác. Vì vậy một cặp có nhiều nhất là 2 người tham gia. Những người tham gia cũng được phép tham gia một mình.

Chúng tôi có thể giải quyết vấn đề này bằng cách sử dụng lặp lại trong đó các cặp =

• count =1 khi n =0 hoặc 1 (chỉ còn một người)

• nếu một người vẫn độc thân thì n giảm xuống còn n-1

  • bây giờ để ghép nối còn lại, những người còn lại =n-2

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

Hãy cùng hiểu với các ví dụ.

Đầu vào - người =3

Đầu ra - Đếm cách ghép đôi - 4

Giải thích -

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

Đầu vào - người =2

Đầu ra - Đếm cách ghép đôi - 2

Giải thích -

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

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

• Chúng tôi lấy một số nguyên để lưu trữ số lượng người tham gia.

• Hàm makePairs (int p) không có. của những người làm đầu vào và trả về số lượng các cách mà họ có thể tự ghép nối.

• Lấy số lượng ban đầu là 0.

• Nếu p =0 hoặc 1 thì cách duy nhất là 1 để duy trì tình trạng độc thân.

• Người khác có thể chọn ở lại độc thân, sau đó người còn lại (p-1) sẽ tìm các cặp bằng cách sử dụng (p1) * makePairs (p-2).

• Giá trị cuối cùng của số đếm được trả về là không. các cách ghép nối ở cuối.

Ví dụ

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

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -

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