Hãy trình bày thuật toán tìm kiếm tuần tự theo phương pháp làm mịn dần

Giải SBT Tin học 11 Bài 26: Phương pháp làm mịn dần trong thiết kế chương trình

Câu 26.5 trang 79 SBT Tin học 11: Hãy trình bày thuật toán tìm kiếm tuần tự theo phương pháp làm mịn dần.

Lời giải:

Một cách trình bày theo phương pháp làm mịn dần có thể như sau:

Bài toán: Cho trước mảng A (có n phần tử) và giá trị K. Cần tìm phần tử của A có giá trị bằng K. Nếu tìm thấy trả lại chỉ số của phần tử này (chỉ cần tìm một nghiệm), ngược lại trả về −1.

Bước 1. Thiết lập ý tưởng thiết kế ban đầu.

1 Duyệt các phần tử của mảng A từ trái sang phải.

2 Giả sử chỉ số đang duyệt là i, kiểm tra xem A[i] = K

hay không, nếu đúng thì dừng lại, trả về i.

3 Cuối cùng trả về -1.

Bước 2. Chi tiết hoá dòng 1 ở trên.

5 for i in range(len(A)):

Bước 3. Chi tiết hoá dòng 2 của ý tưởng thiết kế ban đầu.

7 if A[i] == K:

8

return i

Bước 4. Chi tiết hoá dòng 3 của ý tưởng thiết kế ban đầu.

return -1

Chương trình hoàn chỉnh:

def LinearSearch (A):

for i in range (A):

if A[i] == K:

return -1

return i