Quay lại giao diện cũ
Phần Tự luận (3 điểm)
Mô phỏng thuật toán sắp xếp chọn theo chiều tăng dần trên bộ số: 1, 9, 2, 3, 4, 7, 6, 2.
Hướng dẫn giải
Vòng lặp 1: Chọn phần tử nhỏ nhất là 1 (ở vị trí 0). Vì 1 đã ở vị trí đầu tiên, không cần hoán đổi gì → [1, 9, 2, 3, 4, 7, 6, 2]
Vòng lặp 2: Chọn phần tử nhỏ nhất là 2 (ở vị trí 2). Hoán đổi 9 và 2 → [1, 2, 9, 3, 4, 7, 6, 2]
Vòng lặp 3: Chọn phần tử nhỏ nhất là 2 (ở vị trí 7). Hoán đổi 9 và 2 → [1, 2, 2, 3, 4, 7, 6, 9]
Vòng lặp 4: Chọn phần tử nhỏ nhất là 3 (ở vị trí 3). Vì 3 đã ở vị trí đầu tiên của phần chưa được sắp xếp, không cần hoán đổi gì → [1, 2, 2, 3, 4, 7, 6, 9]
Vòng lặp 5: Chọn phần tử nhỏ nhất là 4 (ở vị trí 4). Vì 4 đã ở vị trí đầu tiên của phần chưa được sắp xếp, không cần hoán đổi gì → [1, 2, 2, 3, 4, 7, 6, 9]
Vòng lặp 6: Chọn phần tử nhỏ nhất trong mảng [7, 6, 9] là 6 (ở vị trí 5). Hoán đổi 7 và 6 → [1, 2, 2, 3, 4, 6, 7, 9]
Vòng lặp 7: Chọn phần tử nhỏ nhất trong mảng [7, 9] là 7 (ở vị trí 6). Vì 7 đã ở vị trí đầu tiên của phần chưa được sắp xếp, không cần hoán đổi gì → [1, 2, 2, 3, 4, 6, 7, 9]
Chọn một trong hai ngôn ngữ Python hoặc C++ để xem xét đoạn chương trình sau:
|
|
Đoạn chương trình Python |
Đoạn chương trình C++ |
|
1 2 3 4 5 6 |
N = int(input()) s = 0 if N%2 == 0: for i in range(N+1): s = s + i print(s) |
int N; cin >> N; int s = 0; if(N%2 == 0){ for(int i = 0; i <= n; i++) s = s + i; } cout << s; |
Xác định độ phức tạp thời gian của chương trình trên (với N > 0).
Hướng dẫn giải
TH1. N là số lẻ → Hiển thị luôn kết quả là 0 → T(n) = 3 → O(1).
TH2. N là số chẵn → Thực hiện vòng lặp bên trong khối lệnh IF → Vòng lặp chạy từ 0 đến N+1: \(\sum_{i=0}^ni\)→T(n) = n + 3 → O(n).
Người quản trị cần quản lí thời gian hoạt động của hai máy chủ A và B là a và b giờ. Nếu máy chủ trong ngày đó bị tấn công thì thời gian khắc phục sự cố là h và f giờ. Hãy xác định thời gian hoạt động thực của cả 2 máy trong n ngày.
Đầu vào:
- Dòng 1: số ngày hai máy hoạt động.
-
Dòng 2, 3: thời gian hoạt động và thời gian bị tấn công của máy A.
-
Dòng 4, 5: thời gian hoạt động và thời gian bị tấn công của mát B.
Đầu ra:
-
Thời gian hoạt động thực của cả 2 máy trong n ngày
|
INPUT
|
OUTPUT
|
|
5
20 20 10 21 18
20 15 11 13 13
23 19 17 22 12
20 14 11 13 09
|
44
|
Hướng dẫn giải
Dưới đây là đoạn mã mẫu:
def f(A, B, n):
total = 0
for i in range(n):
At = max(0, A[0][i] - A[1][i])
Bt = max(0, B[0][i] - B[1][i])
total += At + Bt
return total
n = 5
A = [[20, 20, 10, 21, 18],[20, 15, 11, 13, 13]]
B = [[23, 0, 17, 22, 12],[20, 14, 11, 13, 9]]
total = f(A, B, n)
print(total)