Bài 19: Bài toán tìm kiếm

Hướng dẫn giải

Bạn An không chắc chắn xác định được thẻ nào in số K nếu An chỉ lật từng thẻ từ đầu đến cuối một cách tuần tự. Trong trường hợp xấu nhất, thẻ in số K có thể nằm ở vị trí cuối cùng của bộ thẻ, khiến An phải lật qua tất cả các thẻ trước đó trước khi tìm ra thẻ in số K. Tuy nhiên, có một cách khác để tìm ra thẻ in số K nhanh hơn, bạn An có thể làm theo các bước sau:

- Lật thẻ ở giữa bộ thẻ để xem giá trị số in trên đó.

- So sánh giá trị số in trên thẻ với số K:

- Nếu giá trị số in trên thẻ bằng số K, thì trò chơi kết thúc và thẻ đó chính là thẻ in số K.

- Nếu giá trị số in trên thẻ lớn hơn số K, thì thẻ in số K nằm ở một vị trí trước đó trong bộ thẻ. Tiếp tục tìm kiếm trong nửa đầu của bộ thẻ từ đầu đến vị trí thẻ vừa lật.

- Nếu giá trị số in trên thẻ nhỏ hơn số K, thì thẻ in số K nằm ở một vị trí sau đó trong bộ thẻ. Tiếp tục tìm kiếm trong nửa sau của bộ thẻ từ vị trí thẻ vừa lật đến cuối.

Lặp lại các bước trên cho đến khi tìm thấy thẻ in số K hoặc đã lật hết tất cả các thẻ trong bộ thẻ. Với cách làm như vậy, An sẽ tìm ra thẻ in số K trong số lượt lật thẻ ít hơn so với phương pháp tìm lần lượt, đặc biệt là khi số lượng thẻ là lớn.

(Trả lời bởi Thanh An)

Hướng dẫn giải

-  Với bài toán 1: Miền dữ liệu là tắt cả các ảnh có trên các máy tính kết nói mạng Intemet. Kết quả là các ảnh có hinh hoa hồng.

- Với bài toán 2: Miền dữ liệu là các tệp văn bản có trên đĩa cứng máy tính của em. Kết quả là tệp có tên bai-hoc- 1 docx.

-  Với bài toán 3: Miền dữ liệu là đanh sách học sinh và điểm các bài dự thi của kì thi Olympic Tin học thành phố. Kết quả là danh sách 5 bạn có thành tích cao nhất tính theo điểm trung bình.

(Trả lời bởi Quoc Tran Anh Le)

Hướng dẫn giải

Miền là đường đi từ nhà em đến trường học

Kết quả: Tên đường trên bản đồ dẫn từ nhà em đến trường học

(Trả lời bởi Thanh An)

Hướng dẫn giải

Miền các trường trung học phổ thông em đang cư trú.

Kết quả tên trường trung học phổ thông em đang cư trú.

(Trả lời bởi Quoc Tran Anh Le)

Hướng dẫn giải

Thuật toán tìm kiếm tuần tự: Duyệt lần lượt các phần tử của dãy để tìm phần tử có giá trị bằng K. Nếu tìm thấy, trả về chỉ số của phản tử bằng K; Ngược lại, thông báo không tìm thây và trả về giá trị -1. Thuật toán có thê duyệt từ đâu dãy hoặc từ cuối dãy.

(Trả lời bởi Thanh An)

Hướng dẫn giải

Trong trường hợp này, chúng ta cần tìm phần tử có giá trị là 47 trong dãy A = [1, 91, 45, 23, 67, 9, 10, 47, 90, 46, 86]. Ta sẽ thực hiện duyệt từng phần tử trong dãy này để tìm kiếm phần tử có giá trị là 47.

Dãy A có tổng cộng 11 phần tử, và trong trường hợp xấu nhất, phần tử cần tìm là phần tử cuối cùng của dãy. Vì vậy, trong trường hợp xấu nhất, ta cần duyệt qua toàn bộ dãy A để tìm thấy phần tử có giá trị là 47.

Vậy, số lần duyệt cần thực hiện là 7 lần.

(Trả lời bởi Thanh An)

Hướng dẫn giải

Thuật toán tìm kiếm tuần tự sẽ cần nhiều bước nhất khi phải duyệt qua toàn bộ dãy số để tìm kiếm phần tử cần tìm, tức là phần tử đó nằm ở cuối dãy hoặc không có trong dãy. Đây là trường hợp xấu nhất của thuật toán tìm kiếm tuần tự.

Ví dụ: Giả sử chúng ta cần tìm phần tử có giá trị là 100 trong dãy A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]. Phần tử này không có trong dãy, và thuật toán tìm kiếm tuần tự sẽ phải duyệt qua toàn bộ dãy 10 phần tử để xác nhận rằng phần tử này không có trong dãy.

Vậy, trong trường hợp xấu nhất, số lần duyệt cần thực hiện là đúng bằng số phần tử trong dãy. Trong ví dụ trên, số lần duyệt cần thực hiện là 10 lần để tìm kiếm phần tử không có trong dãy.

(Trả lời bởi Thanh An)

Hướng dẫn giải

Thuật toán tìm kiếm tuần tự sẽ cần nhiều bước nhất khi phải duyệt qua toàn bộ dãy số để tìm kiếm phần tử cần tìm, tức là phần tử đó nằm ở cuối dãy hoặc không có trong dãy. Đây là trường hợp xấu nhất của thuật toán tìm kiếm tuần tự.

Ví dụ: Giả sử chúng ta cần tìm phần tử có giá trị là 100 trong dãy A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]. Phần tử này không có trong dãy, và thuật toán tìm kiếm tuần tự sẽ phải duyệt qua toàn bộ dãy 10 phần tử để xác nhận rằng phần tử này không có trong dãy.

Vậy, trong trường hợp xấu nhất, số lần duyệt cần thực hiện là đúng bằng số phần tử trong dãy. Trong ví dụ trên, số lần duyệt cần thực hiện là 10 lần để tìm kiếm phần tử không có trong dãy.

(Trả lời bởi Quoc Tran Anh Le)

Hướng dẫn giải

Thuật toán tìm kiếm nhị phân thực hiện tìm kiếm một mảng đã sắp xếp bằng cách liên tục chia các khoảng tìm kiếm thành 1 nửa. Bắt đầu với một khoảng từ phần tử đầu mảng, tới cuối mảng. Nếu giá trị của phần tử cần tìm nhỏ hơn giá trị của phần từ nằm ở giữa khoảng thì thu hẹp phạm vi tìm kiếm từ đầu mảng tới giửa mảng và nguợc lại. Cứ thế tiếp tục chia phạm vi thành các nửa cho dến khi tìm thấy hoặc đã duyệt hết.

Thuật toán tìm kiếm nhị phân tỏ ra tối ưu hơn so với tìm kiếm tuyết tính ở các mảng có độ dài lớn và đã được sắp xếp. Ngược lại, tìm kiếm tuyến tính sẽ tỏ ra hiệu quả hơn khi triển khai trên các mảng nhỏ và chưa được sắp xếp.

(Trả lời bởi Quoc Tran Anh Le)

Hướng dẫn giải

Với thuật toán tìm kiếm tuần tự, cần duyệt 10 phần tử để tìm ra phần từ có giá trị bằng 34.

(Trả lời bởi Quoc Tran Anh Le)