Tìm các số nguyên không vượt quá 100 hoặc là bình phương hoặc là lập phương của một số nguyên?
Đáp án đúng: D
Để giải bài toán này, ta cần tìm các số nguyên không vượt quá 100 mà nó là bình phương hoặc lập phương của một số nguyên nào đó.
- Các số chính phương không vượt quá 100 là: 0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100 (tổng cộng 11 số)
- Các số lập phương không vượt quá 100 là: 0, 1, 8, 27, 64 (tổng cộng 5 số)
Tuy nhiên, ta thấy các số 0, 1, 64 xuất hiện ở cả hai dãy, do đó để đếm số các số thỏa mãn yêu cầu, ta cần loại bỏ các số trùng lặp này.
Số lượng các số thỏa mãn là: 11 + 5 - 3 = 13
Vậy có tổng cộng 13 số nguyên không vượt quá 100 hoặc là bình phương hoặc là lập phương của một số nguyên.
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
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.
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.
