Xét dự án nhỏ về lập trình để thực nghiệm so sánh thời gian thực tế chạy chương trình máy tính thực hiện một số thuật toán sắp xếp mà em đã biết theo cách bấm giờ chạy máy với các dãy số đầu vào ngẫu...

ML

Minh Lệ

18 tháng 7 2023

Xét dự án nhỏ về lập trình để thực nghiệm so sánh thời gian thực tế chạy chương trình máy tính thực hiện một số thuật toán sắp xếp mà em đã biết theo cách bấm giờ chạy máy với các dãy số đầu vào ngẫu nhiên rồi lấy giá trị trung bình. Em hãy áp dụng phương pháp lập trình mô đun hoá:a) Đưa ra thiết kế các hàm sẽ được sử dụng trong chương trình.b) Viết các câu lệnh trong chương trình chính (không cần...

Đọc tiếp

#Tin học lớp 11

1

TA

Thanh An

22 tháng 8 2023

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.

Đúng(0)

ML

Minh Lệ

17 tháng 7 2023

Viết ba chương trình mô phỏng các thuật toán sắp xếp chèn, sắp xếp chọn và sắp xếp nổi bọt mà em đã biết. Cho biết thời gian thực tế thực hiện các chương trình trên với bộ dữ liệu đầu vào là dãy A = [3, 1, 0, 10, 13, 16, 9,7, 5, 11]

#Tin học lớp 11

1

QT

Quoc Tran Anh Le

Giáo viên

23 tháng 8 2023

*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

Đúng(0)

ML

Minh Lệ

17 tháng 7 2023

Viết chương trình nhập một dãy số từ bàn phím, các số cách nhau bởi dấu cách, thực hiện sắp xếp dãy đã nhập theo một trong các thuật toán sắp xếp rồi in kết quả ra màn hình.

#Tin học lớp 11

1

QT

Quoc Tran Anh Le

Giáo viên

23 tháng 8 2023

# 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)

Đúng(0)

VD

Vương Duy Quang

8 tháng 5 2022

Câu 15: Chương trình máy tính là:A. Chương trình trên ti vi về máy tính.B. Một bản hướng dẫn con người sử dụng biết thực hiện công việc nào đó.C. Một tập hợp các lệnh viết bằng ngôn ngữ lập trình, thể hiện theo các bước của thuật toán để máy tính "hiểu" và thực hiện.D. Hình vẽ sơ đồ khối thuật toán để cho máy tính biết cách giải quyết một công...

Đọc tiếp

#Tin học lớp 6

3

L

lynn?

8 tháng 5 2022

C

Đúng(1)

KN

ka nekk

8 tháng 5 2022

c

Đúng(1)

ML

Minh Lệ

25 tháng 7 2023

Chọn các phương án đúng:A. Em có thể dùng ngôn ngữ lập trình Scratch để diễn tả từng bước thực hiện một trò chơi trên máy tínhB. Các câu lệnh của Scratch được sắp xếp theo một thứ tự nhất định tạo thành một chương trình máy tínhC. Máy tính không thể thực hiện trò chơiD.Trong Scratch các lệnh của chương trình máy tính có thể được thể hiện bằng ngôn ngữ tiếng...

Đọc tiếp

#Tin học lớp 4

1

MT

Mai Trung Hải Phong

25 tháng 7 2023

A-B-D

Đúng(2)

ML

Minh Lệ

17 tháng 7 2023

Em hãy thiết lập chương trình và tính thời gian chạy thực tế trên máy tính của các chương trình 1 và 2 ở Hình 24.2 với các giá trị n khác nhau từ đó thấy được ý nghĩa sự khác biệt độ phức tạp thời gian của hai chương trình...

Đọc tiếp

#Tin học lớp 11

1

QT

Quoc Tran Anh Le

Giáo viên

23 tháng 8 2023

*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(n²).

Đúng(0)

ML

Minh Lệ

17 tháng 7 2023

Trong các bài trước em đã học cách thiết kế thuật toán cho một số bài toán như bài toán tìm kiếm, bài toán sắp xếp và thiết lập chương trình thực hiện thuật toán đó. Một bài toán có nhiều thuật toán khác nhau và do đó có thể có nhiều chương trình khác nhau cùng giải quyết một bài toán. Hãy thảo luận và trả lời các câu hỏi sau:Làm thế nào để biết trong các thuật toán giải cùng một bài toán thì thuật toán nào là tốt...

Đọc tiếp

#Tin học lớp 11

2

TA

Thanh An

18 tháng 7 2023

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.

Đúng(0)

NC

Nguyễn Chí Quân

2 tháng 3

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.

Đúng(0)

NC

Nguyễn Cảnh Hùng

21 tháng 1 2018

Để giải bài toán trên máy tính, người ta thực hiện thực hiện các công việc saua). Lựa chọn hoặc thiết kế thuật toánb) Xác định bài toán c) Viết tài liệud) Viết chương trình e) Hiệu chỉnhHy chọn cách sắp xếp đúng nhất về thứ tự thực hiện các công việc nêu trên A. b →a →d →c →e B. b →a →d →e →c C. a →b →d →e D. d →a →b →e...

Đọc tiếp