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
*Chương trình 1:
from collections import Counter
import time
n = 1000
c = 0
# Ghi lại thời điểm bắt đầu
start_time = time.time()
for k in range(n):
c = c + 1
# Ghi lại thời điểm kết thúc
end_time = time.time()
# Tính thời gian hoàn thành
elapsed_time = end_time - start_time
# Sử dụng hàm Counter để đếm số lần lặp
counter = Counter(range(n))
# In số lần lặp
print("Số lần lặp: {}".format(counter))
# In thời gian thực thi
print("Thời gian thực thi của chương trình: {:.6f} giây".format(elapsed_time))
*Chương trình 2:
import time
n = 1000
c = 0
# Ghi lại thời điểm bắt đầu
start_time = time.perf_counter()
for k in range(n):
for j in range(n):
c = c + 1
# Ghi lại thời điểm kết thúc
end_time = time.perf_counter()
# Tính thời gian hoàn thành
elapsed_time = end_time - start_time
# In số lần lặp
print("Số lần lặp: {}".format(c))
# In thời gian thực thi
print("Thời gian thực thi của chương trình: {:.6f} giây".format(elapsed_time))
→Sự khác biệt độ phức tạp thời gian của 2 chương trình trên:
Độ phức tạp thời gian của chương trình 1 là O(1), còn độ phức tạp thời gian của chương trình 2 là O(n2).
Tham khảo:
Xác định cách thức sắp xếp chèn: Sắp xếp chèn là một thuật toán đơn giản, trong đó từng phần tử của dãy đang xét được chèn vào vị trí đúng của dãy con đã được sắp xếp trước đó. Bước này định nghĩa cách thức sắp xếp chèn, bao gồm quá trình so sánh và di chuyển các phần tử để đưa phần tử mới vào vị trí đúng.
1. Bước này đã định nghĩa cách thức sắp xếp chèn, bao gồm cách thức so sánh và di chuyển các phần tử để đưa phần tử mới vào vị trí đúng của dãy con đã được sắp xếp trước đó.
2. Kết quả của bước này khác với kết quả của bước trước đó về cách thức sắp xếp chèn được định nghĩa và thực hiện. Bước này tập trung vào việc định nghĩa và triển khai thuật toán sắp xếp chèn cụ thể, trong khi bước trước đó có thể là các bước chuẩn bị dữ liệu, định nghĩa bài toán, hoặc thiết kế các thuật toán phụ trợ khác.
– Sử dụng hàm sum để tính tổng và điểm trung bình.
- Gọi hàm Python thực hiện sắp xếp thứ tự tăng dần (không giảm); sau khi sắp xếp thì tìm được ngay max, min.
- Dãy số đã sắp thứ tự tăng dần (không giảm) nên có thể dùng hàm bisect left (trong mô đun bisect) tìm được các vị trí phân chia dãy điểm thành 4 đoạn điểm: Chưa đạt, Đạt, Khá và Tốt. Từ đó tính được số lượng điểm theo từng mức xếp hạng.
THAM KHẢO!
Dựa vào hai yếu tố là thời gian thực hiện thuật toán (còn gọi là độ phức tạp thuật toán) và dung lượng bộ nhớ cần thiết để lưu trữ dữ liệu.
Thuật toán tối ưu là sử dụng ít thời gian, ít bộ nhớ, ít phép toán, giải bài toán trên máy tính thường được tiến hành qua 5 bước xác định bài toán, lựa chọn hoặc thiết kế thuật toán, viết chương trình, hiệu chỉnh và viết tài liệu.
Dựa vào hai yếu tố là thời gian thực hiện thuật toán (còn gọi là độ phức tạp thuật toán) và dung lượng bộ nhớ cần thiết để lưu trữ dữ liệu.
Thuật toán tối ưu là sử dụng ít thời gian, ít bộ nhớ, ít phép toán, giải bài toán trên máy tính thường được tiến hành qua 5 bước xác định bài toán, lựa chọn hoặc thiết kế thuật toán, viết chương trình, hiệu chỉnh và viết tài liệu.
Tham khảo:
def nhapDL(finp):
f = open(finp)
A = []
B = []
for line in f:
s = line.split()
A.append(s[0])
temp = s[1:len(s)]
temp = [float(x) for x in temp]
B.append(temp)
f.close()
return A, B
def diem_gk(d):
diem = sum(d) + d[0] + d[len(d) - 1]
diem = diem / (len(d) + 2)
return round(diem, 2)
def xuly(B):
kq = []
for i in range(len(B)):
diem = diem_gk(B[i])
kq.append(diem)
return kq
def ghiDL(fout, A, B):
f = open(fout, "w")
A, B = zip(*sorted(zip(A, B), key=lambda x: x[1], reverse=True))
for i in range(len(A)):
print(A[i], B[i], file=f)
f.close()
finp = "seagames.inp"
fout = "ketqua.out"
DS, Diem = nhapDL(finp)
Kq = xuly(Diem)
ghiDL(fout, DS, Kq)
# Nhập dãy số từ bàn phím
lst = list(map(int, input("Nhập dãy số cách nhau bởi dấu cách: ").split()))
# Sắp xếp dãy số theo thuật toán sắp xếp chọn
for i in range(len(lst)):
min_idx = i
for j in range(i+1, len(lst)):
if lst[j] < lst[min_idx]:
min_idx = j
lst[i], lst[min_idx] = lst[min_idx], lst[i]
# In kết quả ra màn hình
print("Dãy số đã sắp xếp:", lst)
Tham khảo:
Giai đoạn 1. Liệt kê các việc lớn để nhận được các kết quả KQ1, KQ2 và KQ3 1. Đọc dữ liệu từ tập Tổ chức dữ liệu trong chương trình bằng các kiểu dữ liệu của Python sao cho thuận tiện để thực hiện các việc tiếp theo,
2. Phân tích dãy điểm từng học sinh để có KQI và KQ3; viết kết quả vào các tập “phantich_theoHS.txt", "xetKhenThuong tri
3. Với mỗi môn học, sắp xếp dãy điểm để có KQ2a, viết kết quả vào tệp “phantich_
theoMon.txt";
4. Với mỗi môn học, phân tích dãy điểm để có KQ2b; viết kết quả vào tệp "phantich
theoMon.txt".
Giai đoạn 2. Thiết kế các hàm
1. Đọc dữ liệu từ tập
Dữ liệu đầu vào chứa trong một tệp, dọc vào từng dòng và xử lí không phức tạp. Có thể viết một hàm thực hiện việc này. Đặt tên hàm: ví dụ là nhapTuTep.
Đầu vào: tập phần mềm bảng tính chứa dữ liệu như mô tả ở đầu bài học. Đầu ra: dữ liệu trong chương trình được tổ chức như sau:
- Mảng hai chiều các điểm số: Mảng nx m, mỗi hàng là dãy điểm của một học sinh, sẵn sàng để phân tích kết quả cho từng học sinh.
- Cột Tên trong bảng kết quả học tập tạo thành danh sách các tên học sinh để ghép với từng cột điểm số môn học, tách riêng được kết quả học tập theo từng môn.
– Hàng các tên môn học tạo thành danh sách tên môn học để dễ dàng lấy ra từng tên môn học theo chỉ số cột.
2. Phân tích điểm theo học sinh
Có thể tách thành các việc nhỏ, cụ thể hơn như sau:
2a) Phân tích dãy điểm số (là một hàng của mảng hai chiều) để có KQI: Thiết kế một hàm và đặt tên, ví dụ là ptDiem
Đầu vào: một dãy điểm số
Đầu ra: trả về sum, max, min, số lượng điểm thuộc các mức xếp hạng Tốt, Khá
Dat, Chura dat.
2b) Xét khen thưởng
Nếu chamDiem > 0 thì viết thêm (tên, chamDiem) thành một dòng vào tập “xetKhenThuong.txt"; có thể thực hiện việc này bằng một vài câu lệnh ngắn gọn, không cần viết thành một hàm riêng.
Lặp lại các việc 2a) và 2b) cho mỗi hàng trong mảng hai chiều axim sẽ hoàn thành phân tích điểm cho toàn bộ học sinh và lập xong danh sách học sinh được xét khen thưởng.
Có thể thiết kế thân vòng lặp thành một hàm và đặt tên, ví dụ là ptHocSinh.
Đầu vào: Một hàng trong mảng hai chiều axim (một dãy điểm số).
Dau ra
- Thêm một dòng vào tập “phantich theoHS.txt" (gọi hàm ptDiem) — Thêm (tên, chamliem) vào tập “xetKhenThuong.txt" nếu chamDiem ≥ 0, 3. Phân tích điểm theo môn học
3a) Chuẩn bị đầu vào để sẵn sàng phân tích điểm theo môn học:
Dãy điểm số một môn học là một cột của mảng hai chiều năm không sẵn có ngayn như một danh sách Phython. Cũng chưa có sẵn danh sách các cặp (tên, điểm) là kết quả của mỗi môn học (ở đây tên là tên học sinh).
Thiết kế một hàm, đặt tên ví dụ là tach Mom
- Đầu vào: dữ liệu trong chương trình (sau khi đọc từ tập vào)
- Đầu ra: trả về tên danh sách dãy điểm số một môn học và tên danh sách các cặp (tên, điểm) cho môn học đó.
3b) Phân tích điểm một môn học.
Nhận thấy rằng yêu cầu kết quả đầu ra KQI và KQ28 là tương tự như nhau. Hàm ptlhiem sử dụng được cho cả hai việc, phân tích điểm từng học sinh và phân tích điểm từng môn học.
3c) Sắp xếp danh sách các cặp (tên, điểm) theo thứ tự điểm giảm dần để có KQ2a.
Ta đã viết một số chương trinh thực hiện các thuật toán sắp xếp dãy số. Có thể cải biên để nhận được một hàm thực hiện sắp xếp danh sách các cặp (tên, điểm) theo thứ tự điểm giảm dần.
Lặp lại các việc 3h) và 30) cho mỗi cột trong mảng hai chiều a x m sẽ hoàn thành phân tích điểm cho toàn bộ các môn học. Có thể thiết kế một hàm nhận kết quả từ tach Mon và thực hiện 3b) và 3c) cho một môn học; đặt tên, ví dụ là ptMonHoc. - Đầu vào: danh sách điểm một môn học và danh sách các cặp (tên, điểm).
- Đầu ra:
+Thêm một dòng vào tập “phantich_theoMon.txt" (gọi hàm ptDiem). +Thêm danh sách các cặp (tên, điểm) theo thứ tự điểm giảm dần vào tập “phantich theoMon.txt" (gọi hàm sắp xếp đã cải biển).
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.