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.
Thuật toán tìm kiếm nhị phân được thực hiện trên một danh sách đã được (1) sắp xếp. Bắt đầu từ vị trí ở (2) giữa của danh sách. Tại mỗi bước, ta so sánh giá trị cần tìm với giá trị ở vị trí đó. Nếu giá trị cần tìm lớn hơn, ta tìm ở (3) nửa phải của danh sách. Nếu nhỏ hơn, ta tìm ở (4) nửa trái của danh sách.
Thuật toán tìm kiếm nhị phân được mô tả bằng ngôn ngữ tự nhiên:
- Bước 1: Xác định danh sách (mảng) đã được sắp xếp theo thứ tự tăng dần hoặc giảm dần.
- Bước 2: Đặt hai biến trái và phải lần lượt là chỉ số phần tử đầu và phần tử cuối của danh sách.
- Bước 3: Tính chỉ số giữa = (trái + phải) / 2 (lấy phần nguyên).
- Bước 4: So sánh giá trị cần tìm với phần tử ở vị trí giữa:
+ Nếu bằng, thì kết thúc và trả về vị trí giữa.
+ Nếu nhỏ hơn, thì cập nhật phải = giữa - 1 để tiếp tục tìm trong nửa bên trái.
+ Nếu lớn hơn, thì cập nhật trái = giữa + 1 để tiếp tục tìm trong nửa bên phải.
- Bước 5: Lặp lại bước 3 và bước 4 cho đến khi tìm thấy hoặc khi trái > phải (nghĩa là không có phần tử cần tìm).
Vòng lặp 1:
Dãy ban đầu: 3, 2, 4, 1, 5
Tìm số nhỏ nhất từ vị trí 0 đến 4 → là 1
Đổi chỗ 1 với 3
Kết quả sau vòng 1: 1, 2, 4, 3, 5
Vòng lặp 2:
Dãy hiện tại: 1, 2, 4, 3, 5
Tìm số nhỏ nhất từ vị trí 1 đến 4 → là 2
Đã đúng vị trí → không đổi
Kết quả sau vòng 2: 1, 2, 4, 3, 5
Vòng lặp 3:
Dãy hiện tại: 1, 2, 4, 3, 5
Tìm số nhỏ nhất từ vị trí 2 đến 4 → là 3
Đổi chỗ 3 với 4
Kết quả sau vòng 3: 1, 2, 3, 4, 5
Vòng lặp 4:
Dãy hiện tại: 1, 2, 3, 4, 5
Tìm số nhỏ nhất từ vị trí 3 đến 4 → là 4
Đã đúng vị trí → không đổi
Kết quả sau vòng 4: 1, 2, 3, 4, 5
Kết luận:
Dãy số sau khi sắp xếp tăng dần là: 1, 2, 3, 4, 5
Kết quả VL1: 1, 2, 4, 3, 5
Kết quả VL2: 1, 2, 4, 3, 5
Kết quả VL3: 1, 2, 3, 4, 5
Kết quả VL4: 1, 2, 3, 4, 5
Kết quả VL5: 1, 2, 3, 4, 5
Cách làm theo tìm kiếm nhị phân:
- Xác định khoảng cần tìm: từ 1001 đến 1500.
- Tìm số ở giữa: \(\frac{1001 + 1500}{2} = 1250 , 5 \approx 1250\).
- So sánh 1320 với 1250. Vì 1320 > 1250, ta bỏ nửa trái (1001 → 1250), chỉ giữ nửa phải (1251 → 1500).
- Lấy số giữa của khoảng mới: \(\frac{1251 + 1500}{2} = 1375 , 5 \approx 1375\).
- So sánh 1320 với 1375. Vì 1320 < 1375, ta bỏ nửa phải (1375 → 1500), chỉ giữ nửa trái (1251 → 1374).
- Lấy số giữa của khoảng mới: \(\frac{1251 + 1374}{2} = 1312 , 5 \approx 1312\).
- So sánh 1320 với 1312. Vì 1320 > 1312, ta bỏ nửa trái, giữ nửa phải (1313 → 1374).
- Lấy số giữa: \(\frac{1313 + 1374}{2} = 1343 , 5 \approx 1343\).
- So sánh 1320 với 1343. Vì 1320 < 1343, ta giữ nửa trái (1313 → 1342).
- Lấy số giữa: \(\frac{1313 + 1342}{2} = 1327 , 5 \approx 1327\).
- So sánh 1320 với 1327. Vì 1320 < 1327, ta giữ nửa trái (1313 → 1326).
- Lấy số giữa: \(\frac{1313 + 1326}{2} = 1319 , 5 \approx 1319\).
- So sánh 1320 với 1319. Vì 1320 > 1319, ta giữ nửa phải (1320 → 1326).
- Lấy số giữa: \(\frac{1320 + 1326}{2} = 1323\).
- So sánh 1320 với 1323. Vì 1320 < 1323, ta giữ nửa trái (1320 → 1322).
- Lấy số giữa: \(\frac{1320 + 1322}{2} = 1321\).
- So sánh 1320 với 1321. Vì 1320 < 1321, ta giữ nửa trái (1320 → 1320).
- Còn lại đúng một số 1320 → tìm thấy chiếc điện thoại cần mua. ✅
Vì tìm kiếm nhị phân cần danh sách đã sắp xếp để biết chắc phần tử cần tìm nằm ở bên trái hay bên phải. Nếu không sắp xếp, ta không thể loại bỏ nửa danh sách một cách chính xác
Sự khác biệt cơ bản nhất là thuật toán tìm kiếm nhị phân yêu cầu dữ liệu phải được sắp xếp, trong khi thuật toán tìm kiếm tuần tự không có yêu cầu này. Ngoài ra, cách thức tìm kiếm của thuật toán nhị phân là chia để trị, còn thuật toán tuần tự là duyệt lần lượt từng phần tử
Tìm kiếm tuần tự duyệt từng phần tử một, không cần sắp xếp. Tìm kiếm nhị phân chia đôi danh sách mỗi bước, cần sắp xếp trước.
đây nhé
Dãy ban đầu: [7.5, 9.0, 6.0, 8.5, 7.0]
- Lượt 1: so sánh dần, đổi chỗ → [7.5, 6.0, 8.5, 7.0, 9.0]
- Lượt 2: tiếp tục đổi chỗ → [6.0, 7.5, 7.0, 8.5, 9.0]
- Lượt 3: tiếp tục → [6.0, 7.0, 7.5, 8.5, 9.0]
- Lượt 4: dãy đã đúng thứ tự.
Kết quả: [6.0, 7.0, 7.5, 8.5, 9.0]
a) Đúng
b) Sai. Nếu mã số cần tìm là 2350 mà ở giữa là 3000, thì ta phải tìm tiếp ở nửa bên trái (nhỏ hơn), chứ không phải nửa bên phải.
c) Đúng
d) Đúng
Đáp án : 1. Phần tử có giá trị nhỏ nhất trong dãy được tìm thấy và đổi chỗ cho phần tử đứng đầu dãy.
Cần phải tìm kiếm thuật toán tuần tự4step to find number 7 in list. Thuật toán sẽ kiểm tra từng số một, bắt đầu từ số đầu tiên (1), sau đó đến số thứ hai (4), rồi đến số thứ ba (6), và cuối cùng là số thứ tư (7), và tại đây thuật toán sẽ dừng lại vì đã tìm thấy số cần tìm.
Thuật toán tìm kiếm tuần tự cần 4 bước để tìm thấy số 7 trong danh sách. Thuật toán sẽ lần lượt so sánh số cần tìm (7) với từng phần tử trong danh sách, bắt đầu từ phần tử đầu tiên (1), sau đó đến 4, rồi đến 6, và cuối cùng là 7. Ở bước thứ 4, thuật toán sẽ tìm thấy số 7.
baf. Già
cay à
Cần 4 bước để thực hiện
Theo thuật toán tìm kiếm tuần tự thì ta cần 4 bước để tìm số 7
4 bước
Cần thực hiện 4 bước.
Thuật toán tìm kiếm tuần tự cần 4 bước để tìm ra số 7
bước 1: so sánh 1 với 7
+) vì 7 lớn hơn 1 tiếp tục
bước 2: so sánh 4 với 7
+) vì 7 lớn hơn 4 tiếp tục
bước 3: so sánh 6 với 7
+) vì 7 lớn hơn 6 tiếp tục
Bước 4: so sánh 7 với 7
+) vì 7 bằng 7 đã tìm thấy thuật toán kết thúc
Thuật toán tìm kiếm tuần tự cần thực hiện 5 bước để tìm được 7
Các bước thực hiện cụ thể: Bước 1: Kiểm tra phần tử đầu tiên là số . ( ) Tiếp tục. Bước 2: Kiểm tra phần tử thứ hai là số . ( ) Tiếp tục. Bước 3: Kiểm tra phần tử thứ ba là số . ( ) Tiếp tục. Bước 4: Kiểm tra phần tử thứ tư là số . ( ) Tìm thấy! Thuật toán dừng lại. Kết luận: Cần thực hiện 4 bước để tìm thấy số .
Bước 1: kiểm tra số 1—chưa đúng
Bước 2 : kiểm tra số 4— chưa đúng
Bước 3 :kiểm tra số 6— chưa đúng
Bước 4: kiểm tra số 7— đúng , dừng lại
Vậy thuật toán tìm kiếm tuần tự tìm 4 bước để tìm thấy số 7
Phải qua bốn lần lặp
Danh sách:[1,4,6,7,8,10] tìm số 7
Bước 1: số sánh với 1 chưa đúng
Bước 2: so sánh với 4 chưa đúng
Bước 3: số sánh với 6 chưa đúng
Bước 4: số sánh với 7 tìm thấy
Bước 1: So sánh với số thứ nhất (1) -> Không phải 7. Bước 2: So sánh với số thứ hai (4) -> Không phải 7. Bước 3: So sánh với số thứ ba (6) -> Không phải 7. Bước 4: So sánh với số thứ tư (7) -> Tìm thấy số 7. Vậy, thuật toán cần thực hiện 4 bước để tìm thấy số 7.
cần thực hiện 4 bước dể tìm thấy số 7
Cần thực hiện 7 bước để tìm thấy số7
b1: kiểm tra số đầu tiên 1 khác 7, tiếp tục
b2: kiểm tra số thứ 2 4 khác 7, tiếp tục
b3: kiểm tra số thứ 3 6 khác 7, tiếp tục
b4 kiểm tra phần tử thứ 4 là 7=7, dừng lại vì tìm thấy
kết luận thuật toán cần thực hiện 4 bước để tìm thấy số 7
5 bước
4 bước
4 bước