CHÀO MỪNG CÁC EM ĐẾN VỚI BÀI HỌC MỚI!
Định hướng khoa học máy tính 11
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?
KHỞI ĐỘNG
THỰC HÀNH BÀI TOÁN SẮP XẾP
BÀI 22:
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:
Ghi nhớ kiến thức trong bài
DẶN DÒ VỀ NHÀ
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!
Định hướng khoa học máy tính 11