Hãy nhập câu hỏi của bạn vào đây, nếu là tài khoản VIP, bạn sẽ được ưu tiên trả lời.
THAM KHẢO!
1.Thuật toán sắp xếp chèn (Insertion Sort):
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
A = [5, 8, 1, 0, 10, 4, 3]
sorted_A = insertion_sort(A)
print("Dãy A sau khi sắp xếp chèn:", sorted_A)
2. Thuật toán sắp xếp chọn (Selection Sort):
def selection_sort(arr):
for i in range(len(arr)):
min_idx = i
for j in range(i + 1, len(arr)):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
A = [5, 8, 1, 0, 10, 4, 3]
sorted_A = selection_sort(A)
print("Dãy A sau khi sắp xếp chọn:", sorted_A)
3.Thuật toán sắp xếp nổi bọt (Bubble Sort):
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1):
for j in range(n - 1 - i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
A = [5, 8, 1, 0, 10, 4, 3]
sorted_A = bubble_sort(A)
print("Dãy A sau khi sắp xếp nổi bọt:", sorted_A)
Thuật toán tìm kiếm nhị phân thực hiện tìm kiếm một mảng đã sắp xếp bằng cách liên tục chia các khoảng tìm kiếm thành 1 nửa. Bắt đầu với một khoảng từ phần tử đầu mảng, tới cuối mảng. Nếu giá trị của phần tử cần tìm nhỏ hơn giá trị của phần từ nằm ở giữa khoảng thì thu hẹp phạm vi tìm kiếm từ đầu mảng tới giửa mảng và nguợc lại. Cứ thế tiếp tục chia phạm vi thành các nửa cho dến khi tìm thấy hoặc đã duyệt hết.
Thuật toán tìm kiếm nhị phân tỏ ra tối ưu hơn so với tìm kiếm tuyết tính ở các mảng có độ dài lớn và đã được sắp xếp. Ngược lại, tìm kiếm tuyến tính sẽ tỏ ra hiệu quả hơn khi triển khai trên các mảng nhỏ và chưa được sắp xếp.
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.
Def BinrySearch(A,K):
left=0
right=len(A)-1
while left<=right:
mid=(left+right)//2
if A[mid]==K:
return mid
elif A[mid]<K:
left=mid-1
else:
right=mid+1
return -1
input_file=open(“diemthi_sx.inp”)
ds_diem=[]
for line in input_file.readlines():
ds_diem.append(float(line))
input_file.close():
diem=float(input(‘nhập điểm số cần kiểm tra:’))
vitri=BanirySearch(ds_diem,diem)
if vitri==-1:
print(‘không tồn tại điểm số cần tìm trong danh sách’)
else:
print(‘điểm cần tìm nằm ở hàng thứ’,vitri,’trong danh sách’)
THAM KHẢO!
Nếu dãy ban đầu đã được sắp xếp, thì thuật toán sắp xếp chèn sẽ không thực hiện thay đổi nào trên dãy vì mỗi phần tử trong dãy đã đứng đúng vị trí của nó. Cụ thể, các bước của thuật toán sẽ được thực hiện như sau:
Xác định phần tử đầu tiên trong dãy là phần tử thứ 2 (i = 1), không cần thực hiện bất kỳ thay đổi nào vì phần tử này đã đứng đúng vị trí của nó trong dãy đã được sắp xếp.
Kiểm tra phần tử thứ 3 (i = 2) so với các phần tử trước nó trong dãy. Nếu phần tử này đã đứng đúng vị trí, không cần thực hiện thay đổi nào.
Tiếp tục kiểm tra và so sánh từng phần tử còn lại trong dãy với các phần tử trước nó. Nếu phần tử đang xét đã đứng đúng vị trí, không cần thực hiện thay đổi nào.
Sau khi kiểm tra hết các phần tử trong dãy, thuật toán kết thúc mà không có bất kỳ thay đổi nào được thực hiện trên dãy ban đầu, vì dãy đã được sắp xế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.
THAM KHẢO!
Các thuật toán sắp xếp như sắp xếp chèn, sắp xếp chọn và sắp xếp nổi bọt có ý nghĩa thực tế quan trọng trong nhiều tình huống khác nhau, bao gồm việc sắp xếp học sinh trong lớp theo chiều cao tăng dần. Dưới đây là một số ý nghĩa thực tế của các thuật toán sắp xếp:
-Tối ưu hóa thời gian thực thi: Các thuật toán sắp xếp giúp tối ưu hóa thời gian thực thi của các quy trình liên quan đến sắp xếp, giúp giảm bớt thời gian chờ đợi và tăng hiệu quả hoạt động của hệ thống. Ví dụ, khi sắp xếp các học sinh trong lớp theo chiều cao tăng dần, sử dụng thuật toán sắp xếp hiệu quả giúp đảm bảo quá trình sắp xếp nhanh chóng và đáp ứng được thời gian chờ đợi của học sinh và giáo viên.
-Tạo độ thứ tự: Các thuật toán sắp xếp giúp tạo ra độ thứ tự trong các tập dữ liệu, từ đó giúp dễ dàng tìm kiếm, tra cứu, phân tích hoặc xử lý dữ liệu sau này. Ví dụ, trong việc sắp xếp các học sinh trong lớp theo chiều cao tăng dần, độ thứ tự giúp giáo viên dễ dàng định vị vị trí của từng học sinh trong lớp học.
-Áp dụng trong nhiều lĩnh vực: Các thuật toán sắp xếp không chỉ được áp dụng trong lĩnh vực giáo dục, mà còn được sử dụng trong nhiều lĩnh vực khác như khoa học máy tính, công nghệ thông tin, tài chính, thương mại điện tử, kho dữ liệu, v.v. Ví dụ, trong công nghệ thông tin, sắp xếp dữ liệu giúp cải thiện hiệu suất của các thuật toán khác, chẳng hạn trong tìm kiếm dữ liệu, xử lý hình ảnh, xử lý âm thanh, v.v.
-Nền tảng cho các thuật toán phức tạp hơn: Các thuật toán sắp xếp đóng vai trò là nền tảng cho nhiều thuật toán phức tạp.
Nếu dãy A đã được sắp xếp theo thứ tự tăng dần thì có thể cải tiến thuật toán tốt hơn.