BÀI 5. ĐÁNH GIÁ THUẬT TOÁN

PHẦN I. HỆ THỐNG CÂU HỎI, BÀI TẬP TRONG SGK

KHỞI ĐỘNG

Theo em, một thuật toán như thế nào thì được xem là chạy nhanh/chạy chậm?

LUYỆN TẬP

Em hãy cho ví dụ một lời gọi hàm được tính là phép toán sơ cấp và một lời gọi hàm không được tính là phép toán sơ cấp.

VẬN DỤNG

Vận dụng 1: Xét bài toán sắp xếp dãy số. Hãy cho biết khi nào ta có trường hợp thuận lợi nhất, số phép toán cần làm là ít nhất?

Vận dụng 2: Ước lượng số phép toán sơ cấp cần thực hiện để tìm số lớn nhất trong dãy số:

a) Đầu vào là dãy ngẫu nhiên.

b) Đầu vào là dãy giảm dần.

TỰ KIỂM TRA

Tự kiểm tra 1: Tại sao không thể đánh giá thuật toán qua chương trình cài đặt thuật toán?

Tự kiểm tra 2: Khi nào thì áp dụng quy tắc lấy max?

Tự kiểm tra 3: Quy tắc nhân áp dụng cho cấu trúc vòng lặp là gì?

PHẦN II. 5 PHÚT TRẢ LỜI CÂU HỎI, BÀI TẬP SGK

KHỞI ĐỘNG

Đáp án KD: 

Thuật toán hiệu quả hơn nếu thời gian thực hiện chương trình và lượng bộ nhớ máy tính cần dùng ít hơn.

LUYỆN TẬP

Đáp án LT: 

int number = 1990;

if ((number % 2) == 0)

   Console.WriteLine($"{number} là số chẵn");

// In ra: 1990 là số chẵn

int a = 5;

int b = 10;

if (a >= b)

{

   Console.WriteLine("Số a lớn hơn hoặc bằng số b");

}

else

{

   Console.WriteLine("Số a nhỏ hơn số b");

}

//In ra: Số a nhỏ hơn số b

Sau else bạn có thể bắt đầu ngay một lệnh if khác để tạo ra cấu trúc if else, kiểm tra nhiều trường hợp

int a = 10;

int b = 10;

if (a > b)

{

   Console.WriteLine("Số a lớn hơn hoặc bằng số b");

}

else if (a < b)

{

   Console.WriteLine("Số a nhỏ hơn số b");

}

else

{

   Console.WriteLine("Hai số a, b bằng nhau");

}

VẬN DỤNG

Đáp án VD1:

Trường hợp thuận lợi nhất là khi dãy đã có thứ tự tăng dần hoặc giảm dần. 

Đáp án VD2:

Ước lượng số phép toán sơ cấp cần thực hiện

TỰ KIỂM TRA

Đáp án TKT1:

Vì việc đánh giá thuật toán yêu cầu xem xét các khía cạnh khác nhau của thuật toán, chứ không chỉ là chương trình cài đặt của nó. 

Đáp án TKT2:

Khi tìm giá trị lớn nhất trong một danh sách hoặc một tập hợp. 

Đáp án TKT3:

Quy tắc nhân áp dụng cho cấu trúc vòng lặp for và while trong Python.