Tin học 11 Cánh diều bài 8: Lập trình một số thuật toán sắp xếp
Tin học 11 Cánh diều bài 8: Lập trình một số thuật toán sắp xếp được VnDoc.com sưu tầm và xin gửi tới bạn đọc cùng tham khảo để có thêm tài liệu giải SGK Tin học 11 Cánh diều nhé. Mời các bạn cùng theo dõi bài viết dưới đây.
Khởi động
Câu hỏi. Trình quản lí tệp của hệ điều hành cho phép lựa chọn hiển thị nội dung của thư mục được sắp xếp thứ tự theo vài cách khác nhau. Em hãy cho biết một trong số các lựa chọn này và giải thích rõ thêm tiêu chí (yêu cầu) sắp xếp tương ứng.
Bài làm
Sắp xếp nổi bọt
=> Ưu điểm:
Là thuật toán cơ bản, dễ hiểu, phù hợp cho người bắt đầu học về sắp xếp
Đoạn code ngắn gọn, dễ nhớ.
Sắp xếp chèn tuyến tính
=> Ưu điểm:
Thao tác thực hiện đơn giản, dễ hiểu.
Thể hiện sự hiệu quả cao đối với các số liệu nhỏ.
Tại các tình huống thực tế, Insertion Sort tỏ ra hiệu quả hơn so với các thuật toán có độ phức tạp �(�2)O(n2) khác (ví dụ Bubble sort).
Rất phù hợp đối với các số liệu đã được sắp xếp theo thứ tự sẵn.
Tính ổn định, không làm thay đổi nhiều thứ tự các nguyên tố gốc.
Cách sắp xếp có tính phương pháp, tuân theo nguyên tắc cụ thể, dễ nhớ và sử dụng.
Thực hành
Nhiệm vụ 2. Em hãy viết chương trình Python thực biện thuật toán sắp xếp nổi bọt.
Bài làm
Gợi ý:
def bubbleSort(arr):
n = len(arr)
#Duyệt qua tất cả các phần tử
for i in range(n-1):
for j in range(0, n-i-1):
#Hoán đổi phần tử nếu nó lớn hơn phần tử sau nó
if arr[j] > arr[j + 1] :
arr[j], arr[j + 1] = arr[j + 1], arr[j]
#Thực thi đoạn mã
arr = [64, 34, 25, 12, 22, 11, 90]
bubbleSort(arr)
for i in range(len(arr)):
print("%d" % arr[i], end=" ")
Nhiệm vụ 3. Em hãy viết chương trình Python thực hiện thuật toán sắp xếp chèn tuyến tính dựa trên mã giả đã cho trong báo học
Bài làm
void Insertion_Sort(int a[], int n){
int pos, i;
int x;//lưu giá trị a[i] tránh bị ghi đè khi dời chỗ các phần tử
for(i=1; i<n; i++){//đoạn a[0] đã sắp xếp
x = a[i]; pos = i-1;
//tìm vị trí chèn x
while((pos>=0)&&(a[pos]>x)){
//kết hợp dời chỗ các phần tử sẽ đứng sau x trong danh sách mới
a[pos+1] = a[pos];
pos--;
}
a[pos+1] = x;//chèn x vào danh sách
}
}
void main()
{
int a[5] = {8, 4, 1, 6, 5};
Insertion_Sort(a, 5);
cout<<"Mang sau khi sap xep:"<<endl;
for(int i=0;i<5;i++){
cout<<a[i]<<" ";
}
system("pause");
Vận dụng
Câu hỏi: Cho danh sách Bảng điểm là kết quá học tập gồm các cột Họ và tên, điểm Toán, điểm ngữ văn, điểm Tin bọc... Hãy viết chương trình sắp xếp Bảng điểm theo điểm môn Tin học giảm dần.
Gợi ý: Mỗi phân tử của Bảng điểm là một danh sách con, ứng với một học sinh. So sánh theo thành phân điểm Tin học của danh sách con để sắp xếp.
Bài làm
#include <stdio.h>
#define GIOI "\nXep loai gioi"
#define KHA "\nXep loai kha"
#define TB "\nXep loai trung binh"
#define YEU "\nXep loai yeu"
/*
Format code: Alt + Shift + F
*/
int main()
{
// Nhập điểm 3 môn
float diemToan;
float diemVan;
float diemAnh;
float dtb;
printf("\nNhap diem toan = ");
scanf("%f", &diemToan);
printf("\nNhap diem van = ");
scanf("%f", &diemVan);
printf("\nNhap diem anh = ");
scanf("%f", &diemAnh);
dtb = (diemToan + diemVan + diemAnh) / 3;
printf("\nDTB = %.2f", dtb);
if (dtb < 4)
{
printf(YEU);
}else if (dtb < 6.5){
printf(TB);
}else if(dtb < 8.0){
printf(KHA);
}else{
printf(GIOI);
}
}
-----------------------------------------------
Bài tiếp theo: Tin học 11 Cánh diều bài 9: Lập trình thuật toán sắp xếp nhanh
VnDoc.com vừa gửi tới bạn đọc bài viết Tin học 11 Cánh diều bài 8: Lập trình một số thuật toán sắp xếp. Mời các bạn cùng tham khảo thêm tại mục Tin học 11 Cánh diều.
