Em hãy sắp xếp các phần được đánh số trong Hình 6.4 để được thuật toán tính trung bình cộng của hai số a và b.
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.
a) đầu vào : hai số a và b
đầu ra : trung bình cộng của 2 số a và b
b) đầu vào : hai số tự nhiên a và b
đầu ra : ước chung lớn nhất của hai số tự nhiên a và b
a) đầu vào : hai số a và b
đầu ra : trung bình cộng của 2 số a và b
b) đầu vào : hai số tự nhiên a và b
đầu ra : ước chung lớn nhất của hai số tự nhiên a và b
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.
#include <bits/stdc++.h>
using namespace std;
long long n,i,x,t,dem;
int main()
{
cin>>n;
dem=0;
t=0;
for (i=1; i<=n; i++)
{
cin>>x;
if (x%2!=0)
{
dem++;
t=t+x;
}
}
double s=t*1.0/dem*1.0;
cout<<fixed<<setprecision(2)<<s;
return 0;
}
1. Tính số lần lặp của vòng lặp bên trong của thuật toán sắp xếp chèn tuyến tính.
2. Tính số lần lặp của vòng lặp ngoài của thuật toán sắp xếp chèn tuyến tính.
3. Ước lượng độ phức tạp thời gian của thuật toán sắp xếp chèn tuyến tính:
Vòng lặp for bên ngoài kiểm soát việc thực hiện đúng n-1 bước.
Vòng lặp while lồng bên trong thực hiện đồng thời cùng lúc hai việc a) và b) theo cách dịch chuyển dần từng bước sang trái, từ vị trí i tới vị trí k+1
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
Các bước của thuật toán tính trung bình cộng của hai số a và b là: 1 → 3 → 2 → 4 → 6 → 5.