Đang tải trang
Lý thuyết
Nhắc lại thật nhanh
Ở Bài 6, thuật toán là dãy bước rõ ràng, có thứ tự, có điểm kết thúc. Nhưng có những việc phải làm đi làm lại nhiều lần. Viết ra từng lần thì quá dài. Bài này học cách viết gọn: vòng lặp.
1. Bài toán viên gạch của ông Tư
Khoảng hiên dài 48 ô, rộng 18 ô. Ông muốn lát gạch vuông, tất cả cùng một cỡ, to nhất có thể, và không phải cắt viên nào.
Minh thử từng cỡ:
| Cạnh viên gạch | Chiều dài 48 | Chiều rộng 18 | Lát được không? |
|---|---|---|---|
| 4 ô | 48 = 4 × 12, vừa | 18 = 4 × 4 + 2, thừa 2 | Không |
| 9 ô | 48 = 9 × 5 + 3, thừa 3 | 18 = 9 × 2, vừa | Không |
| 5 ô | thừa 3 | thừa 3 | Không |
Thử như vậy thì rất lâu, và không biết khi nào mới gặp cỡ đúng. Cần một cách chắc chắn.
2. Cách của Euclid: cắt hình vuông, rồi làm lại
Khoảng 300 năm trước Công nguyên, ở Alexandria, Euclid viết ra cách sau:
Văn bản
Lặp lại:
Cắt hình vuông lớn nhất khỏi hình chữ nhật.
Dừng khi: không còn phần dư.
Cạnh của hình vuông cuối cùng là đáp án.
Làm với hiên 48 × 18:
| Lượt | Hình chữ nhật đang có | Cắt ra | Phần dư |
|---|---|---|---|
| 1 | 48 × 18 | 2 hình vuông cạnh 18 | 12 × 18 |
| 2 | 12 × 18 | 1 hình vuông cạnh 12 | 12 × 6 |
| 3 | 12 × 6 | 2 hình vuông cạnh 6 | Không còn |
Hình vuông cuối cùng có cạnh 6 ô. Kiểm tra: 48 = 6 × 8 và 18 = 6 × 3, nên cần 8 × 3 = 24 viên, không cắt viên nào.
Lên lớp 6, bạn sẽ gặp lại bài này dưới tên ước chung lớn nhất: số lớn nhất mà cả 48 và 18 đều chia hết. Ước chung lớn nhất của 48 và 18 là 6.
3. Theo dõi vòng lặp bằng bảng
Viết bằng số, mỗi lượt cắt một hình vuông chính là lấy số lớn trừ đi số nhỏ. Ta theo dõi bằng một bảng theo dõi, mỗi dòng là một lần lặp:
| Lần lặp | Số lớn | Số nhỏ | Số lớn − số nhỏ |
|---|---|---|---|
| 1 | 48 | 18 | 30 |
| 2 | 30 | 18 | 12 |
| 3 | 18 | 12 | 6 |
| 4 | 12 | 6 | 6 |
| 5 | 6 | 6 | 0 |
Khi hiệu bằng 0 thì dừng. Đáp án là 6. Lập bảng theo dõi là cách các lập trình viên kiểm tra một vòng lặp chạy có đúng không.
4. Cách nhanh hơn: phép chia lấy dư
Trừ 18 hai lần liền khỏi 48 cũng chính là chia 48 cho 18, lấy số dư. Cách viết hiện đại của thuật toán Euclid dùng phép chia lấy dư nên ít lượt hơn:
| Lượt | Phép chia | Số dư |
|---|---|---|
| 1 | 48 = 2 × 18 + 12 | 12 |
| 2 | 18 = 1 × 12 + 6 | 6 |
| 3 | 12 = 2 × 6 + 0 | 0 |
Số dư bằng 0 thì dừng. Số chia ở lượt cuối là 6. Đây đúng là ba lượt cắt hình vuông trong video.
5. Vòng lặp và điều kiện dừng
Một nhóm bước được làm đi làm lại gọi là vòng lặp. Mỗi vòng lặp cần một điều kiện dừng cho biết khi nào thì thôi. Có hai kiểu hay gặp:
| Kiểu vòng lặp | Điều kiện dừng | Ví dụ |
|---|---|---|
| Lặp đủ số lần | Đã làm đủ N lần | Chép phạt 5 lần một câu |
| Lặp cho đến khi | Một điều kiện trở thành đúng | Euclid: cho đến khi không còn dư |
Có khi người ta kết hợp cả hai: "Thử kết nối Wi‑Fi lại, cho đến khi kết nối được hoặc đã thử 5 lần". Nhờ vế "đã thử 5 lần", điện thoại không bị kẹt mãi nếu Wi‑Fi hỏng.
Ví dụ theo dõi một vòng lặp:
Văn bản
Bắt đầu với số 1.
Lặp lại: nhân đôi số.
Dừng khi: số lớn hơn 50.
| Lần lặp | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| Số sau khi nhân đôi | 2 | 4 | 8 | 16 | 32 | 64 |
Sau lần thứ 6, số là 64, lớn hơn 50, nên dừng.
6. Vì sao thuật toán Euclid chắc chắn dừng?
Mỗi lượt, phần dư luôn nhỏ hơn hình chữ nhật trước đó, mà độ dài thì là số nguyên dương. Một số nguyên dương không thể nhỏ đi mãi mãi: cùng lắm sau một số lượt nó phải về 0. Vì vậy thuật toán Euclid luôn dừng, với bất kỳ hai số nào.
Khi viết một vòng lặp, hãy luôn tự hỏi: mỗi lần lặp, có thứ gì đang tiến dần tới điều kiện dừng không?
7. Vòng lặp vô hạn
Thiếu điều kiện dừng, hoặc điều kiện dừng không bao giờ đúng, thì vòng lặp chạy mãi. Đó là vòng lặp vô hạn.
| Vòng lặp | Vì sao vô hạn? |
|---|---|
| "Gội, xả, lặp lại." | Không có điều kiện dừng |
| Bắt đầu từ 10, lặp lại cộng thêm 2, dừng khi số bằng 15 | Số đi 10, 12, 14, 16… không bao giờ bằng 15 |
| Bắt đầu từ 5, lặp lại cộng thêm 0, dừng khi số lớn hơn 9 | Số đứng yên ở 5, không tiến tới điều kiện dừng |
Sửa chai dầu gội: "Gội, xả, lặp lại cho đến khi tóc sạch". Sửa ví dụ thứ hai: dừng khi số lớn hơn hoặc bằng 15.
Một chương trình máy tính bị vòng lặp vô hạn thì bị treo: màn hình đứng yên, bấm gì cũng không phản ứng.
Ghi nhớ
- Vòng lặp: một nhóm bước được làm đi làm lại.
- Điều kiện dừng: cho biết khi nào thì thôi. Có kiểu lặp đủ số lần và kiểu lặp cho đến khi.
- Thuật toán Euclid: cắt hình vuông lớn nhất (hay trừ số lớn cho số nhỏ, hoặc chia lấy dư), lặp đến khi không còn dư. Kết quả là ước chung lớn nhất: của 48 và 18 là 6.
- Thuật toán Euclid luôn dừng vì phần dư nhỏ dần.
- Thiếu điều kiện dừng hoặc điều kiện không bao giờ đúng thì có vòng lặp vô hạn, máy bị treo.