Lý thuyết Tin học 11 Bài 26 (Kết nối tri thức): Phương pháp làm mịn dần trong thiết kế chương trình

Lý thuyết Tin học 11 Bài 26: Phương pháp làm mịn dần trong thiết kế chương trình

A. Lý thuyết Phương pháp làm mịn dần trong thiết kế chương trình

1. Phương pháp thiết kế làm mịn dần

- Bài toán gốc: Cho trước dãy số A: A[0], A[ 1], ..., A[n-1]. Cần tiến hành sắp xếp dãy phải nhận được là trên theo thứ tự tăng dần. Kết quả phải nhận được: A[0] ≤ A[1] ≤ ... ≤ A[n-1]

- Ví dụ với bộ dữ liệu đầu vào là dãy [2, 1,7,10,4] thì kết quả thu được dãy [1,2,4,7,101. Quá trình phân tích, thiết kế được mô tả theo các bước sau.

a) Tìm hiểu bài toán

- Bài toán gốc là cho trước dãy A, cần sắp xếp lại dãy này theo thứ tự tăng dần.

b) Thiết kế chương trình giải bài toán

* Việc thiết kế chương trình giải bài toán được chia thành nhiều bước:

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

+ Ý tưởng ban đầu của thuật toán là duyệt từ phần tử thứ hai đến phần tử cuối của dãy để sắp xếp dãy.

+ Sử dụng vòng lặp với biến i chạy từ chỉ số 1 đến n-1.

+ Thực hiện các thao tác để bổ sung A[i] vào dãy các phần tử đã được sắp xếp A[0], A[1]..., A[i-1].

- Bước 2: Thực hiện việc "Chèn A[i] vào đúng vị trí."

+ Lấy phần tử A[i] ra và chuyển các phần tử bên trái A[i] nhưng có giá trị lớn hơn A[i] sang phải.

+ Đặt A[i] vào vị trí trống.

- Bước 3: Nhấc A[i] lên bằng cách tạo biến value để lưu giá trị A[i].

- Bước 4: Chuyển các phần tử bên trái A[i] và lớn hơn A[i] sang phải.

+ Thiết lập biến j = i - 1 là chỉ số của phần tử ngay bên trái A[i].

+ Liên tục so sánh A[j] với value, nếu A[j] > value thì chuyển A[j] sang phải một vị trí bằng lệnh A[j+1] = A[j] và giảm j = j - 1.

+ Quá trình kết thúc khi đi hết bên trái của dãy hoặc A[j] <= value.

- Bước 5: Chèn A[i] vào đúng vị trí trống.

+ Vị trí j+1 là vị trí trống cần chèn.

+ Chèn phần tử A[i] (giá trị được lưu trong value) vào vị trí j+1 bằng câu lệnh A[j+1] = value.

- Quá trình thiết kế kết thúc sau khi chi tiết hoá bằng các câu lệnh tất cả các thao tác được mô tả trong các bước trên.

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

Chương trình giải bài toán đặt ra được thiết kế hoàn chỉnh dưới dạng hàm InsertionSort(A). Tổng hợp các bước trên chúng ta có chương trình hoàn chỉnh như sau:

Quá trình thiết kế chương trình sắp xếp chèn đã trải qua nhiều bước, mỗi bước làm mịn dần các phân tích của bước trước đó.

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

- Bài toán: Cho trước dãy số A: A[0], A[ 1], ..., A[n-1]. Cặp phần tử A[i], A[j] được gọi là nghịch đảo nếu i < j nhưng A[i] > A[j]. Cần viết chương trình đếm số các cặp nghịch đảo của dãy A. Ví dụ dãy 3, 4, 2, 1 sẽ có 5 cặp nghịch đảo là (3,2), (3, 1), (4,2), (4,1), (2,1). Thiết kế theo phương pháp làm mịn dần

a) Tìm hiểu bài toán

Bài toán gốc là cho trước dãy số A có n phần tử, cần đếm số các cặp phần tử nghịch đảo của A.

