BÀI 27 - THỰC HÀNH THIẾT KẾ CHƯƠNG TRÌNH THEO PHƯƠNG PHÁP LÀM MỊN DẦN

MỞ ĐẦU

Câu 1: Phương pháp làm mịn dần là một trong các cách tiếp cận tổng quát khi giải quyết các bài toán cụ thể. Em có thể sử dụng sơ đồ hình cây để mô tả phương pháp này không?

Giải nhanh:

Phương pháp làm mịn dần là một trong các cách tiếp cận tổng quát để giải quyết các bài toán cụ thể. Sơ đồ hình cây là một công cụ hữu ích để mô tả phương pháp này.

LUYỆN TẬP

Câu 1: Thiết kế thuật toán cho nhiệm vụ 1 với ý tưởng khác như sau: Dãy A là một hoán vị của dãy các số từ 1 đến n khi và chỉ khi dãy A có độ dài n và mọi số i từ 1 đến n đều nằm trong A.

Giải nhanh:

function kiemTraHoanVi(a):

 n = len(a)

 visited = [False] * n

 # Kiểm tra độ dài của dãy a

 if n != len(set(a)):

  return "KHÔNG"

 # Duyệt qua từng phần tử trong dãy a

 for i in a:

  # Nếu số i đã xuất hiện trong dãy a

  if i < 1 or i > n or visited[i-1]:

   return "KHÔNG"

  visited[i-1] = True

 # Kiểm tra mảng visited

 if all(visited):

  return "CÓ"

 else:

  return "KHÔNG"

Câu 2: Trong Nhiệm vụ 2, nếu dãy A đã được sắp xếp theo thứ tự tăng dần thì có thể cải tiến thuật toán tốt hơn được không?

Giải nhanh:

Nếu dãy A đã được sắp xếp theo thứ tự tăng dần thì có thể cải tiến thuật toán tốt hơn.

VẬN DỤNG

Câu 1: Cho dãy số A = A[0], A[1]. .... A[n - 1]. Thiết kế và viết chương trình kiểm tra trong dãy A có hai phân tử nào trùng nhau hay không. Cần đưa ra câu Giải nhanh là “có” hay “không”. Yêu cầu đưa ra quy trình thiết kế theo phương pháp làm mịn dần.

Giải nhanh:

def check_duplicate(A):

 for i in range(len(A)):

  for j in range(i + 1, len(A)):

   if A[i] == A[j]:

    return "có"

 return "không"

# Đầu vào: Dãy số A

A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

# Gọi hàm để kiểm tra

result = check_duplicate(A)

# Đầu ra: Kết quả kiểm tra

print(result)

Câu 2: Xâu kí tự được gọi là đối xứng nêu thay đổi thứ tự ngược lại các kí tự của xâu thì vẫn nhận được dãy ban đầu. Ví dụ xâu “abcdcba" là đối xứng, còn xâu “1011” không là đối xứng. Thiết kế và viết chương trình kiểm tra một xâu kí tự cho trước có là đối xứng hay không. Yêu cầu đưa ra quy trình thiết kế theo phương pháp làm mịn dần.

Giải nhanh:

def kiem_tra_doi_xung(xau):

 # Loại bỏ các kí tự không cần thiết và chuyển đổi xâu về dạng chữ thường

 xau = xau.replace(" ", "").lower()

 n = len(xau)

 # Sử dụng vòng lặp để kiểm tra từ đầu và cuối xâu kí tự

 for i in range(n // 2):

  if xau[i] != xau[n - i - 1]:

   return "Không đối xứng"

 return "Đối xứng"