Giải Tin học 7 Bài 1 (Cánh diều): Tìm kiếm tuần tự

Giải Tin học 7 Bài 1: Tìm kiếm tuần tự

Khởi động

Khởi động trang 78 Tin học 7: Giáo viên tin học lớp 7A trả kết quả bài kiểm tra và thông báo: “Trong lớp ta có duy nhất một bạn đạt điểm 10”. Xem danh sách lớp kèm cột kiểm tra, em làm thế nào để biết ai đạt điểm 10?

Trả lời:

Giáo viên tin học lớp 7A trả kết quả bài kiểm tra và thông báo: “Trong lớp ta có duy nhất một bạn đạt điểm 10”. Xem danh sách lớp kèm cột kiểm tra, muốn biết ai đạt điểm 10 em phải nhìn và tìm kiếm lần lượt từ đầu đến cuối của cột điểm đến khi thấy điểm 10, sau đó gióng sang cột tên để tìm bạn được điểm 10.

2. Thuật toán tìm kiếm tuần tự

Hoạt động

Hoạt động trang 79 Tin học 7: Với dãy số đã cho ở ví dụ trên, em hãy thực hiện thuật toán được mô tả ở hình bên và cho biết đó có phải là thuật toán tìm kiếm tuần tự hay không?

Bước 1. Số đang xét là số ở đầu dãy.

Bước 2. Lặp khi (chưa xét hết dãy số)

Nếu Số đang xét khác x: Chuyển đến xét số tiếp theo trong dãy.

Trái lại: Thông báo vị trí tìm thấy x và kết thúc thuật toán.

Hết nhánh

Hết lặp

Bước 3. Thông báo không tìm thấy x và kết thúc thuật toán.

Trả lời:

- Thực hiện thuật toán ở ví dụ trên.

Bước 1. Số 18 là số ở đầu dãy.

Bước 2. Lặp

+ Số 18 khác số 44: Chuyển đến xét số tiếp theo trong dãy.

+ Số 94 khác số 44: Chuyển đến xét số tiếp theo trong dãy.

+ Số 42 khác số 44: Chuyển đến xét số tiếp theo trong dãy.

+ Số 44 trùng số 44. Thông báo tìm thấy số 44.

Hết nhánh

Bước 3. Tìm thấy số 44 trong dãy.

- Đó là thuật toán tìm kiếm tuần tự.

Luyện tập

Luyện tập trang 80 Tin học 7: Cho một dãy số:

Em hãy thể hiện từng bước của thuật toán giải bài toán “Tìm xem số 45 có trong dãy này không? Nếu có thì nằm ở vị trí nào?”.

Trả lời:

Dãy xuất phát:

Gọi số phải tìm là x (x=45), các bước tìm kiếm như sau:

- Bước 1. Số đang xét là số ở đầu dãy; Kết quả chưa tìm thấy

- Bước 2. Lặp khi (chưa xét hết dãy số) và (Kết quả = chưa tìm thấy);

Nếu số đang xét # x: chuyển đến số tiếp theo trong dãy.

Trái lại: Kết quả = tìm thấy ; Thông báo vị trí tìm thấy x

Hết nhánh

Hết lặp

- Bước 3. Nếu kết quả = chưa tìm thấy: Thông báo không có x trong dãy

Hết nhánh

Vận dụng

Vận dụng 1 trang 80 Tin học 7: Em có cách nào khác để giải bài toán tìm kiếm trong dãy không sắp thứ tự không?

Trả lời:

Cách để giải bài toán tìm kiếm trong dãy không sắp thứ tự:

Khi dãy không sắp thứ tự thì cần tìm kiếm tuần tự. Hoặc có thể sắp xếp dãy theo tuần tự sau có tiến hành tìm kiếm trong dãy đã sắp thứ tự.

