Mr X muốn chọn 3 thành viên bạn cần sự trong lớp 10a2 có n học sinh hỏi số cách chọn

Question

Cách tính tổ hợp trong c++ bằng đệ quy

Ta có công thức truy hồi như sau:

Nội dung chính Show

Cách tính tổ hợp trong c++ bằng đệ quy
Cách tính tổ hợp trong c++ bằng phương pháp lặp
Thứ tự từ điển
Một tổ có 10 học sinh. Số cách chọn ra hai bạn học sinh làm tổ trưởng và tổphó là:

Với các tính chất sau:

Từ công thức truy hồi trên ta sẽ dễ dàng viết được một hàm đệ quy để tính tổ hợp như sau:

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

#include<iostream>

using namespace std;

int C(int k, int n) {

if (k == 0 || k == n) return 1;

if (k == 1) return n;

return C(k - 1, n - 1) + C(k, n - 1);

}

int main(){

int n, k;

cout << "Nhap k: ";

cin >> k;

cout << "Nhap n: ";

cin >> n;

cout << "To hop bang: " << C(k, n);

system("pause");

return 0;

}

Sau khi chạy chương trình thì chúng ta sẽ có kết quả sau

0

1

2

3

4

Nhap k: 3

Nhap n: 5

To hop bang: 10

Các bạn có thể thấy ở trên mình dùng ba điểm neo để làm điều kiện dừng đó là:

Tại k bằng 0 hoặc k bằng n thì ta phải return 1
Tại k bằng 1 thì ta return n

Hoàn toàn đúng với các tính chất mình đã trình bày ở trên nhé ^_^

Nhưng nhược điểm của phương pháp đệ quy này lại là tốc độ. không tin thì bạn cứ thử nhập k và n lớn xí nhé !

Cách tính tổ hợp trong c++ bằng phương pháp lặp

Số các tổ hợp chậpkcủaphần tử:

Với công thức trên thì ta chỉ cần viết một hàm tính giai thừa là xong rồi phải không nào. Chúng ta cùng bắt đầu nhé

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

#include<iostream>

using namespace std;

long long gt(int n) {

long long s = 1;

for (int i = 1; i <= n; i++)

s *= i;

return s;

}

long long C(int k, int n) {

returngt(n) / (gt(k)*gt(n - k));

}

int main(){

int n, k;

cout << "Nhap k: ";

cin >> k;

cout << "Nhap n: ";

cin >> n;

cout << "To hop bang: " << C(k, n);

system("pause");

return 0;

}

Mặc dù là nhanh nhưng cách làm trên vẫn không thể tính được nhũng số tổ hợp lớn được. Lý do đơn giản là vì khi tính ra giai thừa thì con số đã rất lớn. Đó cũng là lý do mà mình dùng kiểu long long ở trên (Nhưng chẳng nhằm nhò gì ^_^)

Các bạn thử cải thiện chương trình trên xem sao nhé ! Nếu có gặp khó khăn gì thì đừng ngại comment ở phía dưới mình sẽ hỗ trợ các bạn nhiệt tình. Bye !!!

Thứ tự từ điển

Trên các kiểu dữ liệu đơn giản chuẩn, người ta thường nói tới khái niệm thứ tự. Ví dụ trên kiểu số thì có quan hệ: 1 < 2; 2 < 3; 3 < 10; …, trên kiểu ký tự Char thì cũng có quan hệ 'A' < 'B'; 'C' < 'c'… Xét quan hệ thứ tự toàn phần "nhỏ hơn hoặc bằng" ký hiệu "≤" trên một tập hợp S, là quan hệ hai ngôi thoả mãn bốn tính chất:

Với mọia, b, c ϵS

Tính phổ biến: Hoặc là a ≤ b, hoặc b≤ a;

Tính phản xạ: a ≤ a

Tính phản đối xứng: Nếu a ≤ b và b ≤ a thì bắt buộc a = b. Tính bắc cầu: Nếu có a ≤ b và b ≤ c thì a ≤ c.

Trong trường hợp a ≤ b và a ≠b, ta dùng ký hiệu "<" cho gọn, (ta ngầm hiểu các ký hiệu như ≥, >, khỏi phải định nghĩa).

Ví dụ như quan hệ "≤" trên các số nguyên cũng như trên các kiểu vô hướng, liệt kê là quan hệ thứ tự toàn phần.

Trên các dãy hữu hạn, người ta cũng xác định một quan hệ thứ tự:

Xét a = (a1, a2, …, an) và b = (b1, b2, …, bn); trên các phần tử của a1, …, an, b1, …, bn đã có quan hệ thứ tự "≤". Khi đó a ≤ b nếu như:

Hoặc ai = bi với mọii: 1 ≤ i ≤ n.

Hoặc tồn tại một số nguyên dương k: 1 ≤ k < n để:

a1 = b1

a2 = b2

…

ak-1=bk-1

ak=bk

ak+1<bk+1

Trong trường hợp này, ta có thể viết a < b.

Thứ tự đó gọi là thứ tự từ điển trên các dãy độ dài n.

Khi độ dài hai dãy a và b không bằng nhau, người ta cũng xác định được thứ tự từ điển. Bằng cách thêm vào cuối dãy a hoặc dãy b những phần tử đặc biệt gọi là phần tử Ø để độ dài của a và b bằng nhau, và coi những phần tử Ø này nhỏ hơn tất cả các phần tử khác, ta lại đưa về xác định thứ tự từ điển của hai dãy cùng độ dài. Ví dụ:

(1, 2, 3, 4) < (5, 6)

(a, b, c) < (a, b, c, d)

'calculator' < 'computer'