Nội dung bài viết

    Xem thêm

    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 Câu 26.7 trang 79 SBT Tin học 11 sách Kết nối tri thức hay nhất, chi tiết sẽ giúp học sinh dễ dàng làm bài tập Tin học 11.

    1 145 18/12/2023
    Trang trước
    Chia sẻ
    Trang sau  

    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

    Câu 26.7 trang 79 SBT Tin học 11: 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.

    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 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):

    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.

    Xem thêm lời giải sách bài tập Tin học lớp 11 bộ sách Kết nối tri thức hay, chi tiết khác:

    Câu 26.1 trang 79 SBT Tin học 11: Mệnh đề nào sau đây mô tả đúng về phương pháp thiết kế làm mịn dần?...

    Câu 26.2 trang 79 SBT Tin học 11: 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...

    Câu 26.3 trang 79 SBT Tin học 11: Phát biểu sau về phương pháp làm mịn dần là đúng hay sai?...

    Câu 26.4 trang 79 SBT Tin học 11: 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...

    Câu 26.5 trang 79 SBT Tin học 11: 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....

    Câu 26.6 trang 79 SBT Tin học 11: 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.....

    Câu 26.7 trang 79 SBT Tin học 11: 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....

    Xem thêm lời giải sách bài tập Tin học lớp 11 bộ sách Kết nối tri thức hay, chi tiết khác:

    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

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

    Bài 29: Thực hành thiết kế chương trình theo mô đun

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

    Bài 31: Thực hành thiết lập thư viện chương trình

    Tham khảo các loạt bài Tin học 11 khác:

    Bài viết cùng lớp mới nhất

    Xem thêm
    1 145 18/12/2023
    Trang trước
    Chia sẻ
    Trang sau  

    Xem thêm các chương trình khác: