[Bài Tập C++] Bài Toán Cách Chọn Choise.***

[Bài Tập C++] Bài Toán Cách Chọn Choise.***

SỐ CÁCH CHON (CHOICES.***)

        Một lớp học có n học sinh, thầy giáo muốn chọn ra đúng k học sinh lên bảng kiểm tra bài cũ, hỏi thầy giáo có bao nhiêu cách chọn khác nhau. Ở đây hai cách chọn giống nhau được gọi là khác nhau nếu tồn tại một học sinh được chọn trong cách thứ nhất nhưng không được chọn trong cách thứ hai.

       

        Ví dụ:

Với lớp có n=5 học sinh A, B, C, D, E nếu thầy giáo muốn chọn ra đúng k=3 người thì có 10 cách chọn là : ABC, ABD, ABE, ACD, ADE, BCD, BCE, BDE, CDE.

Dữ Liệu: Vào từ thiết bị nhập chuẩn hai số nguyên n,k cách nhau bởi dấu cách trống ($1 \leq k \leq n \leq 60$) 

Kết quả: Ghi ra thiết bị xuất chuẩn số cách chọn của thầy giáo

Minh hoạ:

  

Sample Input	Sample Output
5         3	10

Giải Thuật: Với bài toán này chúng ta chỉ cần có công thức là giải được.Về công thức của bài toán này thì sử dụng bài toán chọn số: 

VD: Cho 6 số 1,2,3,4,5,6. Hỏi có thể lập được bao nhiêu số có 3 chữ số khác nhau từ 6 số đã cho. 

Nhưng ở đây thì khác, đối với bài toán chọn số thì 123 giống 132 nhưng ở bài toán CHOISE thì ABC lại gióng ACB. Vì vậy ta cần thêm một phép chia các cách trùng lặp như trên. Và dễ dàng đoán ra phép chia là cho k!

Với giải thuật như trên ta có code của bài toán trên như sau:

Lời giải: 

#include <iostream>

#include <math.h>

using namespace std;

int main()

{

    long long n,k,i,chon=1;

    cin>>n>>k;

    for (i=1;i<=k;i++)

    {

        chon=chon*n/i;

        n=n-1;

    }

    cout<<chon;

    return 0;

}

____________________________________________

Giải Thuật: Với bài toán này chúng ta chỉ cần có công thức là giải được.Về công thức của bài toán này thì sử dụng bài toán chọn số: VD: Cho 6 số 1,2,3,4,5,6. Hỏi có thể lập được bao nhiêu số có 3 chữ số khác nhau từ 6 số đã cho. Nhưng ở đây thì khác, đối với bài toán chọn số thì 123 giống 132 nhưng ở bài toán CHOISE thì ABC lại gióng ACB. Vì vậy ta cần thêm một phép chia các cách trùng lặp như trên. Và dễ dàng đoán ra phép chia là cho k! Với giải thuật như trên ta có code của bài toán trên như sau: #include #include