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
Trả lời Vận dụng 1 trang 110 Tin học 11 sách Kết nối tri thức hay, chi tiết sẽ giúp học sinh dễ dàng làm bài tập Tin học 11.
Giải Tin học 11 Bài 23: Kiểm thử và đánh giá chương trình
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.
Lời giải:
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.
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:
Câu hỏi trang 110 Tin học 11: Hai tiêu chỉ đánh giá độ phức tạp tính toán quan trọng nhất là gì?
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].
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:
Bài 18: Thực hành dữ liệu mảng một chiều và hai chiều
Bài 20: Thực hành bài toán tìm kiếm
Xem thêm các chương trình khác:
- Soạn văn lớp 11 Kết nối tri thức - hay nhất
- Văn mẫu lớp 11 - Kết nối tri thức
- Tóm tắt tác phẩm Ngữ văn 11 – Kết nối tri thức
- Tác giả tác phẩm Ngữ văn 11 - Kết nối tri thức
- Giải SBT Ngữ văn 11 – Kết nối tri thức
- Bố cục tác phẩm Ngữ văn 11 – Kết nối tri thức
- Giải Chuyên đề học tập Ngữ văn 11 – Kết nối tri thức
- Nội dung chính tác phẩm Ngữ văn lớp 11 – Kết nối tri thức
- Soạn văn 11 Kết nối tri thức (ngắn nhất)
- Giải sgk Toán 11 – Kết nối tri thức
- Giải Chuyên đề học tập Toán 11 – Kết nối tri thức
- Lý thuyết Toán 11 - Kết nối tri thức
- Giải sbt Toán 11 – Kết nối tri thức
- Bài tập Tiếng Anh 11 Global success theo Unit có đáp án
- Giải sgk Tiếng Anh 11 – Global success
- Giải sbt Tiếng Anh 11 - Global Success
- Trọn bộ Từ vựng Tiếng Anh 11 Global success đầy đủ nhất
- Ngữ pháp Tiếng Anh 11 Global success
- Giải sgk Vật lí 11 – Kết nối tri thức
- Lý thuyết Vật lí 11 – Kết nối tri thức
- Giải sbt Vật lí 11 – Kết nối tri thức
- Giải Chuyên đề học tập Vật lí 11 – Kết nối tri thức
- Chuyên đề dạy thêm Vật lí 11 cả 3 sách (2024 có đáp án)
- Giải sgk Hóa học 11 – Kết nối tri thức
- Giải Chuyên đề học tập Hóa học 11 – Kết nối tri thức
- Lý thuyết Hóa 11 - Kết nối tri thức
- Giải sbt Hóa học 11 – Kết nối tri thức
- Chuyên đề dạy thêm Hóa 11 cả 3 sách (2024 có đáp án)
- Giải sgk Sinh học 11 – Kết nối tri thức
- Lý thuyết Sinh học 11 – Kết nối tri thức
- Giải Chuyên đề học tập Sinh học 11 – Kết nối tri thức
- Giải sbt Sinh học 11 – Kết nối tri thức
- Giải sgk Giáo dục Kinh tế và Pháp luật 11 – Kết nối tri thức
- Giải Chuyên đề học tập Kinh tế pháp luật 11 – Kết nối tri thức
- Lý thuyết Kinh tế pháp luật 11 – Kết nối tri thức
- Giải sbt Kinh tế pháp luật 11 – Kết nối tri thức
- Giải sgk Lịch sử 11 – Kết nối tri thức
- Giải Chuyên đề học tập Lịch sử 11 – Kết nối tri thức
- Lý thuyết Lịch sử 11 - Kết nối tri thức
- Giải sbt Lịch sử 11 – Kết nối tri thức
- Giải sgk Địa lí 11 – Kết nối tri thức
- Giải Chuyên đề học tập Địa lí 11 – Kết nối tri thức
- Lý thuyết Địa lí 11 - Kết nối tri thức
- Giải sbt Địa lí 11 – Kết nối tri thức
- Giải sgk Công nghệ 11 – Kết nối tri thức
- Lý thuyết Công nghệ 11 - Kết nối tri thức
- Giải sbt Công nghệ 11 – Kết nối tri thức
- Giải sgk Giáo dục quốc phòng an ninh 11 – Kết nối tri thức
- Lý thuyết Giáo dục quốc phòng 11 – Kết nối tri thức
- Giải sbt Giáo dục quốc phòng 11 – Kết nối tri thức
- Giải sgk Hoạt động trải nghiệm 11 – Kết nối tri thức