1. Kiểm tra hoán vị
🔻Bài toán: Cho trước một dãy n số, kiểm tra dãy đã cho có phải là một hoán vị của dãy số 1, 2, 3,..., n. Thông báo kết quả là CÓ hoặc KHÔNG.
📝Hướng dẫn thiết kế
Bước 1. Nếu dãy A là hoán vị thì các phần tử có vị trí khác so với dãy gốc.
1. Sắp xếp dãy A theo thứ tự tăng dần.
2. Kiểm tra A có là dãy 1, 2,..., n hay không?
Bước 2. Sắp xếp dãy A bằng thuật toán sắp xếp theo chiều tăng dần.
1. def sapxep(A):
2. for i in range(len(A)):
3. j = i
4. while j > 0 and A[j] < A[j-1]:
5. A[j], A[j-1] = A[j-1], A[j]
6. j = j - 1
Bước 3. Kiểm tra dãy vừa sắp xếp có là dãy 1, 2, 3,..., n?
1. sapxep(A)
2. kq = True #giả sử A là hoán vị
3. for i in range(len(A)):
4. if A[i] != i+1:
5. kq = False # nếu một phần tử không khớp thì A không là hoán vị
6. break
7. return kq
Bước 4. Hoàn thiện hàm kiểm tra hoán vị
def kt_hoanvi(A):
sapxep(A)
kq = True #giả sử A là hoán vị
for i in range(len(A)):
if A[i] != i+1:
kq = False # nếu một phần tử không khớp thì A không là hoán vị
break
return kq
@204215760852@
2. Đếm số lần lặp
🔻Bài toán: Cho trước một dãy A có n số, đếm số lần xuất hiện của ai trong dãy. Biết B[k] = số lần A[k] xuất hiện trong A. Ví dụ, A = [2, 1, 1, 3, 5, 10, 2, 5] thì B = [2, 2, 2, 1, 2, 1, 2, 2].
📝Hướng dẫn thiết kế
Bước 1. Hai dãy A và B cùng kích thước, có mối liên hệ là B[k] = số lần A[k] xuất hiện trong A.
1. Thiết lập dãy B rỗng.
2. for i in range(len(A)):
3. Tính số lần lặp của A[i].
4. Bổ sung giá trị này vào B.
5. Trả về dãy B.
Bước 2. Chuyển thao tác đơn trực tiếp thành câu lệnh.
1. B = []
2. for i in range(len(A)):
3. Tính số lần lặp của A[i].
4. Bổ sung giá trị này vào B.
5. return B
Bước 3. Tính số lần lặp của A[i] trong A.
1. def lap(x, A):
2. S = 0
3. for a in A:
4. if a == x:
5. S = S + 1
6. return S
Bước 4. Vì hàm lap(x, A) trả ra kết quả là số lần xuất hiện của A[i] nên có thể gộp với dòng 4 trong Bước 2 như sau. Bổ sung các thành phần còn thiếu để thu được hàm hoàn chỉnh.
1. def tinh_lap(A):
2. B = []
3. for i in range(len(A)):
4. B.append(lap(A[i], A))
5. return B
@204215821723@@204215825307@
Bạn có thể đánh giá bài học này ở đây