Giải sách bài tập Tin học 11 định hướng Khoa học máy tính Cánh diều bài 5: Đánh giá thuật toán
Hướng dẫn giải bài 5: Đánh giá thuật toán SBT Tin học 11 định hướng Khoa học máy tính Cánh diều mới. Đây là sách bài tập nằm trong bộ sách "Chân trời sáng tạo" được biên soạn theo chương trình đổi mới của Bộ giáo dục. Hi vọng, với cách hướng dẫn cụ thể và giải chi tiết học sinh sẽ nắm bài học tốt hơn.
Fcs17. Những phát biểu nào dưới đây là SAI?
1) O(m + n + p) = O(max(m,n,p)) với m, n, p được cho ở dữ liệu đầu vào.
2) O(2n+n2)=O(n2) với n được cho ở dữ liệu đầu vào.
3) O(n+n2+nm)=O(nm) với n được cho ở dữ liệu đầu vào.
4) O(2022) = O(1)
Hướng dẫn trả lời:
2) O(2n+n2)=O(n2) với n được cho ở dữ liệu đầu vào.
3) O(n+n2+nm)=O(nm) với n được cho ở dữ liệu đầu vào.
Fcs18. Xét bài toán: Tính tổng bình phương các số tự nhiên từ 1 đến n, với n là một số tự nhiên lớn hơn 0. Nói cách khác, tính giá trị $S=1^{2}+2^{2}+...+(n-1)^{2}+n^{2}$
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(n)
2) O(1)
Hướng dẫn trả lờ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
total = 0
for i in {i, $1\leq i \leq n$}
total += i^2
return total
2) Sử dụng công thức $S=\frac{n(n+1)(2n+1)}{6}$
return (n * (n + 1) * (2 * n + 1)) / 6
Fcs19. Xét bài toán: Cho danh sách các số nguyên A= (a1, a2, ..., an) 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(n2)
2) O(n)
Hướng dẫn trả lời:
1) Sử dụng hàm Sorted() để sắp xếp lại danh sách theo thứ tự giảm dần rồi in ra phần tử ở vị trí thứ hai
arr.sort(reverse = True)
return arr[1]
2) Khởi tạo hai biến max1 = 0 và max2 = 0 tượng trưng cho giá trị lớn thứ 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
max1 = max2 = 0
for v in arr:
if v > max1:
max2 = max1
max1 = v
elif v > max2:
max2 = v
return max2
Fcs20. Xác định độ phức tạp của đoạn chương trình sau, với giá trị N > 0 được cho ở dữ liệu đầu vào.
a, i = N, N
while (i != 0):
a -= i
i //= 2
Hướng dẫn trả lời:
Độ phức tạp: O(n)
Fcs21. Xác định độ phức tạp của đoạn chương trình sau, với giá trị n > 0 được cho ở dữ liệu đầu vào.
j = 0
for i in range(n):
while j < n:
j += 1
Hướng dẫn trả lời:
Độ phức tạp: O(n)