Bài 26: Phương pháp làm mịn dần trong thiết kế chương trình

Chủ đề 6. Kĩ thuật lập trình – Bài 26: Phương pháp làm mịn dần trong thiết kế chương trình – sách bài tập trang 79 lớp 11 Khoa học máy tính – Kết Nối Tri Thức, mời các em tham khảo cùng Bumbii.

Chủ đề 6. Kĩ thuật lập trình – Bài 26: Phương pháp làm mịn dần trong thiết kế chương trình

Câu 26.1

Mệnh đề nào sau đây mô tả đúng về phương pháp thiết kế làm mịn dần?

A. Thiết kế được chia làm nhiều bước, các bước đều độc lập hoàn toàn với nhau.

B. Thiết kế được chia làm nhiều bước, bước sau thường là chi tiết hơn, làm mịn hơn một bước ở trước đó.

C. Thiết kế được chia làm nhiều bước, bước sau thường là tổ hợp, kết hợp các kết quả của các bước trước đó.

D. Thiết kế được chia làm nhiều bước, mỗi bước sẽ tương ứng với một hàm hoặc chương trình con nào đó của bước trước.

Trả lời:

Đáp án B. Thiết kế được chia làm nhiều bước, bước sau thường là chi tiết hơn, làm mịn hơn một bước ở trước đó.

Câu 26.2

Phương pháp thiết kế làm mịn dần chính là tên gọi khác của phương pháp thiết kế từ trên xuống. Đúng hay sai?

Trả lời:

Đúng. Phương pháp thiết kế làm mịn dần chính là tên gọi khác của phương pháp thiết kế từ trên xuống.

Câu 26.3

Phát biểu sau về phương pháp làm mịn dần là đúng hay sai?

Phương pháp thiết kế làm mịn dần sẽ chia bài toán gốc thành các bài toán con, mỗi bài toán con sẽ lại được phân tích và chia thành các bài toán vấn đề con nhỏ hơn nữa. Quá trình phân rã thành các bài toán con đó sẽ còn tiếp tục cho đến khi nhận được bài toán đủ đơn giản để có thể giải ngay bằng các câu lệnh lập trình. Quá trình thiết kế đó sẽ kết thúc khi tất cả các bài toán con được giải quyết hoàn toàn.

Trả lời:

Phát biểu sau về phương pháp làm mịn dần là đúng.

Câu 26.4

Với một bài toán, chỉ có một phương pháp thiết kế làm mịn dần duy nhất. Đúng hay sai?

Trả lời:

Sai. Một bài toán có thể có nhiều phương pháp thiết kế làm mịn dần khác nhau, tùy thuộc vào cách quyết định chia nhỏ và cấu trúc các bài toán con, cũng như cách tiến hành từng bước gia công để hoàn thiện bài toán lớn hơn.

Câu 26.5

Hãy trình bày thuật toán tìm kiếm tuần tự theo phương pháp làm mịn dần.

Trả lời:

Một cách trình bày theo phương pháp làm mịn dần có thể như sau:

Bài toán: Cho trước mảng A (có n phần tử) và giá trị K. Cần tìm phần tử của A có giá trị bằng K. Nếu tìm thấy trả lại chỉ số của phần tử này (chỉ cần tìm một nghiệm), ngược lại trả về −1.

– Bước 1. Thiết lập ý tưởng thiết kế ban đầu.

– Bước 2. Chi tiết hóa dòng 1 ở trên.

– Bước 3. Chi tiết hóa dòng 2 của ý tưởng thiết kế ban đầu.

– Bước 4. Chi tiết hóa dòng 3 của ý tưởng thiết kế ban đầu.

Chương trình hoàn chỉnh:

def LinearSearch(A):
    for i in range(A):
        if A[i] == K:
            return i
return -1

Câu 26.6

Hãy trình bày thuật toán sắp xếp chọn theo phương pháp làm mịn dần.

Trả lời:

Một cách trình bày theo phương pháp làm mịn dần có thể như sau.

Bài toán: Cho trước dãy A có n phần tử. Cần sắp xếp dãy A theo thứ tự tăng dần theo thuật toán chọn.

