Có thể áp dụng thuật toán tìm kiếm tuần tự cho dãy đã sắp thứ tự không? Tại sao?
Theo em, với dãy đã sắp thứ tự và cho một số x cụ thể
a) Trường hợp nào tìm kiếm tuần tự nhanh hơn tìm kiếm nhị phân?
b) Về trung bình thuật toán tìm kiếm tuần tự hay thuật toán tìm kiếm nhị phân tốt hơn?
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.
cho 1 dãy 10 thẻ đc đánh lộn xộn như sau: 15, 7,21, 35, 30, 50, 46, 47 , 44, 1
a) sắp xếp các thẻ theo thứ tự tăng dần
b) áp dụng thuật toán tìm kiếm nhị phân tìm thẻ số 50 trong danh sách đã sắp xếp
Có 2 loại bài toán tìm kiếm, đó là:1-Tìm kiếm dãy không sắp xếp tứ tự.
2-Tìm kiếm dãy đã sắp xếp thứ tự.
3-Tìm kiếm ngẫu nhiên.
Cho trước một đây số đã được sắp xếp theo thứ tự tăng dần. Hãy đọc, quan sát và thảo luận cách làm sau đây để hiểu được thuật toán tìm kiếm nhị phân, biết được tính ưu việt của thuật toán này so với thuật toán tìm kiếm tuần tự trên một dây các phần từ đã sắp xếp.
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.
Câu 1: Nêu công dụng và cú pháp của hàm SUM và COUNT. Cho ví dụ minh họa.
Câu 2: Có mấy loại bài toán tìm kiếm. Nêu ý tưởng của thuật toán tìm kiếm tuần tự.
Câu 3: Cho dãy số sau: 20, 13, 10, 5, 15, 27, 30. Sử dụng thuật toán tìm kiếm tuần tự, hãy tìm xem có số 15 ở trong dãy này hay không? Nếu có thì đưa ra vị trí đầu tiên tìm thấy.
Câu 4: Cho dãy số 3, 19, 7, 25, 65, 22, 30, 42, 45, 12. Sử dụng thuật toán tìm kiếm nhị phân để tìm số 40 trong dãy trên.
Cho dãy số sau 10,2,5,12,20,6,8,15,18 A,sắp xếp dãy số sau theo thứ tự tăng dần B,hãy liệt kê các bước tìm kiếm số 15 trong dãy số đã sắp xếp theo thuật toán tìm kiếm nhị phân
Giúp elm Vs ạ , mai em nộp r
Cho dãy số sau 10,2,5,12,20,6,8,15,18 A,sắp xếp dãy số sau theo thứ tự tăng dần B,hãy liệt kê các bước tìm kiếm số 15 trong dãy số đã sắp xếp theo thuật toán tìm kiếm nhị phân
Giúp em Vs ạ , mai em nộp r
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ll a[]={10,2,5,12,20,6,8,15,18}; //mảng đã cho
ll n=sizeof(a)/sizeof(a[0]); //độ dài mảng
sort(a,a+n); //sắp xếp mảng
//Thuật toán tìm kiếm nhị phân
ll l=0, r=n-1;
while(l<=r) {
ll mid=(l+r)/2; //Tìm phần tử giữa left và right
if(a[mid]<15) l=mid+1; //Vì từ đoạn [0,mid] thì phần tử nhỏ hơn 15 nên ta duyệt từ khoảng (mid,r]
else r=mid-1; //vì thấy nên rút r để thu hẹp phạm vi
}
cout << l+1; //in ra kq (vì bắt đầu từ 0 đến n-1 nên phải tăng thêm để ra vị trí đúng)
}
(Bạn có thể dựa vào code mình để rút ra các bước)
Chúc bạn học tốt!
Cho dãy số sau 10,2,5,12,20,6,8,15,18 A,sắp xếp dãy số sau theo thứ tự tăng dần B,hãy liệt kê các bước tìm kiếm số 15 trong dãy số đã sắp xếp theo thuật toán tìm kiếm nhị phân Giúp elm Vs ạ , mai em nộp r
Bài học trước cho em tháy việc tìm kiếm trên một dãy đã sắp xếp nhanh hơn với việc tìm kiếm tuần tự. Vì vậy bài toán tìm kiếm liên quan mật thiết đến bài toán sắp xếp. Bài toán sắp xếp cơ bản có dạng như sau:
Cho dãy A gồm n phần tử:
A[0], A[1], ….,A[n - 1] (1)
Cần sắp xếp dãy A theo thứ tự tăng dần:
A[0] ≤ A[1] ≤ ... ≤ A[n - 1]
(2)Em hãy trình bày ý tưởng của mình để giải bài toán sắp xếp với dãy có bốn phần tử.
Em có thể thực hiện như sau:
- Duyệt qua từng phần tử của dãy từ đầu đến cuối.
- So sánh hai phần tử liền kề, nếu phần tử sau lớn hơn phần tử trước thì hoán đổi chúng.
- Tiếp tục duyệt qua các phần tử còn lại cho đến khi không còn phần tử nào cần hoán đổi.
- Lặp lại quá trình trên cho đến khi toàn bộ dãy được sắp xếp.
Hoặc:
-Duyệt qua từng phần tử của dãy từ đầu đến cuối.
-Lưu giá trị của phần tử hiện tại vào biến tạm thời.
-So sánh phần tử hiện tại với các phần tử bên trái, nếu phần tử nào lớn hơn phần tử hiện tại thì dời chúng sang phải một vị trí.
-Chèn giá trị của phần tử hiện tại vào vị trí đúng sau khi dời các phần tử.
-Tăng vị trí phần tử hiện tại lên 1 và lặp lại quá trình trên cho đến khi toàn bộ dãy được sắp xếp.
Mô phỏng thuật toán tìm kiếm tuần tự với dãy B: 1 - 5 - 7 - 6 với k = 7
Mô phỏng thuật toán tìm kiếm tuần tự với dãy B: 1 - 5 - 7 - 6 với k = 9
Làm ơn trình bày giúp mik nha
#include <bits/stdc++.h>
using namespace std;
long long x,i,n,k;
int main()
{
cin>>n>>k;
for (i=1; i<=n; i++)
{
cout<<x;
if (x==k) cout<<i<<" ";
}
return 0;
}