Vận dụng 1 trang 110 SGK Tin học 11 Kết nối tri thức - KNTT

a)

import time

def linear_search(arr, x):

 """

 Tìm kiếm tuyến tính trong dãy arr để tìm giá trị x.

 Trả về vị trí của x trong dãy nếu x được tìm thấy, -1 nếu không tìm thấy.

 """

 n = len(arr)

 for i in range(n):

  if arr[i] == x:

   return i

 return -1

# Dãy số A

A = [3, 1, 0, 10, 13, 16, 9, 7, 5, 11]

# Phần tử cần tìm kiếm

C = 9

# Bắt đầu đo thời gian

start_time = time.perf_counter()

# Tìm kiếm phần tử C trong dãy A

result = linear_search(A, C)

# Kết thúc đo thời gian

end_time = time.perf_counter()

if result != -1:

 print(f"Phần tử {C} được tìm thấy tại vị trí {result} trong dãy A.")

else:

 print(f"Phần tử {C} không có trong dãy A.")

print(f"Thời gian thực hiện thuật toán: {end_time - start_time} giây.")

b)

import time

def binary_search(arr, x):

 """

 Tìm kiếm nhị phân trong dãy arr để tìm giá trị x.

 Trả về vị trí của x trong dãy nếu x được tìm thấy, -1 nếu không tìm thấy.

 """

 left, right = 0, len(arr) - 1

 while left <= right:

  mid = (left + right) // 2

  if arr[mid] == x:

   return mid

  elif arr[mid] < x:

   left = mid + 1

  else:

   right = mid - 1

 return -1

# Dãy số A đã được sắp xếp

A = [0, 1, 3, 5, 7, 9, 10, 11, 13, 16]

# Phần tử cần tìm kiếm

C = 9

# Bắt đầu đo thời gian

start_time = time.perf_counter()

# Tìm kiếm phần tử C trong dãy A bằng thuật toán tìm kiếm nhị phân

result = binary_search(A, C)

# Kết thúc đo thời gian

end_time = time.perf_counter()

if result != -1:

 print(f"Phần tử {C} được tìm thấy tại vị trí {result} trong dãy A.")

else:

 print(f"Phần tử {C} không có trong dãy A.")

print(f"Thời gian thực hiện thuật toán: {end_time - start_time} giây.")

- Thời gian thực hiện ở câu a là 8.99999,thời gian thực hiện ở câu b là 6,49999 giây.

-- Mod Tin Học 11 HỌC247