Thuật toán đệ quy dưới đây tính:

Function Test(a,b): Integer;

Begin

If (b = a) or (b = 0) then Test:=1

Else Test := Test (a-1,b-1) + Test (a-1,b);

End;

Bội chung nhỏ nhất của a và b

Ước chung lớn nhất của a và b

Số Fibonaci thứ a

Tổ hợp chập b của a

Trả lời:

Đáp án đúng: D

Đoạn code trên tính tổ hợp chập b của a, ký hiệu C(a, b). Ta có thể thấy rõ điều này nếu thay đổi cách viết như sau:

Function C(a, b): Integer;

Begin

If (b = a) or (b = 0) then C:=1

Else C := C (a-1, b-1) + C (a-1, b);

End;

Công thức truy hồi trên chính là công thức tính tổ hợp: C(n, k) = C(n-1, k-1) + C(n-1, k) với điều kiện dừng C(n, 0) = C(n, n) = 1.

525 câu trắc nghiệm môn Toán rời rạc kèm lời giải chi tiết - Phần 3

Bộ 525 câu hỏi trắc nghiệm ôn thi môn Toán rời rạc có đáp án dưới đây sẽ là tài liệu ôn tập hữi ích dành cho các bạn sinh viên. Mời các bạn cùng tham khảo!

30 câu hỏi 60 phút

Bắt đầu thi

Câu hỏi liên quan

Câu 17:

Cho thuật toán:

Function Test(a,b): Integer;

Begin

If (b = a) or (b = 0) then Test:=1

Else Test := Test (a-1,b-1) + Test (a-1,b);

End;

Với a = 21, b = 3. Kết quả nào đúng trong số những kết quả dưới đây:

Lời giải:

Đáp án đúng: B

Để giải bài này, ta cần tính giá trị của `Test(21, 3)` bằng cách sử dụng đệ quy theo thuật toán đã cho.

`Test(21, 3) = Test(20, 2) + Test(20, 3)`

Để tính `Test(20, 2)` và `Test(20, 3)`, ta tiếp tục áp dụng đệ quy:

`Test(20, 2) = Test(19, 1) + Test(19, 2)`
`Test(20, 3) = Test(19, 2) + Test(19, 3)`

Tiếp tục phân tích cho đến khi đạt đến điều kiện dừng (b = a hoặc b = 0):

Nhận thấy rằng hàm này thực chất đang tính tổ hợp chập k của n, tức là C(n, k), hay "n choose k". Trong trường hợp này, ta có C(21, 3).

Công thức tính tổ hợp chập k của n là: C(n, k) = n! / (k! * (n-k)!) hoặc C(n, k) = C(n-1, k-1) + C(n-1, k)

Vậy, `Test(21, 3)` tương ứng với C(21, 3) = 21! / (3! * 18!) = (21 * 20 * 19) / (3 * 2 * 1) = 1330

Vậy đáp án đúng là 1330.

Câu 18:

Trong bất kỳ một nhóm có 367 người, thế nào cũng có:

Lời giải:

Đáp án đúng: C

Trong một năm thông thường, có 365 ngày. Nếu có 367 người trong một nhóm, theo nguyên lý Dirichlet (hay còn gọi là nguyên lý chuồng chim bồ câu), ít nhất sẽ có hai người có cùng ngày sinh. Nguyên lý Dirichlet phát biểu rằng nếu có n chuồng chim bồ câu và n+1 con chim bồ câu, thì ít nhất một chuồng phải chứa ít nhất hai con chim bồ câu. Trong trường hợp này, các ngày trong năm là các "chuồng", và những người trong nhóm là các "chim bồ câu". Vì số lượng người (367) lớn hơn số lượng ngày trong năm (365), nên chắc chắn có ít nhất hai người có cùng ngày sinh.

Câu 19:

Phương trình x₁ + x₂ + x₃ = 11 có bao nhiêu nghiệm nguyên không âm?

