Câu hỏi:
11/07/2024 283
Xét bài toán: Cho danh sách các số nguyên 4-4, a,,..., a ) khác nhau từng đôi một. Xác định phần tử có giá trị lớn thứ hai trong danh sách A. Em hãy xây dựng thuật toán để giải quyết bài toán trên với độ phức tạp:
1) O(nlogn).
2) O(n).
Xét bài toán: Cho danh sách các số nguyên 4-4, a,,..., a ) khác nhau từng đôi một. Xác định phần tử có giá trị lớn thứ hai trong danh sách A. Em hãy xây dựng thuật toán để giải quyết bài toán trên với độ phức tạp:
1) O(nlogn).
2) O(n).
Quảng cáo
Trả lời:
1) Sắp xếp lại danh sách theo thứ tự giảm dần bằng phương pháp sắp xếp nhanh (hàm Sorted ( ) có độ phức tạp O(n.log,n )) rồi in ra phần tử ở vị trí thứ hai.
2) Khởi tạo hai biến max1 = 0 và max2 = 0 tượng trưng cho giá trị lớn thứ 0 nhất và lớn thứ hai trong danh sách A, ta tiến hành duyệt và xét lần lượt từng phần tử v của A:
Nếu max1 < v, ta cập nhật max2 = max1 và max1 = v.
Ngược lại, ta có thể suy ra max1>v(max1 không thể bằng v vì các phần tử trong danh sách A khác nhau từng đôi một). Ta so sánh max2 và v. Nếu max2 < v thì ta cập nhật max2 = v.
Hot: Học hè online Toán, Văn, Anh...lớp 1-12 tại Vietjack với hơn 1 triệu bài tập có đáp án. Học ngay
- Trọng tâm Hóa học 11 dùng cho cả 3 bộ sách Kết nối, Cánh diều, Chân trời sáng tạo VietJack - Sách 2025 ( 58.000₫ )
- Sách - Sổ tay kiến thức trọng tâm Vật lí 11 VietJack - Sách 2025 theo chương trình mới cho 2k8 ( 45.000₫ )
- Sách lớp 11 - Trọng tâm Toán, Lý, Hóa, Sử, Địa lớp 11 3 bộ sách KNTT, CTST, CD VietJack ( 52.000₫ )
- Sách lớp 10 - Combo Trọng tâm Toán, Văn, Anh và Lí, Hóa, Sinh cho cả 3 bộ KNTT, CD, CTST VietJack ( 75.000₫ )
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Lời giải
1) Dùng vòng lặp từ 1 đến n để cộng từng giá trị bình phương vào biến tổng S.
2) Dùng công thức
Lời giải
f(x) = số lượng ước số của x.
Thuật toán thô
– Tạo hàm ((-x), đếm số lượng ước số của x.
Lặp khi 1 <<n. Nếu f(x) > f(x,) thì gán x = x (x là kết quả bài toán, ban đầu x − 1).

Cải tiến:
Nhận xét: x chia hết cho i nghĩa là x = i × j, x có hai ước là i và j. Giả sử i<j thì i < sqrt(x) . Em chỉ cần kiểm tra với i không lớn hơn căn bậc hai của x, giảm được số lần lặp. Chú ý đến trường hợp x là số chính phương thì x=ixinên x chỉ có một ước.
Cải tiến hàm f(x) như sau:
Mã giả

Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.