Học xong bài này, em sẽ:
• Biết được cấu trúc rẽ nhánh trong thực tế là gì và khi nào trong thuật toán có cấu trúc rẽ nhánh.
• Thực hiện được cấu trúc rẽ nhánh.
1. Lựa chọn hành động tuỳ thuộc vào điều kiện
Trong cuộc sống có những lúc chúng ta lựa chọn hành động tùy thuộc vào điều kiện cụ thể ví dụ tuần này một nhóm bạn lớp 6 hạng chơi cùng nhau sau 3 tiết học của chiều thứ Năm như sau:
1) 16 giờ có mặt ở cửa phòng học lớp 6A.
2) Nếu trời mưa: chơi cờ vua trong phòng học lớp 6A.
3) Nếu trời không mưa: chơi đá bóng ở sân trường.
Trong mô tả trên có hai dòng bắt đầu là từ "Nếu". Điều đó nghĩa là có hai trường hợp khác nhau cần xem xét. Khi thực hiện quy trình trên sẽ xảy ra chỉ một trong hai trường hợp. Ta nói trong thuật toán có rẽ nhánh, giống như đến ngã ba đường, cần phải chọn rẽ phải hay rẽ trái.
Khi phải dựa trên điều kiện cụ thể nào đó để xác định bước thực hiện tiếp theo trong quá trình thực hiện thuật toán thì cần cấu trúc rẽ nhánh.
2. Thể hiện cấu trúc rẽ nhánh
Quy trình trong ví dụ trên được mô tả theo cách liệt kê tuần tự các bước và hoàn toàn rõ ràng để thực hiện. Ở đó, mỗi trường hợp (mỗi nhánh) chỉ nêu một việc phải làm, cấu trúc rẽ nhánh có hai nhánh đều rất ngắn. Tuy nhiên, còn có những thuật toán chứa cấu trúc rẽ nhánh mà có nhánh gồm nhiều việc. Do vậy, muốn tránh nhầm lẫn, khi thể hiện cấu trúc rẽ nhánh cần làm rõ danh sách các việc trong một nhánh kết thúc ở đâu.
Để thể hiện cấu trúc rẽ nhánh, cần nhận biết những thành phần sau:
- Điều kiện rẽ nhánh là gì?
- Các bước tiếp theo khi điều kiện được thoả mãn, ta gọi ngắn gọn đó là nhánh đúng.
- Các bước tiếp theo khi điều kiện không thoả mãn, ta gọi ngắn gọn đó là nhánh sai.
Ta quy ước sử dụng cặp từ khóa "Nếu - Trái lại" để thể hiện cấu trúc rẽ nhánh theo mẫu ở Hình 1a. Ví dụ minh họa mẫu này cho Hình 1b.
|
Mẫu thể hiện cấu trúc rẽ nhánh Nếu <điều kiện>: nhánh đúng Trái lại: nhánh sai Hết nhánh Hình 1a. Mẫu cấu trúc rẽ nhánh |
Một ví dụ thể hiện Nếu trời mưa: Chơi cờ vua trong lớp Trái lại: Chơi bóng đá ở sân trường Hết nhánh Hình 1b. Một ví dụ thể hiện cấu trúc rẽ nhánh |
Cấu trúc rẽ nhánh kết thúc ngay sau khi gặp “Hết nhánh”. Ta trở lại với quy ước thực hiện tuần tự các bước. Chú ý rằng từ khóa "Trái lại" vừa đánh dấu hết nhánh đúng vừa bắt đầu cho nhánh sai. Nhưng ta cần dùng từ khóa "Hết nhánh" để kết thúc nhánh sai.
Nếu nhánh sai là trống rỗng (nghĩa là không cần làm gì cả) thì cấu trúc rẽ nhánh khuyết từ khóa "Trái lại". Vì thế, trường hợp này được gọi là cấu trúc rẽ nhánh khuyết và cần dùng từ khóa "Hết nhánh" để kết thúc nhánh đúng (Hình 3a). Một ví dụ về cấu trúc rẽ nhánh khuyết là tình huống máy tính hỏi "Tiếp tục" hay "Bỏ qua". Nhấn nút "Bỏ qua" tức là nhánh sau từ khóa "Trái lại" không làm gì cả.
Hình 2. Sơ đồ mô tả rẽ nhánh ở Hình 1b
|
Mẫu thể hiện cấu trúc rẽ nhánh Nếu <điều kiện>: nhánh đúng Hết nhánh Hình 3a. Mẫu cấu trúc rẽ nhánh dạng khuyết |
Một số ví dụ thể hiện Nếu trời mưa: Lấy áo mưa ra mặc vào Hết nhánh Hình 3b. Mẫu ví dụ thể hiện cấu trúc rẽ nhánh dạng khuyết |
Hoạt động
| Có thể dùng sơ đồ ở Hình 2 để mô tả cấu trúc rẽ nhánh ở Hình 1b. Nếu dùng sơ đồ mô tả cấu trúc rẽ nhánh khuyết ở Hình 3b, em sẽ vẽ sơ đồ đó như thế nào? |
3. Biểu thức điều kiện trong cấu trúc rẽ nhánh
Thao tác kiểm tra điều kiện phải cho kết quả là thoả mãn hoặc không thoả mãn, hay nói theo kiểu logic là “đúng” hoặc “sai” như cách ta đặt tên nhánh ở trên. Điều kiện cần kiểm tra trong cấu trúc rẽ nhánh thường là một biểu thức so sánh
Ví dụ: (a + b) > 5 là biểu biểu thức so sánh giá trị (a + b) với 5. Chẳng hạn với a = 1 và b = 2 thì kết quả so sánh cho giá trị là sai, Còn nếu a = 3 và b = 4 thì kết quả so sánh cho giá trị là đúng.
Luyện tập
Bài 1. Quy trình tính số tiền được giảm trừ cho khách hàng mua sách truyện thiếu niên ở hiệu sách Người Máy:
1) Tính Tổng số tiền sách (khi chưa tính giảm giá), gọi số đó là Tổng số tiền sách.
2) Nếu Tổng số tiền sách >= 500.000 đồng: số tiền được giảm là 10% của Tổng số tiền sách.
3) Nếu Tổng số tiền sách < 500.000 đồng: số tiền được giảm là 5% của Tổng số tiền sách.
Sử dụng mẫu thể hiện cấu trúc rẽ nhánh, em hãy viết lại (hoặc vẽ sơ đồ) mô tả quy trình tính số tiền được giảm cho khách hàng mua sách nêu ở trên.
Bài 2. Trong các phát biểu sau về biểu thức điều kiện ở cấu trúc rẽ nhánh, phát biểu nào đúng, phát biểu nào sai? Vì sao?
1) Phải là một biểu thức so sánh giá trị bằng.
2) Phải là một biểu thức so sánh giá trị lớn hơn, nhỏ hơn.
3) Khi kiểm tra phải cho kết quả là "đúng" hoặc "sai".
Vận dụng
Em hãy sử dụng mẫu thể hiện cấu trúc rẽ nhánh để mô tả thuật toán giải bài toán: Cho ba đồng xu trong đó có một đồng xu giả nhẹ hơn. Dùng cân thăng bằng để tìm đồng xu giả.
Câu hỏi tự kiểm tra
Trong các phát biểu sau về thuật toán, phát biểu nào đúng?
1) Dùng cấu trúc rẽ nhánh nếu có quá nhiều việc cần làm.
2) Dùng cấu trúc rẽ nhánh khi có các trường hợp khác nhau cần xem xét, trường hợp khác nhau thì thực hiện việc khác nhau.
3) Để thể hiện cấu trúc rẽ nhánh cần dùng mẫu "Nếu ... Trái lại ...".
4) Cấu trúc rẽ nhánh luôn kết thúc với dấu hiệu "Hết nhánh".
TÓM TẮT BÀI HỌC* Khi nào mô tả thuật toán phải dùng từ "Nếu", thì ta có cấu trúc rẽ nhánh. Dùng mẫu "Nếu ... Trái lại ..." để thể hiện cấu trúc rẽ nhánh. * Cần đánh dấu "Hết nhánh" để trở lại với quy ước thực hiện các bước tương tự theo liệt kê. |
