Câu hỏi:
13/07/2024 410Quảng cáo
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:
1 Lặp cho đến khi dãy ban đầu đã được sắp xếp đúng
2 Duyệt 1 lượt phần tử từ trái sang phải nếu 2 phần tử cạnh nhau sắp xếp không đúng chỗ thì đổi chỗ 2 phần tử này.
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: for j in range(n-1): # n là số phần tử của dãy.
nếu A[j] > A[j+1] thì đổi vị trí A[j] và A[j+1]
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:
for j in range(n-2): # n là số phần tử của dãy.
nếu A[j] > A[j+1] thì đổi vị trí A[j] và A[j+1]
Tổng quát, ở vòng duyệt thứ k thì công việc tại dòng 2 ở trên có thể viết như sau:
1 for j in range(n-k): # n là số phần tử của dãy.
2 nếu A[j] > A[j+1] thì đổi vị trí A[j] và A[j+1]
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 thì 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: for i in range(n - 1):
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ó:
1 for i in range(n-1):
2 for j in range(n-i-1):
3 Nếu A[j] > A[j+1] thì đổi chỗ A[j],A[j+1]
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.
1 def bubbleSort (A)
2 n = len(A)
3 for i in range(n-1):
Hot: Học hè online Toán, Văn, Anh...lớp 1-12 tại Vietjack với hơn 1 triệu bài tập có đáp án. Học ngay
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Lời giải
Đáp án đúng là: 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 đó.
Lời giả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.
1 Duyệt các phần tử của mảng A từ trái sang phải.
2 Giả sử chỉ số đang duyệt là i, kiểm tra xem A[i] = K
hay không, nếu đúng thì dừng lại, trả về i.
3 Cuối cùng trả về -1.
Bước 2. Chi tiết hoá dòng 1 ở trên.
5 for i in range(len(A)):
Bước 3. Chi tiết hoá dòng 2 của ý tưởng thiết kế ban đầu.
7 if A[i] == K:
8
return i
Bước 4. Chi tiết hoá dòng 3 của ý tưởng thiết kế ban đầu.
return -1
Chương trình hoàn chỉnh:
def LinearSearch (A):
for i in range (A):
if A[i] == K:
return -1
return i
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Bộ 4 đề thi cuối học kì 2 Tin 11 Kết nối tri thức có đáp án (Đề 2)
Bộ 4 đề thi cuối học kì 2 Tin 11 Kết nối tri thức có đáp án (Đề 1)
15 câu Trắc nghiệm Tin học 11 Kết nối tri thức Bài 26 có đáp án
15 câu Trắc nghiệm Tin học 11 Cánh diều Bài 1: Một số thao tác chỉnh sửa ảnh và hỗ trợ chỉnh sửa ảnh có đáp án
15 câu Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25 có đáp án
15 câu Trắc nghiệm Tin học 11 Cánh diều Bài 2: Tẩy xóa ảnh có đáp án
15 câu Trắc nghiệm Tin học 11 Kết nối tri thức Bài 27 có đáp án
Bộ 4 đề thi giữa học kì 2 Tin 11 Kết nối tri thức có đáp án (Đề 4)
Hãy Đăng nhập hoặc Tạo tài khoản để gửi bình luận