MỞ ĐẦU

Câu 1: Em đã biết thiết kế một số thuật toán và chương trình: tìm kiếm tuần tự, tìm kiếm nhị phân, sắp xếp chèn, sắp xếp chọn, sắp xếp nổi bọt. Tất cả các thiết kế chương trình đó có điểm nào chung?

Theo em, để thiết kế một thuật toán đúng giải một bài toán cho trước cần trải qua các bước như thế nào? Nêu quan điểm của riêng em và trao đổi với các bạn.

Trả lời:

• Chi tiết hóa các bước lập trình

1. Xác định bài toán

2. Tìm cấu trúc dữ liệu biểu diễn thuật toán.

3. Tìm Thuật toán.

4. Lập trình 

5. Kiểm thử 

6. Tối ưu 

1. PHƯƠNG PHÁP THIẾT KẾ LÀM MỊN DẦN

Hoạt động 1. Tìm hiểu các bước thiết kế làm mịn dần

Câu 1: Cùng trao đổi, thảo luận các bước thiết kế chương trình theo thuật toán sắp xếp chèn, từ đó đưa ra phương pháp chính khi thiết kề chương trình. Sau mỗi bước thiết kế cần trao đổi và trả lời các câu hỏi sau:

1. Bước này đã thực hiện được công việc gì?

2. Kết quả vừa thực hiện với kết quả của bước trước đó khác nhau như thế nào?

Trả lời:

1. Định nghĩa cách thức sắp xếp chèn, gồm cách thức so sánh và di chuyển các phần tử để đưa phần tử mới vào vị trí đúng của dãy con đã được sắp xếp trước đó.

2. Cách thức sắp xếp chèn được định nghĩa và thực hiện. Bước này tập trung định nghĩa và triển khai thuật toán sắp xếp chèn cụ thể, bước trước đó có thể là các bước chuẩn bị dữ liệu, định nghĩa bài toán, hoặc thiết kế các thuật toán phụ trợ khác.

Câu hỏi

Câu 1: Trong các bước đã thực hiện của bài toán sắp xếp chèn ở trên, bước nào là đơn giản nhất theo nghĩa có thể thực hiện ngay bảng các lệnh lập trình.

Trả lời:

Quá trình di chuyển các phần tử để đưa phần tử mới vào vị trí đúng của dãy con đã được sắp xếp trước đó.

Câu 2: Nếu bài toán đặt ra là sắp xếp dãy A theo thứ tự giảm dần thì các bước thiết kế như trên có cần thay đổi không? Thay đổi như thế nào?

Trả lời:

Cần

def Insertionsort(A):

 n=len(A)

 for i in range(1,n):

  value=A[i]

 j=i-1

 while j>=0 and A[j]<value:

  A[j+1]=A[j]

  j=j-1

 A[j+1]=value

2. THIẾT KẾ CHƯƠNG TRÌNH BẰNG PHƯƠNG PHÁP LÀM MỊN DẦN

Hoạt động 2. Thiết kế chương trình bằng phương pháp làm mịn dần

Câu 1: Thực hiện thiết kế thuật toán và chương trình bằng phương pháp làm mịn dần theo các bài toán sau. Trao đổi, thảo luận với bạn bè để thiết lập được lời giải tốt hơn.

Trả lời:

def nghichdao(A):

 n = len(A)

 count = 0

 for i in range(n-1):

  for j in range(i+1, n):

   if A[i] > A[j]:

    count = count + 1

 return count

Câu hỏi

Câu 1: Với Bài toán 1 có thể tách các dòng lệnh từ 4 đến 9 thành một hàm con độc lập được không?

Trả lời:

Có thể 

Câu 2: Trong thiết kế bài toán tìm các cặp phần tử nghịch đảo, các bước sau đã thực hiện những thay đổi quan trọng nào so với bước trước đó?

Trả lời:

Bước thực hiện có thể được thực hiện theo nhiều cách khác nhau và tùy thuộc vào cách tiếp cận của người lập trình. Giả sử trong Python:

