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
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 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!
Hãy sắp xếp danh sách {1,8,6,7,10,4,28} theo thứ tự tăng dần.Thuật toán tìm kiếm nhị phân cần bao nhiêu bước để tìm thấy số 10 trong danh sách vừa sắp xếp
Hãy sắp xếp danh sách {1,8,6,7,10,4,28} theo thứ tự tăng dần.Thuật toán tìm kiếm nhị phân cần bao nhiêu bước để tìm thấy số 10 trong danh sách vừa sắp xếp
Cho danh sách tên các bn hs trg lớp 7a1 như sau
Châu , Dũng , Hà, Ánh , Bảo ,Linh,thắng, nhàn,quyên
a, hãy sắp xếp lại danh sách theo thứ tự bảng chữ cái
b, Liệt kê các bước tìm kiếm tên bạn 'Thắng " theo thuật toán tìm kiếm nhị phâ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.
Viết chương trình nhập vào một mảng gồm n phần tử nguyên, hiển
thị mảng đã nhập ra màn hình, thực hiện sắp xếp mảng vừa nhập theo thứ tự tăng dần
bằng thuật toán sắp xếp chèn (Insert_sort). Sử dụng thuật toán tìm kiếm nhị phân để
tìm một phần tử k bất kỳ trong mảng, với k nhập từ bàn phím, hiển thị vị trí của k nếu
tìm thấy, và -1 nếu không tìm thấy k. (Viết bằng ngôn ngữ C++)
Em đã biết thiết kế một số thuật toán và chương trình: tìm kiếm tuần tự, tìm kiếm nhị phân, sắp xếp chèn, sắp xếp chọn, sắp xếp nổi bọt. Tất cả các thiết kế chương trình đó có điểm nào chung?
Theo em, để thiết kế một thuật toán đúng giải một bái toàn cho trước cần trải qua các bước như thế nào? Nêu quan điểm của riêng em và trao đổi với các bạn.
- Các thuật toán và chương trình mà em đã biết đều là các thuật toán cơ bản trong lập trình và giải quyết các vấn đề thông thường. Các điểm chung của chúng bao gồm: Tính đơn giản, độ phức tạp thấp.
- Theo em, để thiết kế một thuật toán đúng giải một bái toàn cho trước cần trải qua các bước:
1. Xác định bài toán
2. Tìm cấu trúc dữ liệu biểu diễn thuật toán.
3. Tìm Thuật Toán.
4. Lập Trình (Programming)
5. Kiểm thử chương trình (Testing program)
6. Tối ưu chương trình (optimization program)