Hướng dẫn giải nhanh Tin học 11 định hướng Khoa học máy tính KNTT 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 hỏi: 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?

Hướng dẫn trả lời:

• Có thể

• Sơ đồ hình cây là một biểu đồ hình cây đơn giản, thường được sử dụng để minh họa quá trình giải quyết bài toán bằng phương pháp làm mịn dần. 

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.

Hướng dẫn trả lời:

sử dụng tính chất đặc biệt của hoán vị. Biết rằng một hoán vị của dãy số từ 1 đến n sẽ có các giá trị từ 1 đến n đúng một lần, tức không có giá trị lặp lại và không có giá trị bỏ sót. Có thể thiết kế thuật toán như sau:

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?

Hướng dẫn trả lời:

Có thể 

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 trả lời 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.

Hướng dẫn trả lời:

• Bước 1: Xác định đầu vào và đầu ra 

Đầu vào: Dãy số A gồm n phần tử (A[0], A[1], ..., A[n-1]).

Đầu ra: "có" nếu trong dãy A có hai phần tử trùng nhau, "không" nếu không có.

• Bước 2: Xác định giải thuật kiểm tra trùng nhau.

Duyệt qua từng phần tử của dãy A, so sánh với các phần tử trước đó trong dãy để tìm kiếm phần tử trùng nhau.

• Bước 3: Thiết kế mã nguồn chương trình.

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.

Hướng dẫn trả lời:

• Bước 1: Nhận đầu vào là xâu kí tự cần kiểm tra.

• Bước 2: Loại bỏ các ký tự không cần thiết

• Bước 3: Chuyển đổi xâu kí tự về dạng chữ thường hoặc dạng chữ hoa 

• Bước 4: Sử dụng một vòng lặp để so sánh các ký tự ở đầu và cuối xâu kí tự, sau đó di chuyển lần lượt về phía nhau.

• Bước 5: Trong quá trình lặp lại, so sánh các ký tự ở hai vị trí tương ứng với nhau. Nếu khác nhau, xâu kí tự không là đối xứng và chương trình dừng lại, trả về kết quả là "Không đối xứng".

• Bước 6: Nếu giống nhau, tiếp tục di chuyển các con trỏ về phía nhau và so sánh các ký tự tiếp theo cho đến khi hoàn thành kiểm tra toàn bộ xâu kí tự.

• Bước 7: Nếu tất cả các cặp đều giống nhau, tức là xâu kí tự là đối xứng, chương trình dừng lại và trả về kết quả là "Đối xứng".

• Bước 8: Kết thúc chương trình và đưa ra kết quả cuối cùng.

Chương trình:

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"