• Tạo danh sách các số nguyên cần tìm các cặp phần tử nghịch đảo.

• Tạo danh sách trống để lưu các cặp tìm được.

• Duyệt qua từng phần tử trong danh sách các số nguyên, cho vào một vòng lặp trong đó duyệt qua các phần tử còn lại của danh sách.

• Kiểm tra xem tích của mỗi cặp phần tử có bằng 1 không. Nếu có, thêm cặp phần tử này vào danh sách chứa các cặp phần tử nghịch đảo.

Thay đổi có thể được thực hiện: sử dụng thuật toán tìm kiếm nhị phân để tìm các cặp phần tử nghịch đảo thay vì duyệt qua từng phần tử hoặc sử dụng một thư viện bên ngoài như numpy để thực hiện tính toán và tìm kiếm các cặp phần tử nghịch đảo. 

LUYỆN TẬP

Câu 1: Phát biểu sau đúng hay sai?

Khi thiết kế chương trình thì việc đầu tiên là tìm hiểu yêu cầu chung của bài toán, xác định đầu vào, đầu ra của bài toán, sau đó mới đi cụ thể vào chi tiết.

Trả lời:

Đúng. 

Hiểu rõ yêu cầu chung của bài toán, giúp định hướng rõ ràng cho quá trình thiết kế, đảm bảo rằng chương trình được xây dựng đúng theo yêu cầu của bài toán và đáp ứng được yêu cầu của người dùng. Việc đúng đắn từ đầu sẽ giúp tiết kiệm thời gian và nguồn lực trong quá trình phát triển chương trình.

Câu 2: Sử dụng thiết kế của Bài toán 2, tìm tất cả các cặp nghịch đảo của dãy: 3, 2, 1, 5, 4.

Trả lời:

 (3,2), (3,1), (3,5), (3,4), và (2,1)

VẬN DỤNG

Câu 1: Sử dụng phương pháp làm mịn dần để giải bài toán sau: Cho trước số tự nhiên không âm n, viết chương trình kiểm tra xem số n có phải là số nguyên tố hay không? Chương trình cần thông báo "CÓ" nếu n là số nguyên tế, ngược lại thông báo "KHÔNG".

Trả lời:

def is_prime(n):

 if n <= 1:

  return "KHÔNG"# Trường hợp n <= 1 không phải số nguyên tố

 elif n <= 3:

  return "CÓ"# Trường hợp n = 2 hoặc n = 3 là số nguyên tố

 elif n % 2 == 0:

  return "KHÔNG"# Trường hợp n chẵn lớn hơn

Câu 2: Với thuật toán sắp xếp chèn, chứng minh rằng nếu thay toàn bộ phần Chèn A[i] vào vị trị đúng của dãy con A[@), A[l], ..., A[i - 1]> bằng các lệnh sau thì chương trình vẫn đứng:

Trả lời:

Để chứng minh tính đúng đắn, cần chứng minh:

• Điều kiện ban đầu (trước khi bắt đầu vòng lặp): Sau khi thực hiện lệnh j = 1, giá trị của j đang là 1, và dãy con A[0] chỉ gồm một phần tử là A[0] (vì j-1 là 0): sắp xếp đúng.

• Điều kiện duy trì (trong quá trình vòng lặp): Trong mỗi vòng lặp của while, nếu A[j] < A[j-1], ta hoán đổi giá trị của A[j] và A[j-1] bằng lệnh Đổi chỗ A[j] và A[j-1]. Sau đó, ta giảm giá trị của j đi 1 đơn vị bằng lệnh j = j - 1. Lúc này, giá trị của A[j] là giá trị của A[j-1] trước khi hoán đổi, và giá trị của A[j-1] là giá trị của A[j] trước khi hoán đổi: dãy con A[0], A[1], ..., A[j-1] đã được sắp xếp đúng sau mỗi vòng lặp.

Vậy nên, dãy con A[0], A[1], ..., A[j-1] luôn được sắp xếp đúng sau mỗi vòng lặp của while, và dãy con này sẽ không bị thay đổi giá trị trong quá trình hoán đổi.