Quan sát cách thực hiện thuật toán tìm kiếm tuần tự trên ví dụ cụ thể sau. Hãy trao đổi thảo luận để hiểu và mô tả được thuật toán trong trường hợp tổng quát.
Cho trước một đây số đã được sắp xếp theo thứ tự tăng dần. Hãy đọc, quan sát và thảo luận cách làm sau đây để hiểu được thuật toán tìm kiếm nhị phân, biết được tính ưu việt của thuật toán này so với thuật toán tìm kiếm tuần tự trên một dây các phần từ đã sắp xếp.
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.
Quan sát chương trình mô tả thuật toán sắp xếp chèn. Hãy thảo luận và đưa ra các lập luận để kiểm tra tính đúng của thuật toán sắp xếp chèn.
Tính đúng của thuật toán cần được chứng minh bằng lập luận toán học. Sử dụng các bộ dữ liệu kiểm thử có thể làm tăng độ tin cậy của chương trình nhưng chưa chứng minh được tính đúng của thuật toán.
Quan sát sơ đồ mô phỏng, trao đổi thảo luận về ý tưởng chính của thuật toán sắp xếp chọn.
Tại mỗi bước lặp của thuật toán, phần tử nhỏ nhất ở mảng con chưa được sắp xếp sẽ được di chuyển về đoạn đã sắp xếp.
Quan sát sơ đồ mô phỏng, trao đổi, thảo luận về ý tưởng chính của thuật toán sắp xếp chèn.
Ý tưởng của thuật toán sắp xếp chèn là thực hiện vòng lặp duyệt từ phần tử thứ hai đến cuối dãy. Sau mỗi bước lặp phần tử tương ứng sẽ được chèn vào vị trí đúng của dãy con đã sắp xếp là các phần tử phía trước vị trí đang duyệt.
Trong các câu sau, những câu nào đúng?
1) Có thể mô tả một kịch bản dưới dạng các bước tuần tự của một thuật toán.
2) Trong một kịch bản, thứ tự thực hiện các bước rất quan trọng, nhưng trong mô tả thuật toán thì thứ tự các bước không quan trọng.
3) Thứ tự các bước trong một thuật toán quy định thứ tự các lệnh (hay khối lệnh) trong chương trình thể hiện thuật toán đó.
Các câu trả lời đúng là:
1) Có thể mô tả một kịch bản dưới dạng các bước tuần tự của một thuật toán. Đó là mô tả một thuật toán có các bước được thực hiện tuần tự.
3) Các bước của thuật toán được mô tả như thế nào thì các lệnh của bước đó cũng phải kế tiếp tuần tự như vậy.
Câu 2 bị sai vì khi thay đổi thứ tự các bước của thuật toán ta có thể thu được kịch bản khác
Câu 1: Nêu công dụng và cú pháp của hàm SUM và COUNT. Cho ví dụ minh họa.
Câu 2: Có mấy loại bài toán tìm kiếm. Nêu ý tưởng của thuật toán tìm kiếm tuần tự.
Câu 3: Cho dãy số sau: 20, 13, 10, 5, 15, 27, 30. Sử dụng thuật toán tìm kiếm tuần tự, hãy tìm xem có số 15 ở trong dãy này hay không? Nếu có thì đưa ra vị trí đầu tiên tìm thấy.
Câu 4: Cho dãy số 3, 19, 7, 25, 65, 22, 30, 42, 45, 12. Sử dụng thuật toán tìm kiếm nhị phân để tìm số 40 trong dãy trên.
mô tả thuật toán sắp xếp chọn và thuật toán tìm kiếm tuần tự
Thảo luận với bạn để mô tả thuật toán tính chu vi mảnh vườn hình chữ nhật có chiều dài a và chiều rộng b được nhập từ bàn phím. Sau đó, sắp xếp các lệnh, khối lệnh dưới đây theo thứ tự đúng để thực hiện thuật toán đó.
Câu 29: Cho danh sách như hình sau: 2 1 An Bình |Hòa |Liên Mai Phương|Trang |Trúc | Tước a/ Em hãy so sánh số bước thực hiện của thuật toán tìm kiếm tuần tự với số bước thực hiện của thuật toán tìm kiếm nhị phân để tìm được khách hàng tên “Hoà” trong danh sách b/ Hãy viết các bước tim kiếm nhị phân tìm khách hành tên Hoà.