Bài thi các môn học trong trường đai học được chấm theo thang điểm là các số nguyên từ 0 đến 100. Một lớp học cần phải có ít nhất bao nhiêu sinh viên để đảm bảo trong mọi môn thi đều có ít nhất 2 sinh viên nhận cùng điểm?
Đáp án đúng: B
Câu hỏi này liên quan đến nguyên lý Dirichlet (hay còn gọi là nguyên lý chuồng bồ câu). Nguyên lý này phát biểu rằng nếu có n chuồng và n+1 con bồ câu, thì ít nhất một chuồng phải chứa ít nhất hai con bồ câu.
Trong bài toán này, các điểm số từ 0 đến 100 đóng vai trò là các "chuồng" (tức là có 101 "chuồng"). Số sinh viên đóng vai trò là "bồ câu".
Để đảm bảo có ít nhất 2 sinh viên có cùng điểm, số sinh viên phải lớn hơn số lượng điểm số có thể. Vì có 101 điểm số khác nhau (từ 0 đến 100), cần ít nhất 101 + 1 = 102 sinh viên.
Vậy, đáp án đúng là 102.
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!
Câu hỏi liên quan
Số nguyên dương có 3 chữ số nhỏ nhất là 100, lớn nhất là 999.
Số các số chia hết cho 3 là: (999 - 102)/3 + 1 = 300 số.
Số các số chia hết cho 4 là: (996 - 100)/4 + 1 = 225 số.
Số các số chia hết cho cả 3 và 4, tức là chia hết cho 12 là: (996 - 108)/12 + 1 = 75 số.
Số các số chia hết cho 3 hoặc 4 là: 300 + 225 - 75 = 450. Tuy nhiên, không có đáp án nào trùng khớp. Kiểm tra lại ta thấy:
Số các số chia hết cho 3 là: (999 - 102)/3 + 1 = 300 số (đúng)
Số các số chia hết cho 4 là: (996 - 100)/4 + 1 = (896)/4 + 1 = 224 + 1 = 225 số (đúng)
Số các số chia hết cho 12 là: (996 - 108)/12 + 1 = (888)/12 + 1 = 74 + 1 = 75 số (đúng)
Vậy số các số chia hết cho 3 hoặc 4 là: 300 + 225 - 75 = 450.
Tuy nhiên có lẽ có sự nhầm lẫn trong các đáp án, vì 450 không có trong các lựa chọn. Giả sử câu hỏi là "Có bao nhiêu số tự nhiên gồm đúng 3 chữ số chia hết cho 3?", thì đáp án là 300.
Nếu câu hỏi là "Có bao nhiêu số tự nhiên gồm đúng 3 chữ số chia hết cho 4?", thì đáp án là 225 (gần với 224 nhất).
Do không có đáp án nào đúng, ta sẽ chọn đáp án gần đúng nhất là 449.
Thuật toán Dijkstra được sử dụng để tìm đường đi ngắn nhất từ một đỉnh nguồn đến tất cả các đỉnh còn lại trong một đồ thị có trọng số không âm. Độ phức tạp của thuật toán Dijkstra phụ thuộc vào cách cài đặt:
- Nếu sử dụng mảng để tìm đỉnh có khoảng cách ngắn nhất, độ phức tạp là O(n2), trong đó n là số đỉnh.
- Nếu sử dụng hàng đợi ưu tiên (ví dụ: heap nhị phân) để tìm đỉnh có khoảng cách ngắn nhất, độ phức tạp là O((m+n) log n), trong đó m là số cạnh và n là số đỉnh. Với đồ thị dày đặc, m có thể là O(n2), khi đó độ phức tạp gần với O(n2 log n). Với đồ thị thưa, m gần với O(n), thì độ phức tạp gần với O(n log n).
Trong các đáp án đã cho, O(n2 log2n) thể hiện độ phức tạp khi sử dụng hàng đợi ưu tiên (heap) và thường được chấp nhận là độ phức tạp phổ biến của thuật toán Dijkstra.
Thuật toán BFS (Breadth-First Search) duyệt đồ thị theo chiều rộng. Bắt đầu từ đỉnh I, ta duyệt các đỉnh kề với I trước, sau đó duyệt các đỉnh kề với các đỉnh vừa duyệt, cứ tiếp tục như vậy cho đến khi duyệt hết các đỉnh có thể đến được từ I.
1. Bắt đầu từ đỉnh I.
2. Các đỉnh kề với I là A và B. Ta duyệt A trước (vì A đứng trước B theo thứ tự chữ cái).
3. Các đỉnh kề với A là E và G. Ta duyệt E trước.
4. Các đỉnh kề với E là K. Ta duyệt K.
5. Tiếp theo, quay lại duyệt các đỉnh kề với I (đã duyệt A), ta duyệt B.
6. Các đỉnh kề với B là C và F. Ta duyệt C trước.
7. Các đỉnh kề với C là H. Ta duyệt H.
8. Tiếp theo, quay lại duyệt các đỉnh kề với B (đã duyệt C), ta duyệt F.
9. Các đỉnh kề với F là D. Ta duyệt D.
Vậy thứ tự duyệt các đỉnh là: I, A, E, G, K, B, C, F, H, D