b) Thiết kế chương trình giải bài toán

Chúng ta sẽ thiết kế lời giải bài toán theo phương pháp làm mịn dần.

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

+ Bài toán đếm các cặp chỉ số nghịch đảo của dãy A.

+ Chương trình sẽ trả về số lượng các cặp số nghịch đảo.

+ Cần tìm tất cả các cặp chỉ số (i, j) có thể tạo cặp nghịch đảo A[i], A[j], sau đó kiểm tra xem cặp này có là nghịch đảo không.

- Bước 2: Tìm tất cả các cặp chỉ số (ij).

+ Thiết lập 2 vòng lặp theo i, j để tìm.

+ Tìm các chỉ số i chạy từ 0 đến n-2, chỉ số j chạy từ i+1 đến n-1 để tiết kiệm thời gian.

- Bước 3: Kiểm tra tính nghịch đảo của cặp (i)).

+ Cặp (i, j) sẽ là nghịch đảo khi A[i] > A[j].

+ Điều kiện i < j đã được đảm bảo tại bước 2.

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

Trên cơ sở các phân tích trên chúng ta có thể thiết lập hàm Nghichdao(A) để đếm số các cặp nghịch đảo của dãy A cụ thể như sau:

Sơ đồ tư duy Phương pháp làm mịn dần trong thiết kế chương trình

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

Câu 1: Mô tả thuật toán pha trà mời khách

+ B1: Tráng ấm, chén bằng nước sôi

+ B2: Rót nước sôi vào ấm và đợi khoảng 3 đến 4 phút.

+ B3: Cho trà vào ấm

+ B4: Rót trà ra chén để mời khách.

A. B1- B3-B4- B2

B. B1- B3- B2-B4

C. B2-B4-B1-B3

D. B3-B4-B1-B2

Câu 2: Hãy cho biết kết quả sau khi thực hiện thuật toán sau:

Bước 1. Tam←x;

Bước 2. x←y;

Bước 3. y← tam;

A. Giá trị của biến x bằng giá trị của biến y

B. Hoán đổi giá trị hai biến x và y

C. Giá trị của biến y bằng giá trị của biến x

D. Khác

Câu 3: Quá trình giải bài toán trên máy tính gồm mấy bước?

A. 2

B. 3

C. 4

D. 5

Câu 4: Thứ tự các bước giải bài toán trên máy tính:

A. Xác định bài toán → Viết chương trình → Mô tả thuật toán

B. Xác định bài toán → Mô tả thuật toán → Viết chương trình

C. Mô tả thuật toán → Xác định bài toán → Viết chương trình

D. Viết chương trình → Xác định bài toán → Mô tả thuật toán

Câu 5: Hãy xác đinh bài toán sau: "Tìm số lớn nhất trong dãy n số tự nhiên cho trước"?

A. INPUT: Dãy n số tự nhiên. OUTPUT: Số lớn nhất trong dãy n số.

B. INPUT: Dãy n số tự nhiên. OUTPUT: Số các số lớn nhất trong dãy n số.

C. INPUT: Số lớn nhất trong dãy n số. OUTPUT: Dãy n số tự nhiên.

D. INPUT: Số các số lớn nhất trong dãy n số. OUTPUT: Dãy n số tự nhiên.

Câu 6: Hãy chọn phát biểu Đúng:

A. Các bước giải bài toán trên máy tính là: Mô tả thuật toán → Xác định bài toán → Viết chương trình

B. Cần phải xác định bài toán trước khi giải bài toán trên máy tính

C. Máy tính có hiểu được chương trình viết bằng ngôn ngữ tự nhiên

D. Với mỗi bài toán cụ thể, phải lựa chọn ngôn ngữ lập trình phù hợp rồi mới xây dựng thuật toán giải bài toán đó

Câu 7: Xác định bài toán: “ kiểm tra n có phải là số nguyên tố hay không? ”

