Giải Tin học 11 trang 93 Kết nối tri thức

Giải Tin học 11 trang 93 Kết nối tri thức

Câu hỏi 1 trang 93 Tin học 11: Cho dãy A= {0, 4, 9, 10, 12,14, 17, 18, 20, 31, 34, 67}. Với thuật toán tìm kiếm tuần tự, cần duyệt bao nhiêu phần tử để tìm ra phần từ có giá trị bằng 34?

Lời giải:

Để tìm phần tử có giá trị bằng 34 trong dãy A = {0, 4, 9, 10, 12, 14, 17, 18, 20, 31, 34, 67} bằng thuật toán tìm kiếm tuần tự, ta sẽ duyệt qua từng phần tử của dãy cho đến khi tìm thấy phần tử cần tìm.

Vì phần tử 34 nằm ở vị trí thứ 11 trong dãy, nên số lần duyệt cần thực hiện để tìm ra phần tử này là 11 lần, bao gồm cả phần tử 34.

Vậy, cần duyệt qua 11 phần tử để tìm ra phần tử có giá trị bằng 34 trong dãy A.

Câu hỏi 2 trang 93 Tin học 11: Cho dãy A= {0, 4, 9, 10, 12,14, 17, 18, 20, 31, 34, 67}. Với thuật toán tìm kiếm nhị phân, cần duyệt bao nhiêu phần tử để tìm ra phân tử có giá trị bằng 34?

Lời giải:

Với dãy A = {0, 4, 9, 10, 12, 14, 17, 18, 20, 31, 34, 67}, và sử dụng thuật toán tìm kiếm nhị phân, số lần duyệt cần thực hiện để tìm ra phần tử có giá trị bằng 34 là 2 lần.

Quy trình tìm kiếm nhị phân hoạt động bằng cách so sánh giá trị cần tìm với giá trị ở giữa dãy, và dựa vào kết quả của so sánh này để tiếp tục tìm kiếm trong nửa đầu dãy chứa giá trị cần tìm. Lần đầu tiên duyệt, ta so sánh giá trị cần tìm (34) với giá trị ở giữa dãy, tại vị trí (0 + 11)/2 = 5. Vì giá trị tại vị trí này là 14 và 34 > 14, nên ta sẽ tiếp tục tìm kiếm trong nửa đầu dãy phải của vị trí này. Lần duyệt tiếp theo, ta so sánh giá trị cần tìm với giá trị ở giữa dãy, tại vị trí (5 + 11)/2 = 8. Vì giá trị tại vị trí này là 31 và 34 > 31, nên ta sẽ tiếp tục tìm kiếm trong nửa đầu dãy phải của vị trí này. Lần duyệt tiếp theo, giá trị cần tìm là 34 và giá trị tại vị trí này cũng là 34, nên ta đã tìm thấy phần tử cần tìm.

Tổng cộng, số lần duyệt cần thực hiện là 2 lần để tìm ra phần tử có giá trị bằng 34 bằng thuật toán tìm kiếm nhị phân trong dãy A này.

Câu hỏi 3 trang 93 Tin học 11: Thay vị lần lượt lật các thẻ từ đầu đến cuối, bạn Minh đã chơi như sau: Đầu Tiên Minh lật thẻ ở giữa, sau đó tuỳ theo số ghi trên thẻ là lớn hơn hay nhỏ hơn số K mà lạt tiếp thẻ ở ngay bên trái hoặc ngay bên phải thẻ ở giữa. Trong trường hợp này, số lần nhiều nhất mà Minh phải lật để tìm ra thẻ in số K là bao nhiêu?

Lời giải:

Để tìm số lần lật thẻ nhiều nhất để tìm ra thẻ in số K trong dãy A = {0, 4, 9, 10, 12, 14, 17, 18, 20, 31, 34, 67} với phương pháp lật thẻ từ đầu đến cuối và quyết định lật tiếp theo dựa trên số ghi trên thẻ so với số K, ta có thể giả sử trường hợp xấu nhất là K nằm ở đầu dãy hoặc ở cuối dãy.

Nếu K nằm ở đầu dãy, ta sẽ cần lật tất cả các thẻ từ đầu đến khi lật thẻ in số K (lật tối đa 11 lần), sau đó lật thẻ in số K (1 lần), tổng cộng là 12 lần.

Nếu K nằm ở cuối dãy, ta sẽ cần lật tất cả các thẻ từ đầu đến cuối dãy trước khi lật thẻ in số K (lật tối đa 11 lần), sau đó lật thẻ in số K (1 lần), tổng cộng là 12 lần.

