Bài toán

Một dãy ngoặc hợp lệ được định nghĩa theo kiểu đệ quy như sau:

• Dãy rỗng - dãy không gồm ký tự nào - là dãy ngoặc đúng.
• Nếu X là một dãy ngoặc đúng, thì (X) cũng là một dãy ngoặc đúng. Ví dụ, vì X = ()() là một dãy ngoặc đúng nên (()()) cũng là một dãy ngoặc đúng.
• Nếu X và Y là hai dãy ngoặc đúng, thì XY là một dãy ngoặc đúng. Ví dụ, vì X = (()) và Y = () là các dãy ngoặc đúng, nên XY = (())() cũng là dãy ngoặc đúng.

Một số ví dụ về các dãy không phải là dãy ngoặc đúng: )(, (())), ((()...

Yêu cầu bài toán: Cho cho một dãy ngoặc, yêu cầu kiểm tra dãy ngoặc có hợp lệ hay không?

Gợi ý

Xét điều kiện đúng của dãy, ta nhận thấy dãy sẽ sai khi:

• Dãy có độ dài là số lẻ.
• Dãy có dấu ngoặc đầu tiên là dấu ngoặc mở.
• Dãy có số ngoặc đóng và mở không tạo thành 1 bộ ngoặc đúng gần nhất (), [], {}.

Vậy chỉ cần duyệt qua các phần tử, phần tử thỏa điều kiện sẽ đưa vào STACK, nếu xuất hiện một ngoặc đóng sẽ so sánh với TOP của STACK, nếu không tạo thành ngoặc đúng thì ngừng lại, ngược lại tiếp tục đến khi duyệt hết dãy.

Cuối cùng kiểm tra STACK, nếu rỗng chứng tỏ các cặp ngoặc đã tạo thành bộ => Dãy ngoặc đúng; Xuất kết quả "yes"!

Bài toán cổ:

Trăm trâu, trăm cỏ
Trâu đứng ăn năm,
Trâu nằm ăn ba,
Lụ khụ trâu già,
Ba con một bó.

Hỏi có bao nhiêu trâu đứng, trâu nằm, trâu già?

Phân tích

• Trâu đứng ăn 5 bó cỏ, có tổng cộng 100 bó cỏ => có tối đa 20 trâu đứng (100/5).
• Tương tự với trâu nằm => có tối đa 33 trâu nằm (100/3).
• 3 trâu già ăn 1 bó cỏ => số trâu già phải chia hết cho 3 => có tối đa 99 trâu già.

Gợi ý

• Với bài toán này, không thể xác định số lần lặp, không thể dùng repeat.
• Sử dụng "while lồng while" khiến bài toán khó hiểu.

Kết luận

Sử dụng "for lồng for", kiểm tra điều kiện bằng if

Cú pháp

if <điều kiện> [lệnh_1 lệnh_2 ...]

Giải thích

Khi điều kiện có kết quả đúng các lệnh sẽ được thực hiện.

Ví dụ

In ra màn hình số lớn hơn

to sosanh :a :b

if :a > :b [label :a]

if :b > :a [label :b]

end

Cú pháp

for [biến_chạy giá_trị_đầu giá_tri_cuối giá_trị_tăng] [lệnh_1 lệnh_2 ...]

Giải thích

biến_chạy ban đầu sẽ được gán giá_trị_đầu, mỗi lần lặp biến_chạy sẽ cộng thêm giá_trị_tăng cho đến khi biến_chạy = giá_trị_cuối, ở mỗi lần lặp lệnh FOR sẽ xử lý nhóm lệnh bên trong [].

Ví dụ

In ra màn hình từ 1 đến 10

to in110

for[i 1 10 1][label :i]

end