mô tả thuật toán sắp xếp chọn và thuật toán tìm kiếm tuần tự
K
Khách
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.
Những câu hỏi liên quan
TA
23 tháng 8 2023
- 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)
TA
23 tháng 8 2023
1.Thuật toán tìm kiếm tuần tự:
- Độ phức tạp thời gian của thuật toán tìm kiếm tuần tự là O(n)
- Giá trị lớn nhất của n với thời gian thực thi là 1 giây: n = 1 giây * (106 us / phép tính) = 106
- Giá trị lớn nhất của n với thời gian thực thi là 1 phút: n = 1 phút * (60 giây / phút) * (106us / phép tính) = 6 * 107
- Giá trị lớn nhất của n với thời gian thực thi là 1 giờ: n = 1 giờ * (60 phút / giờ) * (60 giây / phút) * (106us / phép tính) = 3.6 * 109
2.Thuật toán sắp xếp chèn:
- Độ phức tạp thời gian của thuật toán sắp xếp chèn là O(102
- Giá trị lớn nhất của n với thời gian thực thi là 1 giây: n = sqrt(1 giây * (106us / phép tính)) =103
- Giá trị lớn nhất của n với thời gian thực thi là 1 phút: n = sqrt(1 phút * (60 giây / phút) * (106us / phép tính)) = 6 * 104
- Giá trị lớn nhất của n với thời gian thực thi là 1 giờ: n = sqrt(1 giờ * (60 phút / giờ) * (60 giây / phút) * (106us / phép tính)) = 3.6 * 106
3. Thuật toán sắp xếp chọn:
- Độ phức tạp thời gian của thuật toán sắp xếp chọn là O(n2)
- Giá trị lớn nhất của n là: n = sqrt(1 giây * (106us / phép tính)) = 1000.
Thời gian thực thi là 1 phút:
Giá trị lớn nhất của n là: n = sqrt(1 phút * (60 giây / phút) * (106us / phép tính)) = 60000.
Thời gian thực thi là 1 giờ:
Giá trị lớn nhất của n là: n = sqrt(1 giờ * (60 phút / giờ) * (60 giây / phút) * (106us / phép tính)) = 3.6 * 106
QT
Quoc Tran Anh Le
Giáo viên
23 tháng 8 2023
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.
QT
Quoc Tran Anh Le
Giáo viên
9 tháng 11 2023
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.
29 tháng 10 2021
#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;
}
QT
Quoc Tran Anh Le
Giáo viên
23 tháng 8 2023
Tính đúng của thuật toán cần được chứng minh bằng lập luận toán học. Sử dụng các bộ dữ liệu kiểm thử có thể làm tăng độ tin cậy của chương trình nhưng chưa chứng minh được tính đúng của thuật toán.
NC
1
7 tháng 8 2017
Mô phỏng thuật toán
| A | -1 | 5 | 91 | 82 | -22 | -31 | 45 | 67 | 1 | 55 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
Kết quả: Dãy A không có số hạng có giá trị bằng k = 21