13/01/2018, 07:19

Câu 3 trang 44 SGK Tin học 10

Câu 3 trang 44 SGK Tin học 10 Hãy chỉ ra tính dừng của thuật toán tìm kiếm tuần tự. ...

Câu 3 trang 44 SGK Tin học 10

Hãy chỉ ra tính dừng của thuật toán tìm kiếm tuần tự.

Hãy chỉ ra tính dừng của thuật toán tìm kiếm tuần tự.

Trả lời:

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

Bước 1. Nhập N, các số hạng a,...a2,...aN và khoá k

Bước 2. i

Bước 3. Nếu ai= k thì thông báo chỉ số i, rồi kết thúc;

Bước 4. i

Bước 5. Nếu i > N thì thông báo dãy A không có sô hạng nào có giá trị nào bằng k, rồi kết thúc;

Bước 6. Quay lại bước 3.

Tính dùng cùa thuật toán tìm kiếm tuần tự: nghĩa là thuật toán phải kết thúc sau một số hữu hạn lần bước tính.

Thuật toán chia làm hai trường hợp

- Nếu tìm thấy giá trị cần tìm trong dãy A (ai= k) thì thông báo chỉ số i (vị trí tìm thấy khoá k trong dãy A), rồi kết thúc.

- Nếu không tìm thấy giá trị cần tìm trong dãy A, vì bước 4 thực hiện việc tăng giá trị của i lớn hơn 1, nên sau N lần thì i > N, thông báo dãy A không có giá trị nào bằng k, rồi kết thúc.

0