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

120

Với giải Câu Fcs19 trang 52 SBT Tin học 11 Cánh diều chi tiết trong Bài 5: Đánh giá thuật toán giúp học sinh dễ dàng xem và so sánh lời giải từ đó biết cách làm bài tập trong SBT Tin học 11. Mời các bạn đón xem:

Giải SBT Tin học 11 Bài 5: Đánh giá thuật toán

Câu Fcs19 trang 52 SBT Tin học 11Xé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).

Lời giả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.

Đánh giá

0

0 đánh giá