Vận dụng 2 trang 80 Tin học 7: Có thể áp dụng thuật toán tìm kiếm tuần tự cho dãy đã sắp thứ tự không? Tại sao?

Trả lời:

Có thể áp dụng thuật toán tìm kiếm tuần tự cho dãy đã sắp xếp thứ tự. Vì việc sắp xếp dãy theo thứ tự không ảnh hưởng đến thuật toán tìm kiếm tuần tự.

Câu hỏi tự kiểm tra

Câu 1 trang 80 Tin học 7: Hai khả năng xảy ra khi thực hiện tìm kiếm tuần tự là gì?

Trả lời:

Hai khả năng xảy ra khi thực hiện tìm kiếm tuần tự là:

- Tìm được số

- Không tìm được số khi kết thúc dãy số.

Câu 2 trang 80 Tin học 7: Khi nào thì việc tìm kiếm tuần tự được kết thúc giữa chừng của dãy?

Trả lời:

Việc tìm kiếm tuần tự được kết thúc giữa chừng của dãy khi số đã được tìm thấy ở đó.

Câu 3 trang 80 Tin học 7: Khi nào thì việc tìm kiếm tuần tự dò tìm đến phần tử ở cuối dãy?

Trả lời:

Việc tìm kiếm tuần tự dò tìm đến phần tử ở cuối dãy khi số cần tìm chưa được tìm thấy.

Lý thuyết Tin Học 7 Bài 1: Tìm kiếm tuần tự

1. Tìm kiếm tuần tự một số trong dãy số

- Quy trình để tìm một số trong dãy số không sắp thứ tự được minh hoa qua ví dụ sau:

Ví dụ: Cho dãy số 18, 94, 42, 06, 42, 44, 06, 55, 12, 67. Hãy tìm xem có số 44 trong dãy này hay không. Nếu có thì đưa ra vị trí đầu tiên tìm thấy.

Dãy xuất phát

Gọi số phải tìm là x (x = 44). Các bước thực hiện tìm kiếm như sau:

Hình 1.1: Minh họa các bước tìm kiếm tuần tự

Nếu thay x = 30 thì các bước tìm kiếm x trong dãy trên không dừng lại ở bước 4 mà tiếp tục cho đến hết dãy và kết luận “Không tìm thấy x trong dãy”.

2. Thuật toán tìm kiếm tuần tự

Ý tưởng thuật toán tuần tự: Xuất phát từ đầu dãy, nếu có số ở đầu dãy không phải số cần tìm thì chuyển sang số tiếp theo, cứ thế cho đến khi tìm được hoặc xét hết dãy.

Mô tả thuật toán:

3. Bài toán tìm kiếm

Bài toán tìm kiếm trong dãy không sắp thứ tự

- Khi dãy không sắp thứ tự thì cần thực hiện tìm kiếm tuần tự.

Ví dụ: Tập bài kiểm tra của lớp chưa được xếp theo thứ tự bảng chữ cái đối với tên học sinh, muốn tìm bài của em, giáo viên sẽ xem tên học sinh trên từng bài, cho đến bài của em.

Bài toán tìm kiếm trong dãy đã sắp thứ tự

Ví dụ: Tương tự như ví dụ trên, nếu danh sách tên học sinh trong lớp được xếp theo thứ tự chữ cái trong từ điển thì em có thể nhanh chóng thấy tên của mình.

Xem thêm lời giải bài tập Tin học lớp 7 Cánh diều hay, chi tiết khác:

Bài 2: Tìm kiếm nhị phân

Bài 3: Sắp xếp chọn

Bài 4: Sắp xếp nổi bọt

Bài 5: Thực hành mô phỏng các thuật toán tìm kiếm, sắp xếp

Bài 1: Thiết bị vào - ra cơ bản cho máy tính cá nhân

Xem thêm tài liệu Tin học lớp 7 Cánh diều hay, chi tiết khác:

Lý thuyết Bài 1: Tìm kiếm tuần tự