Soạn Tin học 11 Cánh Diều Bài 7: Lập trình giải bài toán tìm kiếm (trang 117, 121)

Hướng dẫn Soạn Tin học 11 Cánh Diều Bài 7: Lập trình giải bài toán tìm kiếm (trang 117, 121) ngắn gọn, hay nhất theo chương trình Sách mới.

Bài 7: Lập trình giải bài toán tìm kiếm

Lý thuyết Tin học 11 Cánh Diều Bài 7: Lập trình giải bài toán tìm kiếm

Sơ đồ tư duy Tin học 11 Cánh Diều Bài 7 Chủ đề FCs: Lập trình giải bài toán tìm kiếm

1. Viết chương trình tìm kiếm vị trí tên của một người trong mỗi danh sách sau đây:

a) Danh sách học sinh của lớp em.

b) Danh sách tên các chủ tài khoản ngân hàng (kí tự không dấu) và đã sắp thứ tự theo bang chữ cái.

Trả lời:

a) Gợi ý

Gán i = 0

Gán j = 0

Nếu j < n – i – 1:

Nếu A[j] > A[j + 1] thì đối chỗ A[j] và A[j + 1]

Đúng thì j = j + 1 và quay lại bước 3

Sai thì sang bước 5

Nếu i < n – 1:

Đúng thì i = i + 1 và quay lại bước 2

Sai → dừng lại

b) Gợi ý:

#include<stdio.h>

#include<string.h>

int main() {

  char s[4][20];

  char t[20];

  int i, j;

  int size = 4;

  printf("\nNhap 4 chuoi bat ky: \n");

  for (i = 0; i < size; i++) {

     scanf("%s", s[i]);

  }

  // sap xep chuoi

  for (i = 1; i < size; i++) {

     for (j = 1; j < size; j++) {

        if (strcmp(s[j - 1], s[j]) > 0) {

           strcpy(t, s[j - 1]);

           strcpy(s[j - 1], s[j]);

           strcpy(s[j], t);

        }

     }

  }

  printf("\nSap xep thu tu cua cac chuoi:");

  for (i = 0; i < size; i++) {

     printf("\n%s", s[i]);

  }

  return(0);

}

2. Em hãy nêu ra một vài ví dụ về bài toán tìm kiếm trong thực tế

Trả lời: 

* Ví dụ: Tìm tên quyển sách trong thư viện

- Mã số, tên sách được sắp xếp theo thứ tự trong bảng chữ cái.

⇒ Để tìm tên một quyển sách, chúng ta có thể thực hiện thuật toán tìm kiếm nhị phân để tìm kiếm.

- Hướng dẫn tìm tên cuốn sách “Dế mèn phưu lưu ký”, (giả sử trong thư viện không có tên sách trùng nhau).

+ Chúng ta, xem xét từ vị trí giữa sách. So sánh tên cần tìm với tên ở vị trí xét.

- Nếu kí tự đầu của tên đứng trước vần D thì tên cần tìm ở nửa sau danh sách.

- Nếu kí tự đầu của tên đứng sau vần D thì tên cần tìm ở nửa trước của danh sách.

Nếu tên trùng nhau thì dừng lại.

+ Nếu chưa tìm thấy thì tiếp tục tìm như bước trên.

* Gợi ý một vài ví dụ khác:

- Tìm kiếm sản phẩm của một trang thương mại điện tử.

- Tìm kiếm thông tin của khách hàng

- Tìm kiếm một file hoặc thư mục trong tệp của máy tính.

3. Theo em, với dãy đã sắp thứ tự và cho một số x cụ thể

a. Trường hợp nào tìm kiếm tuần tự nhanh hơn tìm kiếm nhị phân?

b. Về trung bình thuật toán tìm kiếm tuần tự hay thuật toán tìm kiếm nhị phân tốt hơn?

Trả lời:

a. Ví dụ một bài toán tìm kiếm trong thực tế: Giáo viên muốn tìm tên bạn Chung trong danh sách lớp sau:

Các bước thực hiện thuật toán tìm kiếm nhị phân cho bài toán trên:

- Bước 1: Xét vị trí ở giữa (vị trí số 5)

- Bước 2: Xét vị trí ở giữa của nửa đầu (vị trí số 3)

- Vì sau bước 2 đã tìm thấy tên học sinh nên thuật toán kết thúc.

b. Thuật toán tìm kiếm nhị phân

- Từ việc so sánh trên, ta có thể nhận thấy rằng, Thuật toán tìm kiếm nhị phân sử dụng tốt và dễ dàng hơn.

>>> Xem toàn bộ: Soạn Tin 11 Cánh diều

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

Trên đây Toploigiai đã cùng các bạn Soạn Tin học 11 Cánh Diều Bài 7: Lập trình giải bài toán tìm kiếm trong bộ SGK Cánh Diều theo chương trình sách mới. Chúng tôi hi vọng các bạn đã có kiến thức hữu ích khi đọc bài viết này. Click vào trang chủ Toploigiai để tham khảo và chuẩn bị bài cho năm học mới nhé. Chúc các bạn học tốt!