– Bước 1. Phân tích và ý tưởng thiết kế ban đầu.

Ý tưởng ban đầu của thuật toán này như sau:

Với mỗi phần tử của dãy, cần thiết lập vị trí chính xác của vị trí này trong dãy sao cho phía bên trái vị trí này bao gồm các phần tử đã đứng đúng vị trí.

Để thực hiện được ý tưởng trên, cách làm ban đầu là chọn ra phần tử đúng đó và đổi chỗ cho phần tử tại vị trí hiện thời. Từ đó dẫn đến việc phân rã bài toán như sau:

– Bước 2: Chi tiết hóa dòng 1 trong thiết kế trên

– Bước 3: Chi tiết hoả công việc tại dòng 2.

Để tìm được phần tử nhỏ nhất bên phải vị trí i và sau đó đổi chỗ cho vị trí i chúng ra sẽ tìm vị trí đó thông qua chỉ số. Kết quả của bước này như sau:

– Bước 4. Chi tiết hoá dòng 5 của thiết kế trên. Việc đổi chỗ hai phần tử trong dãy được thực hiện bằng lệnh sau trong Python:

Kết quả cuối cùng thu được thuật toán sắp xếp chọn như sau:

def selectionSort(A):
    n = len(A)
    for i in range(n-1):
        iMin = i
    for j in range(i+1,n):
        if A[j] < A[iMin]:
            iMin = j
    A[i],A[iMin] = A[iMin], A[i]

Câu 26.7*

Hãy trình bày thuật toán sắp xếp nổi bọt theo phương pháp làm mịn dần.

Trả lời:

Một cách trình bày theo phương pháp làm mịn dần có thể như sau:

Bài toán: Cho trước dãy A có n phần tử. Cần sắp xếp dãy A theo thứ tự tăng dần theo thuật toán nổi bọt.

– Bước 1. Phân tích và ý tưởng thiết kế ban đầu.

Ý tưởng chính của thuật toán sắp xếp chèn là liên tục đổi chỗ hai phần tử cạnh nhau nếu chúng được sắp xếp không đúng, ví dụ nếu A[i] > A[i + 1] thì cần đổi chỗ hai phần tử này. Như vậy có thể thiết kế một ý tưởng như sau:

– Bước 2. Chi tiết hoá công việc mô tả trong dòng lệnh 2 ở trên.

Ý tưởng ban đầu là cần duyệt phần tử từ thứ nhất đến phần tử gần cuối cùng, kiếm tra phần tử đang duyệt và phần tử sau đó, nếu sắp xếp không đúng thì đổi chỗ. Vậy có thể hình dung dòng lệnh 2 ở trên được thể hiện như sau:

Quan sát kĩ hơn chúng ta thấy sau lệnh trên thì phần tử lớn nhất của dãy đã được di chuyển về cuối dãy, tức là phần tử này đã nằm đúng vị trí. Do đó trong vòng lặp tiếp theo thì không cần duyệt cả vòng lặp mà chỉ duyệt tới phần tử có chỉ số n – 3, tức là tại vòng duyệt tiếp theo chỉ cần thực hiện:

Tổng quát, ở vòng duyệt thứ k thi công việc tại dòng 2 ở trên có thể viết như sau:

– Bước 3: Chúng ta quay lại chi tiết hoá dòng 1 của chương trình tại B1.

Theo cách phân tích của bước 2 thì tại dòng 1 chỉ cần lặp đúng n – 1 lần thi dãy sẽ được sắp xếp xong. Như vậy dòng 1 có thể biểu diễn bằng lệnh Python:

Với mỗi i ở vòng lặp trên thì số thứ tự lần lặp sẽ là i+1 (do vòng lặp trên bắt đầu từ 0), do đó phải thay k ở dòng phía dưới (xem B2) bằng i + 1. Như vậy chúng ta có:

– Bước 4: Cuối cùng chúng ta sẽ chi tiết hoá công việc tại dòng 3 của chương trình trên và thu được phiên bản hoàn chỉnh của thuật toán sắp xếp nổi bọt.