Giải SGK Tin học 11 Cánh diều Bài 7. Lập trình giải bài toán tìm kiếm có đáp án

Sau lần chia đôi đầu tiên, pham vi tìm kiếm còn lại n/2 số, sau khi chia đôi lần thứ hai, dãy còn lại n/4 số, sau khi chia đôi lần thứ dãy còn lại n/8, …sau khi chia đôi lần k dãy còn lại n/2$_{.}$mũ k. Kết thúc khi 2 mũ k sấp xỉ n.

a. Viết chương trình phython thực hiện tìm kiếm tuần tự

def search(arr, n, x):

for i in range (0, n):

if (arr[i] == x):

return i;

return -1;

# Driver Code

arr = [ 2, 3, 4, 10, 40 ];

x = 10;

n = len(arr);

result = search(arr, n, x)

if(result == -1):

print("Element is not present in array")

else:

print("Element is present at index", result);

b. Viết phiên bản tìm kiếm tuần tự thứ hai, dùng vòng lặp for thay cho vòng lặp while (hoặc ngược lại).

def search(arr, n, x):

for i in range (0, n):

if (arr[i] == x):

return i;

return -1;

# Driver Code

arr = [ 2, 3, 4, 10, 40 ];

x = 10;

n = len(arr);

result = search(arr, n, x)

if(result == -1):

print("Element is not present in array")

else:

print("Element is present at index", result);

c. Viết phiên bản tìm kiếm tuần tự có thêm hai tham số đầu vào lo và hi tương tự như của hàm index. So sánh kết quả với phương thức index của phython.

def search(arr, n, x):

for i in range (0, n):

if (arr[i] == x):

return i;

return -1;

# Driver Code

arr = [ 2, 3, 4, 10, 40 ];

x = 10;

n = len(arr);

result = search(arr, n, x)

if(result == -1):

print("Element is not present in array")

else:

print("Element is present at index", result);

#Trả về chỉ số của x trong arr nếu tồn tại, nếu không có sẽ trả về -1

def binary_search(arr, low, high, x):

#Trường hợp cơ sở

if high >= low:

mid = (high + low) // 2

#Nếu phần tử có tồn tại ở phần giữa của mảng

if arr[mid] == x:

return mid

#Nếu phần tử nhỏ hơn mid, nó sẽ nằm ở phía bên trái của mảng điểm gốc là tử phần tử mid

elif arr[mid] > x:

return binary_search(arr, low, mid - 1, x)

#Nếu không, phần tử sẽ nằm bên phải

else:

return binary_search(arr, mid + 1, high, x)

else:

#Phần tử không tồn tại trong tập hợp

return -1

#Khởi tạo tập hợp

arr = [ 2, 3, 4, 10, 40 ]

x = 10

#Gọi hàm

result = binary_search(arr, 0, len(arr)-1, x)

if result != -1:

print("Phần tử cần tìm có chỉ số là ", str(result))

else:

print("Phần tử cần tìm không có trong mảng.")

a) Gợi ý

Gán i = 0

Gán j = 0

Nếu A[j] > A[j + 1] thì đối chỗ A[j] và A[j + 1]

Nếu j < n – i – 1:

Đúng thì j = j + 1 và quay lại bước 3

Sai thì sang bước 5

Nếu i < n – 1:

Đúng thì i = i + 1 và quay lại bước 2

Sai thì dừng lại

b) Gợi ý:

#include$<$stdio.h>

#include$<$string.h>

int main() {

char s[4][20];

char t[20];

int i, j;

int size = 4;

printf("\nNhap 4 chuoi bat ky: \n");

for (i = 0; i < size; i++) {

scanf("%s", s[i]);

}

// sap xep chuoi

for (i = 1; i < size; i++) {

for (j = 1; j < size; j++) {

if (strcmp(s[j - 1], s[j]) > 0) {

strcpy(t, s[j - 1]);

strcpy(s[j - 1], s[j]);

strcpy(s[j], t);

}

}

}

printf("\nSap xep thu tu cua cac chuoi:");

for (i = 0; i < size; i++) {

printf("\n%s", s[i]);

}

return(0);

}

- Tìm kiếm sản phẩm trong cơ sở dữ liệu của một trang thương mại điện tử.

- Tìm kiếm thông tin liên hệ của một người trong danh sách khách hàng của một doanh nghiệp.

- Tìm kiếm một file hoặc thư mục trong hệ thống tệp của máy tính.

- Tìm kiếm các bản ghi trong cơ sở dữ liệu y tế để tìm kiếm bệnh nhân cần điều trị.

- Tìm kiếm các bản ghi trong cơ sở dữ liệu của một trang tuyển dụng để tìm kiếm ứng viên phù hợp.

a. Ví dụ một bài toán tìm kiếm trong thực tế: Giáo viên muốn tìm tên bạn Chung trong danh sách lớp sau:

Các bước thực hiện thuật toán tìm kiếm nhị phân cho bài toán trên:

- Bước 1: Xét vị trí ở giữa dãy, đó là vị trí số 5

- Vì sau bước 2 đã tìm thấy tên học sinh nên thuật toán kết thúc.

b) Thuật toán tìm kiếm nhị phân

- Thuật toán tìm kiếm nhị phân thu hẹp được phạm vi tìm kiếm chỉ còn tối đa là một nửa sau mỗi lần lặp. Thuật toán chia bài toán thành những bài toán nhỏ hơn giúp tăng hiệu quả tìm kiếm.

Thuật toán tuần tự

- Mô tả thuật toán phải cụ thể, rõ ràng, đầy đủ, đầu vào là gì, đầu ra là gì và chỉ rõ sự kết thúc thuật toán.

- Cần mô tả thuật toán cho tốt thì người máy hay máy tính mới hiểu đúng và thực hiện được.

- Nếu không, kết quả thực hiện thuật toán có thể không như mong đợi.