Tip:
Highlight text to annotate it
X
Thuật toán là gì?
Trong khoa học máy tính, thuật toán là tập hợp
các chỉ dẫn để giải toán từng bước.
Các thuật toán thường được máy tính xử lí,
nhưng con người chúng ta cũng có thể dùng chúng.
Ví dụ, làm sao đếm số người
có mặt ở trong phòng ?
Nếu là tôi,
tôi sẽ chỉ vào từng người một
đếm : 1, 2, 3, 4 và cứ thế.
Đó là một thuật toán.
Chính quy hơn hãy thử diễn đạt bằng phương trình,
dạng cú pháp giống Tiếng Anh nhưng là ngôn ngữ lập trình.
Lấy n = 0.
Với mỗi người trong phòng, lập n = n+1.
Điều đó nghĩa là gì ?
hàng 1 biểu thị
biến số n
được gán giá trị ban đầu bằng 0.
Nghĩa là chúng ta
bắt đầu thuật toán
bằng cách đếm từ 0.
Sau đó,
chưa đếm gì vội.
Quy ước gọi biến số này là n
Tôi có thể gọi nó bằng bất cứ tên gì.
Giờ hàng 2 là điểm bắt đầu của bảng mạch,
là một chuỗi các bước lặp lại.
Trong ví dụ này, các bước là
đếm những người trong phòng.
Dưới hàng 2 là hàng 3,
mô tả chính xác cách đếm.
Những nét cắt biểu thị rằng hàng thứ 3
sẽ được lặp lại.
Ngôn ngữ code nói rằng
sau khi bắt đầu bằng 0,
với mỗi người trong phòng
chúng ta sẽ cộng thêm 1 vào n.
Thuật toán này đã đúng chưa?
Hãy thử lại xem.
Liệu có áp dụng được trong trường hợp có 2 người trong phòng ?
Để xem. Ở hàng 1, biến n khởi điểm = 0
Với mỗi người trong phòng
ta lại cộng 1 vào n.
Vậy ở vòng đầu
ta đã nâng giá trị của n từ 0 lên 1,
ở vòng hai,
từ 1 lên 2.
Khi thuật toán kết thúc, n=2,
đúng bằng số người trong phòng.
Đến đây vẫn rất suôn sẻ.
Còn trường hợp này thì sao ?
Giả sử không có ai trong phòng,
ngoài tôi, người đang đếm ra.
Ở hàng 1, một lần nữa giá trị ban đầu của n = 0.
Lần này, không thể áp dụng hàng 3
vì không còn ai trong phòng
thành ra, n giữ nguyên bằng 0,
giá trị đúng bằng số người trong phòng.
Đơn giản nhỉ!
Nhưng đếm từng người một thì có vẻ không hiệu quả cho lắm!
Chắc chắn có thể làm tốt hơn!
Sao không thử đếm hai người 1 lúc?
Thay vì đếm 1,2,3,4,5,6,7,8 , v.v
hãy thử 2,4,6,8, v.v
Có vẻ nhanh hơn và chắc chắn là thế rồi!
Thử thể hiện bước cải tiến này bằng ngôn ngữ lập trình nhé!
Coi n = 0.
Mỗi cặp trong phòng
có giá trị n = n+2
Thay đổi này cũng đơn giản mà !
Thay vì đếm từng người một
ta đếm hai người một.
Thuật toán nhờ thế nhanh gấp đôi.
Nhưng nó có chính xác không? Để xem.
Nếu có 2 người trong phòng,
ở hàng 1, n có giá trị ban đầu bằng 0.
Có 1 cặp trong phòng nên cộng thêm 2 vào n.
Cuối cùng, khi thuật toán kết thúc, n = 2,
trùng với số người trong phòng.
Giả sử không có ai trong phòng.
Ở hàng 1, giá trị ban đầu n = 0.
Cũng như lần trước, không áp dụng được
cho hàng 3 vì không có cặp nào trong phòng
n giữ nguyên bằng 0
đúng bằng số người trong phòng.
Nhưng nếu có 3 người trong phòng
thuật toán này sẽ thực hiện thế nào?
Để xem!
Ở hàng 1, giá trị đầu của n bằng 0.
cứ hai người một
ta cộng thêm 2 vào n
rồi sao nữa?
Không có đủ một cặp nữa trong phòng
nên hàng 2 không áp dụng được.
kết thúc thuật toán,
n = 2, và kết quả này không đúng.
Thuật toán này
mắc một sai lầm.
Hãy xem lại một lần nữa!
Coi n = 0.
Với mỗi đôi trong phòng,
lập n = n+2.
Nếu 1 người lẻ ra,
lập n = n+1.
Để giải quyết vấn đề này,
chúng ta đưa một điều kiện vào hàng 4
gọi là một nhánh,
chỉ áp dụng nếu có một người lẻ ra
Giờ thì, nếu có 1 hay 3
hay bất kì số người lẻ nào trong phòng,
thuật toán này vẫn hoạt động được.
Ta có thể làm tốt hơn không?
Ờ thì, ta có thể đếm 3, 4, 5 hay 10 người một lúc,
nhưng quá nữa thì sẽ
hơi khó đếm.
Cuối cùng,
dù là vận hành bởi máy móc hay con người,
thuật toán cũng là tập hợp những chỉ dẫn
để giải các bài toán.
Đây chỉ mới có ba bài toán thôi,
bạn sẽ dùng thuật toán để giải những bài nào ?