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.
Sau lần chia đôi đầu tiên, pham vi tìm kiếm còn lại n/2 số, sau khi chia đôi lần thứ hai, dãy còn lại n/4 số, sau khi chia đôi lần thứ dãy còn lại n/8, …sau khi chia đôi lần k dãy còn lại n/2.mũ k. Kết thúc khi 2 mũ k sấp xỉ n.
Tham khảo:
Viết chương trình Python thực hiện thuật toán sắp xếp chèn tuyến tính dựa trên mã giả đã cho trong báo học:
void Insertion_Sort(int a[], int n){
int pos, i;
int x;//lưu giá trị a[i] tránh bị ghi đè khi dời chỗ các phần tử
for(i=1; i<n; i++){//đoạn a[0] đã sắp xếp
x = a[i]; pos = i-1;
//tìm vị trí chèn x
while((pos>=0)&&(a[pos]>x)){
//kết hợp dời chỗ các phần tử sẽ đứng sau x trong danh sách mới
a[pos+1] = a[pos];
pos--;
}
a[pos+1] = x;//chèn x vào danh sách
}
}
void main()
{
int a[5] = {8, 4, 1, 6, 5};
Insertion_Sort(a, 5);
cout<<"Mang sau khi sap xep:"<<endl;
for(int i=0;i<5;i++){
cout<<a[i]<<" ";
}
system("pause");
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.
a. Thuật toán 1 :
Máy tính sẽ thực hiện 10 vòng lặp , khi kết thúc thuật toán giá trị của S = 5.0
Đoạn chương trình Pascal tương ứng:
Quảng cáo
S := 10; x := 0.5;
While S > 5.2 do
S := S – x;
Writeln(S);
b. Thuật toán 2 :
Máy tính sẽ không thực hiện vòng lặp nào do điều kiện không thỏa mãn, khi kết thúc thuật toán giá trị của S = 10
Đoạn chương trình Pascal tương ứng:
S := 10; n := 0;
While S < 10 do
Begin
n := n + 3;
S := S – n
End;
Writeln(S);
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