A. Input: Nhập số n; Output: n là số nguyên tố hoặc n không là số nguyên tố

B. Input: n là số nguyên tố hoặc n không là số nguyên tố; Output: Nhập số n

C. Input: n là số nguyên tố; Output: Nhập số n

D. Input: Nhập số n; Output: n là số nguyên tố

Câu 8: Thuật toán là:

A. Dãy các thao tác cần thực hiện theo 1 trình tự xác định để thu được kết quả cần thiết từ những điều kiện cho trước.

B. Một thao tác cần thực hiện để thu được kết quả cần thiết từ những điều kiện cho trước.

C. Dãy các thao tác cần thực hiện để thu được kết quả cần thiết từ những điều kiện cho trước.

D. Tất cả đều sai

Câu 9: Hãy chọn phát biểu Sai?

A. Việc thực hiện cả 3 bước khi giải bài toán trên máy tính là cần thiết, nhất là đối với bài toán phức tạp

B. Xác định bài toán là xác định rõ các điều kiện cho trước và kết quả cần thu được

C. Dãy hữu hạn các thao tác cần thực hiện để giải một bài toán được gọi là thuật toán

D. Đối với mỗi bài toán cụ thể chúng ta chỉ có 1 thuật toán duy nhất để giải bài toán đó trên máy tính

Câu 10: Mô tả thuật toán là:

A. Liệt kê các bước thực hiện công việc.

B. Liệt kê các cách thực hiện công việc.

C. Liệt kê một bước thực hiện công việc.

D. Tất cả đều đúng

Trắc nghiệm Tin học 11 Bài 26: Phương pháp làm mịn dần trong thiết kế chương trình

Câu 1: Phương pháp làm mịn dần trong thiết kế chương trình là gì?

A. Phương pháp làm giảm số lượng mã lệnh trong chương trình

B. Phương pháp chi tiết hóa các bước từ ý tưởng tổng quan đến từng hành động cụ thể

C. Phương pháp kiểm tra lỗi sau khi viết xong chương trình

D. Phương pháp tổ chức dữ liệu theo thứ tự tăng dần

Câu 2: Khi thiết kế chương trình theo phương pháp làm mịn dần, bước đầu tiên cần thực hiện là gì?

A. Xác định đầu vào và đầu ra của bài toán

B. Viết toàn bộ chương trình

C. Kiểm tra lỗi

D. Thực hiện từng thao tác cụ thể

Câu 3: Trong thuật toán sắp xếp chèn, tại bước đầu tiên của thiết kế, công việc nào được thực hiện?

A. Tạo biến mới để lưu giá trị cần chèn

B. Duyệt từ phần tử thứ hai đến phần tử cuối của dãy

C. Sắp xếp các phần tử theo thứ tự giảm dần

D. Tạo danh sách mới từ danh sách cũ

Câu 4: Trong bước làm mịn "Chèn A[i] vào đúng vị trí", thao tác nào dưới đây là đúng?

A. So sánh A[i] với tất cả phần tử trong dãy

B. So sánh A[i] với các phần tử bên phải của nó

C. Chuyển các phần tử lớn hơn A[i] sang phải

D. Chèn A[i] vào vị trí đầu tiên của dãy

Câu 5: Sau khi chèn một phần tử vào vị trí đúng trong dãy sắp xếp chèn, ta có thể khẳng định gì?

A. Dãy đã hoàn toàn sắp xếp

B. Các phần tử từ A[0] đến A[i] đã được sắp xếp

C. Các phần tử từ A[i] đến A[n-1] đã được sắp xếp

D. Chỉ phần tử A[i] được sắp xếp

Câu 6: Trong chương trình đếm số cặp nghịch đảo, điều kiện kiểm tra nghịch đảo của cặp (i, j) là gì?

A. A[i] < A[j]

B. i > j

C. A[i] > A[j] và i < j

D. A[i] = A[j]

