Đề bài
Hãy chỉ ra tính dừng của thuật toán tìm kiếm tuần tự.
Lời giải chi tiết
- Thuật toán tìm kiếm tuần tự:
Bước 1. Nhập N, các số hạng a,...a2,...aNvà 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]xảy ra khi thỏa mãn một trong 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.