Hôm nay mình sẽ ra mắt đến những bạn cách tính tổ hợp trong c + + bằng chiêu thức đệ quy và giải pháp lặp. Nhưng thứ nhất ta cùng tìm hiểu và khám phá tổ hợp là gì nhé ?

Trong Toán học, tổ hợp là cách chọn những phần tử từ một nhóm lớn hơn mà không phân biệt thứ tự. Ví dụ chọn 2 trong 3 phần tử {1, 2, 3 } sẽ có ba cách chọn đó là: {1, 2}, {1, 3}, {2, 3}. Các bạn có thể tham khảo tại đây để hiểu rõ hơn.

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

Ta có công thức truy hồi như sau: C^k_n + C^{k+1}_n = C^{k+1}_{n+1}

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

  • C^0_n=C^n_n = 1
  • C^1_n = C^{n-1}_n = n

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

0123456789101112131415161718

#include

usingnamespacestd;

intC(intk,intn){

if(k==0||k==n)return1;

if(k==1)returnn;

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

}

intmain(){

intn,k;

cout<<" Nhap k : ";

cin>>k;

cout<<" Nhap n : ";

cin>>n;

cout<<" To hop bang : "<

system(” pause “);

return0;

}

Sau khi chạy chương trình thì tất cả chúng ta sẽ có hiệu quả sau

01234 Nhap k : 3Nhap n : 5To hop bang : 10

Các bạn hoàn toàn có thể thấy ở trên mình dùng ba điểm neo để làm điều kiện kèm theo 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 những đặc thù mình đã trình diễn ở trên nhé ^ _ ^
Nhưng điểm yếu kém của giải pháp đệ quy này lại là vận 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 chiêu thức lặp

Số những tổ hợp chập k của n thành phần :
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 khởi đầu nhé

0

1

2345678910111213141516171819202122

#include

usingnamespacestd;

longlonggt(intn){

longlongs=1;

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

s*=i;

returns;

}

longlongC(intk,intn){

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

}

intmain(){

intn,k;

cout<<" Nhap k : ";

cin>>k;

cout<<" Nhap n : ";

cin>>n;

cout<<" To hop bang : "<

system(” pause “);

return0;

}

 

Mặc dù là nhanh nhưng cách làm trên vẫn không hề tính được nhũng số tổ hợp lớn được. Lý do đơn thuần là vì khi tính ra giai thừa thì số lượng đã rất lớn. Đó cũng là nguyên 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 tổ chương trình trên xem sao nhé ! Nếu có gặp khó khăn vất vả gì thì đừng ngại comment ở phía dưới mình sẽ tương hỗ những bạn nhiệt tình. Bye ! ! !

Đánh giá bài viết