BÀI 4: BÀI TOÁN VÀ THUẬT TOÁN (tiết 3)

​

​

Ví dụ về thuật toán

THUẬT TOÁN TÌM MAX

3

Người ta đặt 5 quả bóng có kích thước khác nhau trong hộp đã được đậy nắp như hình bên. Chỉ dùng tay hãy tìm ra quả bóng có kích thước lớn nhất .

​

Qu¶ nµy lín nhÊt

Qu¶ nµy míi lín nhÊt

å! Qu¶ nµy lín h¬n

T×m ra qu¶ lín nhÊt råi!

Cïng t×m thuËt to¸n

Ví dụ 1: Cho số nguyên dương N và dãy số nguyên a₁, a₂, …, a_N. Tìm giá trị lớn nhất của dãy số đó

Xác định bài toán:

Input: Số nguyên dương N và dãy N số nguyên a₁, a₂, …, a_N. _�Output: Số lớn nhất (Max) của dãy số.

​

Ý tưởng:� - Đặt giá trị Max = a₁._� - Lần lượt cho i chạy từ 2 đến N, so sánh� giá trị a_i với giá trị Max, nếu a_i > Max thì� Max nhận giá trị mới là a_i.

Cách 1: Liệt kê các bước

B1: Nhập N và dãy a₁,…, a_N;

B2: Max ← a₁; i ← 2;

B3: Nếu i > N thì đưa ra giá trị Max rồi kết thúc;

B4:� Bước 4.1: Nếu a_i > Max thì Max ← a_i;� Bước 4.2: i ← i+1 rồi quay lại B3.

Đ

​

S

Đ

​

S

B1: Nhập N và dãy a₁,…,a_N;

B2: Max ← a₁; i ← 2;

B3: Nếu i > N thì đưa ra giá trị � Max rồi kết thúc;

B4 :� 4.1: Nếu a_i > Max thì Max ← a_i;

4.2: i ← i + 1 rồi quay lại B3.

Cách 2: Sơ đồ khối

Tính chất của thuật toán:

-Tính dừng: Thuật toán phải kết thúc sau một số hữu hạn lần thực hiện các thao tác;.

-Tính xác định: Sau khi thực hiện một thao tác thì hoặc là thuật toán kết thúc hoặc là có đúng một thao tác xác định để được thực hiện tiếp theo;

-Tính đúng đắn: Sau khi thuật toán kết thúc, ta nhận được Output cần tìm.