Hướng dẫn giải nhanh Tin học 11 định hướng Khoa học máy tính Cánh diều bài 7: Lập trình giải bài toán tìm kiếm

KHỞI ĐỘNG

Câu hỏi: Khi tạo mới một tài khoản người dùng, em được yêu cầu nhập tên người dùng “user name”. Có trường hợp em phải nhập lại tên khác vì tên vừa nhập đã có người sử dụng rồi. Theo em, máy tính làm gì ngay sau khi nhận được yêu cầu tạo mới một tài khoản? Hãy phát biểu thành một bài toán.

Hướng dẫn trả lời:

Bài toán: Xác định tính sẵn có của tên người dùng trong hệ thống khi tạo mới một tài khoản.

Mô tả bài toán:

- Đầu vào: Yêu cầu tạo mới một tài khoản và tên người dùng được nhập.

- Đầu ra: Xác định xem tên người dùng đã tồn tại trong hệ thống hay chưa.

Các bước:

1. Nhận yêu cầu tạo mới tài khoản và tên người dùng từ người dùng.

2. Kiểm tra tên người dùng trong danh sách các tên đã tồn tại trong hệ thống.

3. Nếu tên người dùng đã tồn tại:

   - Thông báo cho người dùng biết rằng tên người dùng đã được sử dụng, yêu cầu nhập tên khác.

   - Quay lại bước 1 để người dùng nhập tên mới.

4. Nếu tên người dùng chưa tồn tại:

   - Cho phép tạo mới tài khoản với tên người dùng này.

   - Hoàn thành quá trình tạo mới tài khoản.

Bài toán này giúp xác định tính sẵn có của tên người dùng để đảm bảo rằng không có sự trùng lặp trong hệ thống và đảm bảo tính duy nhất của mỗi tên người dùng.

HOẠT ĐỘNG

Câu 1: Em hãy thực hiện các yêu cầu sau:

1. Viết mã giả cho thuật toán tìm kiếm nhị phân.

2. Ước lượng số lần thực hiện vòng lặp trong thuật toán tìm kiếm nhị phân.

3. Ước lượng độ phức tạp thời gian của thuật toán tìm kiếm nhị phân.

Hướng dẫn trả lời:

Sau khi thực hiện lần chia đôi đầu tiên, phạm vi tìm kiếm sẽ còn lại khoảng n/2 số. Sau khi thực hiện lần chia đôi thứ hai, dãy còn lại sẽ có n/4 số, và tiếp tục chia đôi, dãy còn lại sau lần chia đôi thứ k sẽ có n/2.mũ k số. Quá trình này kết thúc khi 2 mũ k gần tiến đến gần bằng n.

VẬN DỤNG

Câu 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.

Hướng dẫn trả lời:

a) Gợi ý chương trình tìm kiếm vị trí tên của một người trong danh sách học sinh của lớp: 

Gán i = 0

Gán j = 0

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

Nếu j < n – i – 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 thì dừng lại

b) Gợi ý chương trình tìm kiếm vị trí tên của một người trong 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 bảng chữ cá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);

}

CÂU HỎI TỰ KIỂM TRA

Câu 1: 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ế.

Hướng dẫn trả lời:

- Truy vấn sản phẩm trong cơ sở dữ liệu của một trang thương mại điện tử.

- Xác định thông tin liên hệ của một cá nhân trong danh sách khách hàng của một doanh nghiệp.

- Tìm kiếm một tập tin hoặc thư mục trong hệ thống lưu trữ của máy tính.

- Tra cứu các bản ghi trong cơ sở dữ liệu y tế để xác định bệnh nhân cần điều trị.

- Thực hiện tìm kiếm trong cơ sở dữ liệu của một trang web tuyển dụng để tìm ứng viên phù hợp.

Câu 2: 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?

Hướng dẫ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 dãy, đó là vị trí số 5

- Bước 2: Xét vị trí ở giữa của nửa đầu của dãy là 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

- Thuật toán tìm kiếm nhị phân giới hạn phạm vi tìm kiếm xuống còn tối đa một nửa sau mỗi vòng lặp. Phương pháp này phân chia bài toán thành các phần nhỏ hơn, đồng thời nâng cao hiệu suất tìm kiếm.

Thuật toán tuần tự

- Để mô tả thuật toán một cách chính xác, cần cung cấp thông tin chi tiết và rõ ràng về đầu vào và đầu ra của nó, cùng với điểm kết thúc của thuật toán.

- Phải mô tả thuật toán một cách cụ thể để đảm bảo sự hiểu rõ và thực hiện đúng bởi máy tính hoặc người thực hiện.

- Nếu không làm như vậy, kết quả thực hiện thuật toán có thể không khớp với kỳ vọng.