Giao diện mới của VnDoc Pro: Dễ sử dụng hơn - chỉ tập trung vào lớp bạn quan tâm. Vui lòng chọn lớp mà bạn quan tâm: Lưu và trải nghiệm

Tin học 11 Cánh diều bài 9: Lập trình thuật toán sắp xếp nhanh

Giải 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 xin gửi tới bạn đọc bài viết Tin học 11 Cánh diều bài 9: Lập trình thuật toán sắp xếp nhanh để bạn đọc cùng tham khảo và 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

Nếu cần chọn một trong hai việc sau đây, em sẽ chọn làm việc nào? Vì sao?

1) Từ mô tả thuật toán bằng liệt kê các bước, viết chương trình Python thực hiện thuật toán.

2) Từ chương trình Python thực hiện thuật toán, viết lại ngắn gọn ý tưởng chính của thuật toán.

Bài làm

Chọn bước:

1) Từ mô tả thuật toán bằng liệt kê các bước, viết chương trình Python thực hiện thuật toán.

=> Như vậy dễ nắm được các bước thực hiện và giúp bài toán có phương pháp giải chính xác hơn

Thực hành

Nhiệm vụ 1. Viết chương trình thực hiện sắp xếp nhanh một dãy số và chạy thử kiểm tra.

a) Dựa trên mã lệnh thuật toán cho trong Hình 3.

b) Dựa trên mã lệnh thuật toán cho trong Hình 5.

Bài làm

a) Dựa trên mã lệnh thuật toán cho trong Hình 3.

Tin học 11 Cánh diều bài 9

b) Dựa trên mã lệnh thuật toán cho trong Hình 5.

Tin học 11 Cánh diều bài 9

Nhiệm vụ 2. Bổ sung thêm các câu lệnh in kết quả trung gian vào các chương trình nói trên để có thể quan sát diễn biến từng bước thực hiện sắp xếp nhanh một dãy số.

Bài làm

Câu lệnh in ra màn hình: print(".....")

Các bước thực hiện

Phân tích bài toán

Độ phức tạp thuật toán

Vận dụng

Câu hỏi. Em hãy thực hiện các công việc sau:

a) Sửa lại thủ tục phân đoạn đề có hàm quickSort_ down sắp xếp theo thứ tự giảm dần.

Gợi ý. Sửa đối phép so sánh trong câu lệnh 1f a[3] <= pivot: thành 1f a[3]} >= pivot:

b) Tiếp tục sửa lại để có hàm quickSort_tuple down sắp xếp danh sách

các cặp. ví dụ (tên học sinh, điểm môn học) theo điệm môn học giảm dần.

Gợi y: Sửa đổi đầu vào thành danh sách các cặp (tên học sinh, điểm môn học) và thực hiện so sánh theo điểm môn học.

Bài làm

a)Gợi ý

void swap(int *a,int *b){

int temp=*a;

*a=*b;

*b=temp;

}

void bubblesort(int arr[],int n){

for(int i=0; i<n-1; i++){

for(int j=0; j<n-i-1; j++){

if(arr[j]>arr[j+1]){

swap(&arr[j],&arr[j+1]);

}

}

}

}

b) Gợi ý

void quickSort(int a[], int l, int r){

int p = a[(l+r)/2];

int i = l, j = r;

while (i < j){

while (a[i] < p){

i++;

}

while (a[j] > p){

j--;

}

if (i <= j){

int temp = a[i];

a[i] = a[j];

a[j] = temp;

i++;

j--;

}

}

if (i < r){

quickSort(a, i, r);

}

if (l < j){

quickSort(a, l, j);

}

}

-------------------------------------------

Bài tiếp theo: Tin học 11 Cánh diều bài 10: Thiết kế chương trình từ trên xuống và phương pháp modun hóa

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 9: Lập trình thuật toán sắp xếp nhanh. 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.

Chia sẻ, đánh giá bài viết
1
Sắp xếp theo
    🖼️

    Gợi ý cho bạn

    Xem thêm
    🖼️

    Tin học 11 Cánh diều

    Xem thêm