Bài 22. Nghĩ trước khi gõ: xác định bài toán và mô tả thuật toán
Bài này dừng lại ở khâu trước khi gõ dòng mã đầu tiên: đọc đề để tách cho rõ Đầu vào và Đầu ra, mô tả cách giải thành một thuật toán gồm các bước rõ ràng, biết đọc và vẽ sơ đồ khối, mô phỏng bằng bảng giá trị rồi mới dịch sang Python.
- Cánh DiềuTin học 10 - Chủ đề F · Bài 17. Thực hành lập trình giải bài toán trên máy tínhtr. 117
- Cánh DiềuTin học 10 - Chủ đề F · Bài 18. Lập trình giải quyết bài toán trên máy tínhtr. 119
- Kết nối tri thứcTin học 10 - Bài 31. Thực hành viết chương trình đơn giảntr. 149–152
Bắt đầu bằng một hình dung
Chiều thứ Bảy, Minh hẹn Khoa - cậu bạn mới chuyển đến lớp - sang nhà mình học nhóm. Minh nhắn vội một tin: "Từ cổng trường cậu cứ đi một đoạn rồi rẽ ở chỗ có cây to, đi thêm tí nữa là tới nhà mình." Khoa đọc xong thấy cũng có vẻ dễ hiểu, liền xách xe đi ngay.
Bốn mươi phút sau, Khoa gọi điện. Cậu đang đứng ở một ngã tư hoàn toàn xa lạ, phía trước có tới ba cái cây mà cây nào cũng to. "Một đoạn" là bao xa? Rẽ trái hay rẽ phải? "Thêm tí nữa" là thêm bao nhiêu? Mỗi câu trong tin nhắn đều có thể hiểu theo dăm bảy kiểu khác nhau, và Khoa đã hiểu theo kiểu sai.
Minh nhắn lại lần thứ hai, lần này ghi hẳn ra từng việc: ra khỏi cổng trường thì rẽ phải; đi thẳng khoảng ba trăm mét tới ngã tư có hiệu thuốc; rẽ trái vào con đường có hàng bàng; đi qua đúng ba con hẻm rồi dừng; nhà mình là căn số 27, cổng sơn màu xanh. Mười phút sau Khoa bấm chuông.
Hai tin nhắn khác nhau ở chỗ nào? Ở bản thứ hai, mỗi việc chỉ có duy nhất một cách hiểu, số việc phải làm đếm được rõ ràng, và làm hết chừng ấy việc thì chắc chắn tới đúng nhà. Bảo một chiếc máy tính làm việc gì cũng đúng như vậy: nó không đoán được ý ta, nên trước khi bắt tay gõ lệnh, ta phải tự trả lời cho xong ba câu - mình đang có sẵn cái gì, mình cần tìm ra cái gì, và đi từ cái đã có tới cái cần tìm bằng những bước nào.
Nội dung bài học
- 1) Xác định bài toán: đâu là Đầu vào, đâu là Đầu ra?
- 2) Thuật toán và ba tính chất bắt buộc
- 3) Mô tả thuật toán: liệt kê các bước hay vẽ sơ đồ khối
- 4) Mô phỏng bằng bảng giá trị rồi chuyển thành chương trình
Tóm tắt lý thuyết cần nhớ
- Trước khi gõ dòng lệnh nào, hãy xác định bài toán: viết rõ Đầu vào (dữ liệu đã cho) và Đầu ra (kết quả đề yêu cầu), cẩn thận đừng nhầm dữ liệu trung gian với Đầu ra.
- Thuật toán là dãy hữu hạn các bước rõ ràng đưa Đầu vào tới Đầu ra, bắt buộc có ba tính chất: tính xác định, tính hữu hạn và tính đúng đắn.
- Thuật toán được mô tả bằng cách liệt kê các bước hoặc vẽ sơ đồ khối (ôvan bắt đầu/kết thúc, hình bình hành nhập/xuất, hình chữ nhật xử lí, hình thoi rẽ nhánh với hai nhánh Đúng/Sai); mọi thuật toán đều lắp từ ba cấu trúc tuần tự, rẽ nhánh, lặp.
- Muốn biết một sơ đồ khối cho kết quả gì, hãy mô phỏng bằng bảng giá trị qua từng vòng; khi chuyển sang Python thì khối nhập thành
input(), khối xử lí thành lệnh gán, hình thoi thànhif, mũi tên quay ngược thànhforhoặcwhile.
Thuật ngữ tiếng Anh trong bài
| Tiếng Anh | Đọc là | Nghĩa |
|---|---|---|
| algorithm | AL-gô-rít-thầm | thuật toán Các bước làm một việc theo đúng thứ tự để ra kết quả - như công thức pha mì gói: đổ nước sôi, chờ 3 phút, rồi ăn. |
| function | PHẮNG-sần | hàm Một 'cỗ máy nhỏ' lắp sẵn để làm một việc cụ thể. |
| debug | đi-BẤC | gỡ lỗi Đi tìm con bọ (lỗi) đang trốn trong chương trình rồi sửa cho code chạy đúng - như tìm chỗ sai trong bài toán rồi sửa lại. |
Câu hỏi trắc nghiệm có đáp án
Mấy câu mẫu để bạn tự kiểm tra ngay. Trong ứng dụng, bài này có đủ 24 câu, chấm điểm tự động và giải thích từng câu sai.
- Số lượng phần tử n của dãy
- Toàn bộ n số của dãy sau khi đã sắp xếp tăng dần
- Một số - giá trị lớn nhất trong dãy
- Biến dùng để lưu số lớn nhất tạm thời trong lúc duyệt dãy
- Một điều kiện cần kiểm tra, từ đó có hai nhánh đi ra ghi Đúng và Sai
- Thao tác nhập dữ liệu từ bàn phím hoặc xuất kết quả ra màn hình
- Điểm bắt đầu và điểm kết thúc của thuật toán
- Một phép tính hoặc một phép gán giá trị cho biến
- Mỗi bước phải rõ ràng, chỉ có thể hiểu theo đúng một nghĩa duy nhất
- Thuật toán phải dừng lại sau một số hữu hạn bước
- Thuật toán phải cho kết quả đúng với mọi bộ dữ liệu vào hợp lệ
- Thuật toán phải được viết bằng một ngôn ngữ lập trình cụ thể như Python hoặc C++
- a)Trong sơ đồ khối, một mũi tên quay ngược trở lại khối đã đi qua phía trên là dấu hiệu cho thấy thuật toán có cấu trúc lặp.Đúng
- b)Chỉ cần thuật toán cho kết quả đúng với một bộ dữ liệu thử là đã đủ để khẳng định thuật toán có tính đúng đắn.Sai
- c)Cùng một thuật toán có thể được mô tả bằng cách liệt kê các bước hoặc bằng sơ đồ khối; hai cách trình bày khác nhau nhưng diễn tả cùng một dãy thao tác.Đúng
- d)Khi chuyển sơ đồ khối sang Python, khối hình bình hành dùng để nhập dữ liệu thường được viết thành câu lệnh
if.Sai
- (a) Đúng - mũi tên quay ngược lên một khối đã đi qua khiến nhóm bước ở giữa được thực hiện lại nhiều lần, đó chính là vòng lặp; khi dịch sang Python nó thành
forhoặcwhile. - (b) Sai - tính đúng đắn đòi hỏi kết quả đúng với mọi bộ dữ liệu vào hợp lệ, kể cả các trường hợp đặc biệt như số 0, số âm hay dãy chỉ có một phần tử; đúng với một ví dụ may mắn thì chưa nói lên điều gì.
- (c) Đúng - liệt kê các bước và vẽ sơ đồ khối chỉ là hai hình thức ghi lại cùng một cách giải; sơ đồ khối trực quan hơn ở chỗ rẽ nhánh và vòng lặp, còn liệt kê thì nhanh gọn hơn khi thuật toán đơn giản.
- (d) Sai - khối hình bình hành nhập dữ liệu được dịch thành
input(); chính khối hình thoi kiểm tra điều kiện mới được dịch thànhif.
Thử ngay: minh hoạ từng bước
Bấm từng bước để tự xem cơ chế hoạt động, hoặc bấm “Tự chạy” cho nó tiến mỗi giây một lần. Đổi được dữ liệu đầu vào - không cần đăng nhập.
Học trọn bài này trong ứng dụng
Bài giảng đầy đủ, 24 câu luyện tập chấm tự động, thi thử đúng cấu trúc đề tốt nghiệp (24 trắc nghiệm + 4 Đúng/Sai), bài thực hành máy tự chấm và gia sư AI giải thích chỗ sai.
Phần học miễn phí, không cần tạo tài khoản.
Bài liên quan - Lập trình, Thuật toán & CTDL (KHMT)
Cùng mạch kiến thức với bài này, học nối tiếp cho chắc phần lí thuyết.