Vậy số lần nhiều nhất mà Minh phải lật để tìm ra thẻ in số K là 12 lần.

Luyện tập

Luyện tập 1 trang 93 Tin học 11: Em hãy chỉnh sửa thuật toán tìm tuần tự để tìm ra tất cả các phần tử trong dãy bằng giá trị cần tìm, biết dãy đó có nhiều phân tử bằng giá trị cần tìm.

Lời giải:

def timTatCaGiaTri(a, x):

 danhSach = []# Khởi tạo danh sách rỗng để lưu trữ các phần tử tìm thấy

 for i in range(len(a)):

  if a[i] == x:

   danhSach.append(i)# Nếu phần tử được duyệt là phần tử cần tìm, thêm chỉ số của nó vào danh sách

 return danhSach# Trả về danh sách chứa các chỉ số của các phần tử bằng giá trị cần tìm

Luyện tập 2 trang 93 Tin học 11: Viết chương trình của thuật toán tìm kiếm nhị phân với dãy sắp xếp giảm dần.

Lời giải:

def binary_search_reverse(arr, target):

 def binary_search_reverse_helper(arr, target, low, high):

  if low > high:

  return -1

 mid = (low + high) // 2

 if arr[mid] == target:

  return mid

 elif arr[mid] < target:

  return binary_search_reverse_helper(arr, target, low, mid - 1)

 else:

  return binary_search_reverse_helper(arr, target, mid + 1, high)

return binary_search_reverse_helper(arr, target, 0, len(arr) - 1)

# Sử dụng ví dụ đầu vào để kiểm tra

arr = [10, 8, 6, 4, 2]

target = 6

# Gọi hàm tìm kiếm nhị phân với dãy sắp xếp giảm dần

result = binary_search_reverse(arr, target)

if result != -1:

 print("Phần tử", target, "được tìm thấy tại vị trí", result)

else:

 print("Phần tử", target, "không tồn tại trong dãy.")

Vận dụng

Vận dụng 1 trang 93 Tin học 11: Cho A là danh sách tên các học sinh trong lớp, viết chương trình tìm kiếm tuần tự để tìm ra các học sinh có tên là Hoàn.

Lời giải:

def sequential_search(names, target):

 found = []

 for name in names:

  if name == target:

   found.append(name)

 return found

# Danh sách tên học sinh trong lớp

class_names = ["An", "Bình", "Cường", "Đạt", "Hoàn", "Minh", "Nam", "Thảo", "Hoàn", "Trung"]

# Tên học sinh cần tìm

target_name = "Hoàn"

# Danh sách tên học sinh trong lớp

class_names = ["An", "Bình", "Cường", "Đạt", "Hoàn", "Minh", "Nam", "Thảo", "Hoàn", "Trung"]

# Tên học sinh cần tìm

target_name = "Hoàn"

# Gọi hàm tìm kiếm tuần tự

found_names = sequential_search(class_names, target_name)

if len(found_names) > 0:

 print("Các học sinh có tên là", target_name, "là:", found_names)

else:

 print("Không tìm thấy học sinh nào có tên là", target_name)

Vận dụng 2 trang 93 Tin học 11: Cho A là danh sách tên các học sinh trong lớp được sắp xếp theo thứ tự bảng chữ cái, viết thương trình tìm kiếm nhị phân để tìm ra các học sinh có tên là Minh.

Lời giải:

def binary_search(names, target):

 low = 0

 high = len(names) - 1

 while low <= high:

  mid = (low + high) // 2

  mid_name = names[mid]

  if mid_name == target:

   return mid

  elif mid_name < target:

   low = mid + 1

  else:

   high = mid - 1

return -1

# Danh sách tên học sinh trong lớp (đã được sắp xếp theo thứ tự bảng chữ cái)

class_names = ["An", "Bình", "Cường", "Đạt", "Hoàn", "Minh", "Nam", "Thảo", "Trung"]

# Tên học sinh cần tìm

target_name = "Minh"

# Gọi hàm tìm kiếm nhị phân

result = binary_search(class_names, target_name)

if result != -1:

 print("Học sinh có tên là", target_name, "được tìm thấy tại vị trí", result)

else:

 print("Học sinh có tên là", target_name, "không tồn tại trong danh sách.")

Xem thêm lời giải bài tập Tin học lớp 11 Kết nối tri thức hay, chi tiết khác:

Giải Tin học 11 trang 89

Giải Tin học 11 trang 90

Giải Tin học 11 trang 91