Lời giải:

Đáp án đúng: A

Bài toán này là một bài toán tổ hợp quen thuộc: tìm số nghiệm nguyên không âm của phương trình x₁ + x₂ + x₃ = 11.

Đây là bài toán chia kẹo Euler, ta có thể áp dụng công thức số nghiệm nguyên không âm của phương trình x₁ + x₂ + ... + xₖ = n là C(n + k - 1, k - 1) hay C(n + k - 1, n).

Trong trường hợp này, n = 11 và k = 3. Vậy số nghiệm nguyên không âm là C(11 + 3 - 1, 3 - 1) = C(13, 2).

Tính C(13, 2) = 13! / (2! * 11!) = (13 * 12) / (2 * 1) = 13 * 6 = 78.

Vậy số nghiệm nguyên không âm của phương trình là 78.

Câu 20:

Có bao nhiêu chuỗi bít có độ dài nhỏ hơn hoặc bằng 6?

Lời giải:

Đáp án đúng: C

Để giải bài toán này, ta cần tính số lượng chuỗi bit có độ dài từ 0 đến 6, sau đó cộng chúng lại.

Độ dài 0: Có 1 chuỗi (chuỗi rỗng).
Độ dài 1: Có 2¹ = 2 chuỗi.
Độ dài 2: Có 2² = 4 chuỗi.
Độ dài 3: Có 2³ = 8 chuỗi.
Độ dài 4: Có 2⁴ = 16 chuỗi.
Độ dài 5: Có 2⁵ = 32 chuỗi.
Độ dài 6: Có 2⁶ = 64 chuỗi.

Vậy tổng số chuỗi là: 1 + 2 + 4 + 8 + 16 + 32 + 64 = 127. Tuy nhiên, không có đáp án nào là 127. Xem xét lại đề bài, có thể có một lỗi nhỏ. Các đáp án cho thấy có lẽ đề bài muốn hỏi số lượng chuỗi bit có độ dài nhỏ *hơn* 6 (tức là từ 0 đến 5).

Trong trường hợp đó, tổng số chuỗi sẽ là: 1 + 2 + 4 + 8 + 16 + 32 = 63. Vẫn không có đáp án đúng. Tuy nhiên, nếu đề bài bỏ qua trường hợp chuỗi rỗng (độ dài 0), thì tổng số chuỗi có độ dài từ 1 đến 6 là: 2 + 4 + 8 + 16 + 32 + 64 = 126.

Do đó, đáp án hợp lý nhất là 126, mặc dù cần lưu ý rằng cách hiểu đề bài có thể khác nhau.

Câu 21:

Cho A = {0,1,2,3,4,5,6}. Có bao nhiêu số tự nhiên gồm 5 chữ số khác nhau được thành lập từ A.

Lời giải:

Đáp án đúng: B

Số tự nhiên có 5 chữ số khác nhau được thành lập từ A = {0, 1, 2, 3, 4, 5, 6} phải thỏa mãn điều kiện: chữ số đầu tiên khác 0.

Bước 1: Chọn chữ số đầu tiên (hàng chục nghìn). Vì chữ số này phải khác 0, ta có 6 lựa chọn (1, 2, 3, 4, 5, 6).
Bước 2: Chọn 4 chữ số còn lại từ 6 chữ số còn lại (sau khi đã chọn chữ số đầu tiên). Ta có A(6,4) = 6! / (6-4)! = 6! / 2! = 6 * 5 * 4 * 3 = 360 cách chọn và sắp xếp.

Vậy, tổng số các số tự nhiên gồm 5 chữ số khác nhau được thành lập từ A là: 6 * 360 = 2160.

Câu 22:

Người ta xếp ngẫu nhiên 5 lá phiếu có ghi số thứ tự từ 1 đến 5 cạnh nhau. Có bao nhiêu cách xếp để các phiếu số chẵn luôn ở cạnh nhau?

Lời giải: