Cho dãy các số A = (3, 1, 0, 10, 13, 16, 9, 7, 5, 11]

Sách trọng tâm Toán -Lý - Hóa - Văn -Anh 11 trên Shopee Mall

Giải Tin học 11 Bài 23: Kiểm thử và đánh giá chương trình - Kết nối tri thức

Vận dụng 1 trang 110 Tin học 11: Cho dãy các số A = (3, 1, 0, 10, 13, 16, 9, 7, 5, 11].

a) Viết chương trình mô tả thuật toán tìm kiếm phần tử C = 9 của dãy trên. Tính thời gian chính xác thực hiện công việc tìm kiếm này.

b) Giả sử dây A ở trên đã được sắp xếp theo thứ tự tăng dần: A= [0,1,3,5,7,9,10,11,13, 16]. Viết chương trình tìm kiếm nhị phân để tìm kiếm phân tử C = 9, đo thời gian thực hiện thuật toán. So sánh với kết quả 1ìm kiếm ở câu a.

Quảng cáo

Lời giải:

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.")

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.

Quảng cáo

Lời giải bài tập Tin học 11 Bài 23: Kiểm thử và đánh giá chương trình hay khác:

Quảng cáo

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 nhất, ngắn gọn khác:

Gói luyện thi online hơn 1 triệu câu hỏi đầy đủ các lớp, các môn, có đáp án chi tiết. Chỉ từ 200k!

Tủ sách VIETJACK shopee lớp 10-11 cho học sinh và giáo viên (cả 3 bộ sách):

Săn shopee siêu SALE :

ĐỀ THI, GIÁO ÁN, SÁCH LUYỆN THI DÀNH CHO GIÁO VIÊN VÀ PHỤ HUYNH LỚP 11

Bộ giáo án, bài giảng powerpoint, đề thi, sách dành cho giáo viên và gia sư dành cho phụ huynh tại https://tailieugiaovien.com.vn/ . Hỗ trợ zalo VietJack Official

Tổng đài hỗ trợ đăng ký : 084 283 45 85

Giáo án, bài giảng powerpoint Văn, Toán, Lí, Hóa....

4.5 (243)

799,000đs

199,000 VNĐ

Đề thi, chuyên đề Cánh diều, Kết nối tri thức, Chân trời sáng tạo...

4.5 (243)

799,000đ

99,000 VNĐ

Sách luyện 30 đề thi thử THPT năm 2025 mới

4.5 (243)

199,000đ

99.000 - 149.000 VNĐ

xem tất cả

Đã có app VietJack trên điện thoại, giải bài tập SGK, SBT Soạn văn, Văn mẫu, Thi online, Bài giảng....miễn phí. Tải ngay ứng dụng trên Android và iOS.