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.
*Thuật toán sắp xếp chèn (Insertion Sort):
import time
def insertion_sort(arr):
n = len(arr)
for i in range(1, n):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
# Dãy số nguyên đầu vào
A = [3, 1, 0, 10, 13, 16, 9, 7, 5, 1]
# In dãy số nguyên trước khi sắp xếp
print("Dãy số nguyên trước khi sắp xếp:", A)
# Bắt đầu đo thời gian thực hiện thuật toán
start_time = time.time()
# Gọi hàm sắp xếp chèn
insertion_sort(A)
# Kết thúc đo thời gian thực hiện thuật toán
end_time = time.time()
# In dãy số nguyên sau khi sắp xếp
print("Dãy số nguyên sau khi sắp xếp:", A)
# In thời gian thực hiện thuật toán
print("Thời gian thực hiện thuật toán: {:.6f} giây".format(end_time - start_time))
Thời gian thực hiện là 0 giây
*Thuật toán sắp xếp chọn:
import time
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
# Dãy số nguyên đầu vào
A = [3, 1, 0, 10, 13, 16, 9, 7, 5, 1]
# In dãy số nguyên trước khi sắp xếp
print("Dãy số nguyên trước khi sắp xếp:", A)
# Bắt đầu đo thời gian thực hiện thuật toán
start_time = time.time()
# Gọi hàm sắp xếp chọn
selection_sort(A)
# Kết thúc đo thời gian thực hiện thuật toán
end_time = time.time()
# In dãy số nguyên sau khi sắp xếp
print("Dãy số nguyên sau khi sắp xếp:", A)
# In thời gian thực hiện thuật toán
print("Thời gian thực hiện thuật toán: {:.6f} giây".format(end_time - start_time))
Thời gian thực hiện là: 0 giây
*Thuật toán sắp xếp nổi bọt:
import time
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1):
for j in range(n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
# Dãy số nguyên đầu vào
A = [3, 1, 0, 10, 13, 16, 9, 7, 5, 1]
# In dãy số nguyên trước khi sắp xếp
print("Dãy số nguyên trước khi sắp xếp:", A)
# Bắt đầu đo thời gian thực hiện thuật toán
start_time = time.time()
# Gọi hàm sắp xếp nổi bọt
bubble_sort(A)
# Kết thúc đo thời gian thực hiện thuật toán
end_time = time.time()
# In dãy số nguyên sau khi sắp xếp
print("Dãy số nguyên sau khi sắp xếp:", A)
# In thời gian thực hiện thuật toán
print("Thời gian thực hiện thuật toán: {:.6f} giây".format(end_time - start_time))
Thời gian thực hiện là: 0 giây
Công việc của hàm là thực hiện sắp xếp.
Độ phức tạp của thuật toán là O(n2)
a)
import time
def linear_search(arr, x):
"""
Tìm kiếm tuyến tính trong dãy arr để tìm giá trị x.
Trả về vị trí của x trong dãy nếu x được tìm thấy, -1 nếu không tìm thấy.
"""
n = len(arr)
for i in range(n):
if arr[i] == x:
return i
return -1
# Dãy số A
A = [3, 1, 0, 10, 13, 16, 9, 7, 5, 11]
# Phần tử cần tìm kiếm
C = 9
# Bắt đầu đo thời gian
start_time = time.perf_counter()
# Tìm kiếm phần tử C trong dãy A
result = linear_search(A, C)
# Kết thúc đo thời gian
end_time = time.perf_counter()
if result != -1:
print(f"Phần tử {C} được tìm thấy tại vị trí {result} trong dãy A.")
else:
print(f"Phần tử {C} không có trong dãy A.")
print(f"Thời gian thực hiện thuật toán: {end_time - start_time} giây.")
b)
import time
def binary_search(arr, x):
"""
Tìm kiếm nhị phân trong dãy arr để tìm giá trị x.
Trả về vị trí của x trong dãy nếu x được tìm thấy, -1 nếu không tìm thấy.
"""
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == x:
return mid
elif arr[mid] < x:
left = mid + 1
else:
right = mid - 1
return -1
# Dãy số A đã được sắp xếp
A = [0, 1, 3, 5, 7, 9, 10, 11, 13, 16]
# Phần tử cần tìm kiếm
C = 9
# Bắt đầu đo thời gian
start_time = time.perf_counter()
# Tìm kiếm phần tử C trong dãy A bằng thuật toán tìm kiếm nhị phân
result = binary_search(A, C)
# Kết thúc đo thời gian
end_time = time.perf_counter()
if result != -1:
print(f"Phần tử {C} được tìm thấy tại vị trí {result} trong dãy A.")
else:
print(f"Phần tử {C} không có trong dãy A.")
print(f"Thời gian thực hiện thuật toán: {end_time - start_time} giây.")
-Thời gian thực hiện ở câu a là 8.99999,thời gian thực hiện ở câu b là 6,49999 giây.
Độ phức tạp của thuật toán sắp xếp nổi bọt là O(n2)
T = O(n) + O(n2) = O(n2)
#include <iostream>
#include <fstream>
int main()
{
std::ifstream f("daycon.inp");
int n,s,a[1001],d[100][1001];
f>>n>>s;
for(int i=1;i<=n;i++)
{
f>>a[i];
}
d[0][0]=0;
a[0]=0;
d[1][a[1]]=1;
for(int i=2;i<=n;i++)
{
for(int j=0;j<=s;j++)
{
d[i][j]=d[i-1][j];
if(j==a[i]&&d[i-1][j]<1)
d[i][j]=1;
else
if(a[i]<j&&d[i-1][j-a[i]]>0&&d[i-1][j-a[i]]+1>d[i][j])
d[i][j]=d[i-1][j-a[i]]+1;
}
}
for(int i=n;i>=1;i--)
{
if(d[i][s]!=d[i-1][s])
{
std::cout<<a[i]<<" ";
s-=a[i];
}
}
return 0;
}
1. Sắp xếp chèn (Insertion Sort)
Ý tưởng: Insertion Sort lấy ý tưởng từ việc chơi bài, dựa theo cách người chơi "chèn" thêm một quân bài mới vào bộ bài đã được sắp xếp trên tay.
2. Sắp xếp lựa chọn (Selection Sort)
Ý tưởng của Selection sort là tìm từng phần tử cho mỗi vị trí của mảng hoán vị A' cần tìm.
3. Sắp xếp nổi bọt (Bubble Sort)
Ý tưởng: Bubble Sort, như cái tên của nó, là thuật toán đẩy phần tử lớn nhất xuống cuối dãy, đồng thời những phần tử có giá trị nhỏ hơn sẽ dịch chuyển dần về đầu dãy. Tựa như sự nổi bọt vậy, những phần tử nhẹ hơn sẽ nổi lên trên và ngược lại, những phần tử lớn hơn sẽ chìm xuống dưới.
Bài 1:
const fi='mangmin.inp';
fo='mangmin.out';
var f1,f2:text;
a,vt:array[1..100]of integer;
n,i,dem:integer;
begin
assign(f1,fi); reset(f1);
assign(f2,fo); rewrite(f2);
readln(f1,n);
for i:=1 to n do
read(f1,a[i]);
min:=a[1];
for i:=1 to n do
if min>a[i] then min:=a[i];
dem:=0;
for i:=1 to n do
if min=a[i] then
begin
inc(dem);
vt[dem]:=i;
end;
writeln(f2,'Gia tri nho nhat la: ',min);
writeln(f2,'Vi tri cua gia tri nho nhat la: ');
for i:=1 to dem do
write(f2,vt[i]:4);
close(f1);
close(f2);
end.
Bài 2:
const fi='mangchan.inp';
fo='mangchan.out';
var f1,f2:text;
a:array[1..100]of integer;
n,i,t:integer;
begin
assign(f1,fi); reset(f1);
assign(f2,fo); rewrite(f2);
readln(f1,n);
for i:=1 to n do
read(f1,a[i]);
t:=0;
for i:=1 to n do
if a[i] mod 2=0 then t:=t+a[i];
writeln(f2,t);
close(f1);
close(f2);
end.
Bài 3:
const fi='tachxau.inp';
fo='tachxau.out';
var f1,f2:text;
s,s1,s2,s3,s4:string;
i,d:integer;
j,k,l:char;
begin
assign(f1,fi); reset(f1);
assign(f2,fo); rewrite(f2);
readln(f1,s);
d:=length(s);
s1:='';
for i:=1 to d do
if s[i] in ['0'..'9'] then s1:=s1+s[i];
writeln(f2,'Xau S1 la: ',s1);
s2:='';
for i:=1 to d do
if s[i] in ['a'..'z'] then s2:=s2+s[i];
writeln(f2,'Xau S2 la: ',s2);
s3:='';
for i:=1 to d do
if s[i] in ['A'..'Z'] then s3:=s3+s[i];
writeln(f2,'Xau S3 la: ',s3);
close(f1);
close(f2);
end.
Bài 4:
const fi='demtu.inp';
fo='demtu.out';
var s:string;
i,d,dem:integer;
kt:boolean;
f1,f2:text;
begin
assign(f1,fi); reset(f1);
assign(f2,fo); rewrite(f2);
readln(f1,s);
d:=length(s);
i:=0;
while i<=d do
begin
inc(i);
if ((i=1) and (s[i]=' ')) then
repeat
kt:=false;
if (s[i]=' ') then
begin
delete(s,i,1);
d:=length(s);
end
else kt:=true;
until (kt=true) or (i+1>d)
else repeat
kt:=false;
if (s[i]=' ') and (s[i+1]=' ') then
begin
delete(s,i,1);
d:=length(s);
end
else kt:=true;
until (kt=true) or (i+1>d);
d:=length(s);
end;
while s[d]=' ' do
begin
delete(s,d,1);
d:=length(s);
end;
dem:=0;
for i:=1 to d do
if s[i]=' ' then dem:=dem+1;
writeln(f2,dem+1);
close(f1);
close(f2);
end.
tham khảo!
Hai bộ dữ liệu đầu vào có cùng kích thước của thuật toán trên nhưng có thời gian chạy khác nhau có thể là:
- Bộ dữ liệu 1: A = [2, 4, 6, 8, 10] # Có 5 phần tử Kết quả mong đợi: Tổng các số chẵn là 30
- Bộ dữ liệu 2: A = [1, 3, 5, 7, 9] # Có 5 phần tử Kết quả mong đợi: Tổng các số chẵn là 0
Trong trường hợp này, cả hai bộ dữ liệu đều có cùng kích thước là 5 phần tử, nhưng thời gian chạy của thuật toán sẽ khác nhau vì số lượng số chẵn trong dãy số khác nhau. Bộ dữ liệu 1 chứa toàn số chẵn nên thời gian chạy của thuật toán sẽ lớn hơn bộ dữ liệu 2 chỉ chứa các số lẻ.