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");

Theo em, đây là kết quả lập trình theo phương pháp mô đun hoá.

Vì bài toán được viết theo các bước từ việc lớn, thiết kế các hàm, viết các hàm, tiến hành viết chương trình.

#include <bits/stdc++.h>

using namespace std;

long long a[1000],n,i,dem;

int main()

{

cin>>n;

dem=0;

for (i=1; i<=n; i++)

{

cin>>x;

if ((i%2==1) and (x%2==0)) dem++;

}

cout<<dem;

return 0;

}

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

Đọc mã lệnh của thuật toán Eratosthenes cho ở Hình 5 và mô tả liệt kê các bước của thuật toán và bằng mã giả:

Đục bỏ dần các số không nguyên tố bằng cách đánh dấu “là hợp số” (không phải số nguyên tố) mỗi khi biết số đó là bội số của một số nguyên tố.

*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

Tham khảo:

1) Đoán trước kết quả và chạy chương trình để kiểm tra.

In ra 8. 0

2) Xem kết quả và cho biết có sự tương tự giữa mảng với danh sách hay khô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.

A