Giáo án điện tử Khoa học máy tính 11 kết nối Bài 22: Thực hành bài toán sắp xếp

CHÀO MỪNG CÁC EM ĐẾN VỚI BÀI HỌC MỚI!

KHỞI ĐỘNG

Trong bài 21, em đã được học cách triển khai thuật toán sắp xếp để sắp xếp các phần tử trong danh sách theo thứ tự tăng dần. Nếu cần sắp xếp theo thứ tự ngược lại thì câu lệnh so sánh tương ứng trong vòng lặp sẽ cần thay đổi như thế nào?

BÀI 22: THỰC HÀNH BÀI TOÁN SẮP XẾP

NHIỆM VỤ 1

Cho danh sách số lượng mỗi mặt hàng trong kho của một cửa hàng. Người quản lí kho cần xem các mặt hàng theo thứ tự số lượng tăng dần.

Em hãy viết chương trình sắp xếp các mặt hàng trong kho theo thứ tự số lượng tăng dần, sử dụng thuật toán sắp xếp chèn, sau đó in ra màn hình dãy số vừa sắp xếp. Danh sách số lượng các mặt hàng được đọc từ tệp văn bản kho.inp, mỗi dòng bao gồm số lượng một mặt hàng.

Yêu cầu: Thực hành theo các nhóm từ 2 - 4 HS

Gợi ý:

Chúng ta có thể sử dụng thuật toán sắp xếp chèn đã học ở bài trước để sắp xếp các phần tử trong danh sách số lượng mặt hàng theo thứ tự tăng dần.

Chương trình tham khảo:

1   input­_file = open("kho.inp", encoding="UTF-8")

2   soluong_ds = []

3   for line in input_­file.readlines():

4            soluong_ds.append(int(line))

5   n = len(soluong_ds)

6   for i in range(1,n):

7            value = soluong_ds [i]

8            j = i – 1

9            while j >= 0 and so luong_ds[j] > value:

10                   soluong_ds[j+1] = soluong_ds[j] > value:

11                   j = j – 1

12          soluong_ds [j+1] = value

13      print('Số lượng các mặt hàng trong kho theo thứ tự tăng dần là:')

14      for i in range(0,len(soluong_ds)):

15               print(soluong_ds[i])

NHIỆM VỤ 2

Cho danh sách điểm trung bình môn Tin học của các học sinh. Em hãy sử dụng thuật toán sắp xếp chọn để sắp xếp danh sách này theo thứ tự điểm trung bình giảm dần, sau đó in danh sách đã sắp xếp ra màn hình. Danh sách điểm trung bình được đọc ra từ tệp văn bản diem.inp, mỗi dòng bao gồm điểm trung bình của một học sinh.

Gợi ý: Có thể sử dụng thuật toán sắp xếp chọn đã học ở bài trước để sắp xếp danh sách điểm số như sau:

1   input­_file = open("diem.inp", encoding="UTF-8")

2   diem_ds = []

3   for line in input_­file.readlines():

4            diem_ds.append(float(line))

5   n = len(diem_ds)

6   for i in range(n-1):

7            iMax = i

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

9                     if diem_ds[j] > diem_ds[iMax]:

10                               iMax = j

11          diem_ds[i], diem_ds[iMax] = diem_ds[iMax], diem_ds[i]

12      print('Danh sách điểm theo thứ tự giảm dần là:')

13      for i in range(0,len(diem_ds)):

14               print(diem_ds[i])

LUYỆN TẬP

Bài 1

Sử dụng thuật toán sắp xếp chọn viết lại chương trình trong Nhiệm vụ 1.

Bài 2

Sử dụng thuật toán sắp xếp nổi bọt viết lại chương trình trong Nhiệm vụ 2.

Bài 1: Chương trình tham khảo:

1        def SelectionSort(A):

2                 n = len(A)

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

4                           iMin = i

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

6                                    if A[j] < A[iMin]:

7                                              iMin = j

8                           A[i],A[iMin] = A[iMin],A[i]

9        input_file = open("kho.inp", encoding="UTF-8")

10      soluong_ds = []

11      for line in input_file.readlines():

12               soluong_ds.append(int(line))

13      SelectionSort(soluong_ds)

14      print('Số lượng các mặt hàng trong kho theo thứ tự tăng dần là:')

15      for i in range(0,len(soluong_ds)):

16               print(soluong_ds[i])

Bài 2: Chương trình tham khảo:

1        def BubbleSort(A):

2                 n = len(A)

3                 for i in range(n-1):

4                           for j in range(n-1-i):

5                                    if A[j] < A[j+1]:

6                                              A[j],A[j+1] = A[j+1],A[j]

7        input_file = open("kho.inp", encoding="UTF-8")

8        soluong_ds = []

9        for line in input_file.readlines():

10               soluong_ds.append(int(line))

11      BubbleSort(soluong_ds)

12      print('Số lượng các mặt hàng trong kho theo thứ tự tăng dần là:')

13      for i in range(0,len(soluong_ds)):

14               print(soluong_ds[i])

VẬN DỤNG

Một người đi mua hàng với danh sách các mặt hàng cần mua, đơn giản từng mặt hàng và số lượng hàng cần mua được lưu trong tệp văn bản muahang.inp.

Hãy sử dụng thuật toán nổi bọt để sắp xếp các mặt hàng theo thứ tự thành tiền của các mặt hàng tăng dần rồi in ra tên các mặt hàng và thành tiền tương ứng.

Chương trình tham khảo:

DẶN DÒ VỀ NHÀ

Ghi nhớ kiến thức trong bài

Làm các bài tập trong SBT

Đọc trước Bài 23: Kiểm thử và đánh giá chương trình

TẠM BIỆT CÁC EM VÀ HẸN GẶP LẠI!