Câu 7: Câu lệnh nào dùng để thiết lập biến value lưu trữ giá trị của A[i] trong sắp xếp chèn?

A. value = A[i]

B. value = A[j+1]

C. A[i] = value

D. A[j+1] = value

Câu 8: Phương pháp làm mịn dần trong thiết kế chương trình giúp gì cho lập trình viên?

A. Tăng tốc độ chạy chương trình

B. Giảm dung lượng bộ nhớ chương trình

C. Làm rõ từng bước của chương trình, dễ dàng chuyển ý tưởng thành câu lệnh

D. Tự động phát hiện lỗi cú pháp

Câu 9: Trong chương trình đếm số cặp nghịch đảo, tại sao vòng lặp thứ hai chỉ duyệt từ i + 1 đến n - 1?

A. Để tiết kiệm thời gian và tránh lặp lại các cặp đã kiểm tra

B. Vì chỉ số j phải lớn hơn chỉ số i

C. Để kiểm tra mọi phần tử trong dãy

D. Vì cặp (i, j) không quan trọng

Câu 10: Sau khi hoàn thành phương pháp làm mịn dần, kết quả cuối cùng là:

A. Một chương trình hoàn chỉnh với các bước chi tiết

B. Một thuật toán tổng quan mà không có mã lệnh cụ thể

C. Chỉ là một ý tưởng thiết kế ban đầu

D. Một báo cáo về quá trình thiết kế

PHẦN II. Câu trắc nghiệm đúng sai. Thí sinh trả lời từ câu 1 đến câu 2. Trong mỗi ý a), b), c), d) ở mỗi câu, thí sinh chọn đúng hoặc sai

Câu 1: Khi thiết kế chương trình theo phương pháp làm mịn dần, bước đầu tiên thường là:

a) Viết mã hoàn chỉnh ngay từ đầu.

b) Tìm hiểu yêu cầu bài toán, xác định đầu vào và đầu ra của bài toán.

c) Chia bài toán thành các phần nhỏ và tiến hành làm mịn từng phần.

d) Thực hiện từng bước chi tiết theo thứ tự mà không cần phân tích tổng thể.

Câu 2: Trong phương pháp làm mịn dần, khi thiết kế thuật toán sắp xếp chèn, bước nào sau đây là đúng?

a) Đầu tiên, chèn phần tử A[i] vào đúng vị trí rồi mới tiến hành duyệt các phần tử còn lại.

b) Tạo biến value lưu phần tử đang xét, sau đó dịch chuyển các phần tử lớn hơn value sang phải.

c) Chỉ cần kiểm tra điều kiện A[i] < A[j] để xác định vị trí chèn phần tử.

d) Thực hiện tất cả các thao tác trên cùng một dòng lệnh để tăng hiệu suất.

PHẦN III. Câu trả lời ngắn. Thí sinh trả lời từ câu 1 đến câu 3

Câu 1: Phương pháp làm mịn dần trong thiết kế chương trình được thực hiện như thế nào?

Câu 2: Tại sao cần chia nhỏ quy trình thiết kế chương trình thành các bước cụ thể hơn ở phương pháp làm mịn dần?

Câu 3: Khi thiết kế thuật toán sắp xếp chèn, làm thế nào để xác định vị trí đúng cho phần tử cần chèn?

Xem thêm các bài lý thuyết Tin học 11 sách Kết nối tri thức hay, chi tiết tại:

Lý thuyết Bài 21: Các thuật toán sắp xếp đơn giản

Lý thuyết Bài 23: Kiểm thử và đánh giá chương trình

Lý thuyết Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Lý thuyết Bài 28: Thiết kế chương trình theo Mô đun

Lý thuyết Bài 30: Thiết lập thư viện cho chương trình

Xem thêm tài liệu Tin học lớp 11:

Giải Tin học 11 Bài 26: Phương pháp làm mịn dần trong thiết kế chương trình

Giải SBT Tin học 11 Bài 26: Phương pháp làm mịn dần trong thiết kế chương trình