Tóm tắt lý thuyết 1. Bài toán và xác định bài toán a. Bài toán Bài toán là một công việc hay một nhiệm vụ cần phải giải quyết. Ví dụ về bài toán: Bài toán 1: Tính tổng của các số tự nhiên từ 1 đến 100 Bài toán 2: Tính quãng đường ô tô đi được trong 3 giờ với vận tốc 60km/giờ Bài toán 3: Tính diện tích hình tam giác Bài toán 4: Tính điểm trung bình của 3 môn Toán, Lý, Tin Bài toán 5: Bài toán điều khiển Rô-bốt nhặt rác Bài toán 6: Lập bảng điểm của các bạn trong lớp b. Xác định bài toán Để giải quyết được một bài toán cụ thể, người ta cần xác định bài toán, tức là xác định rõ các điều kiện cho trước và kết quả thu được. Ví dụ xác định các bài toán sau: Bài toán 3: Tính diện tích hình tam giác Điều kiện cho trước: Một cạnh và đường cao tương ứng với cạnh đó Kết quả cần thu được: Diện tích hình tam giác 2. Quá trình giải bài toán trên máy tính a. Khái niệm thuật toán Thuật toán là dãy hữu hạn các thao tác cần thực hiện để giải một bài toán Giải bài toán trên máy tính nghĩa là đưa cho máy tính dãy hữu hạn các thao tác đơn giản (thuật toán) để máy tính thực hiện và cho kết quả Chương trình chỉ là thể hiện của thuật toán trong một ngôn ngữ lập trình cụ thể Ví dụ Bài toán điều khiển rô-bốt nhặt rác: 1. Tiến 2 bước; 2. Quay trái, tiến 1 bước; 3. Nhặt rác; 4. Quay phải, tiến 3 bước; 5. Quay trái, tiến 2 bước; 6. Bỏ rác vào thùng; b. Quá trình giải bài toán trên máy tính Hình 1. Quá trình giải bài toán trên máy tính Quá trình giải bài toán trên máy tính gồm 3 bước: Xác định bài toán: Xác định thông tin đã cho (Input) Thông tin cần tìm (Output) Mô tả thuật toán: Tìm cách giải bài toán và diễn tả bằng các lệnh cần phải thực hiện Viết chương trình: Dựa vào mô tả thuật toán, ta viết chương trình bằng một ngôn ngữ lập trình 3. Thuật toán và mô tả thuật toán a. Khái niệm Mô tả thuật toán là liệt kê các bước cần thiết để giải một bài toán b. Các ví dụ Ví dụ 1: Thuật toán pha trà mời khách Input: Trà, nước sôi, ấm và chén Output: Chén trà đã pha để mời khách Các bước thực hiện để pha trà mời khách: Bước 1. Tráng ấm chén bằng nước sôi. Bước 2. Cho một ít trà vào ấm. Bước 3. Tráng trà Bước 4. Rót nước sôi vào ấm và đợi 3 – 4 phút Bước 5. Rót trà ra chén để mời khách Ví dụ 2: Thuật toán "Làm món trứng tráng" Input: Trứng, dầu ăn, muối, hành Output: Món trứng tráng Các bước thực hiện để làm món trứng tráng: Bước 1. Đập trứng, tách vỏ và cho trứng vào bát Bước 2. Cho một chút muối và hành tươi thái nhỏ vào bát trứng. Dùng đũa quấy mạnh cho đến khi đều Bước 3. Cho một thìa dầu ăn vào chảo, đun nóng đều rồi đổ trứng vào. Đun tiếp trong khoảng 1 phút Bước 4. Lật mặt trên của miếng trứng úp xuống dưới. Đun tiếp trong khoảng 1 phút Bước 5. Lấy trứng ra đĩa 4. Một số ví dụ về thuật toán Ví dụ 3: Một hình A được ghép từ một hình chữ nhật với chiều rộng 2a, chiều dài b và một hình bán nguyệt ban kính a như hình dưới đây: Xác định bài toán: Input: Số a là \(\frac{1}{2}\) chiều rộng của hình chữ nhật và là bán kính của hình bán nguyệt, b là chiều dài của hình chữ nhật Output: Diện tích của hình A Mô tả thuật toán: Bước 1. Tính \(S_{1} = 2a \times b\) {Tính diện tích hình chữ nhật} Bước 2. Tính \(S_{2} = \pi a^{2}/2\) {Tính diện tích hình bán nguyệt} Bước 3. Tính kết quả \(S = S_{1} + S_{2}\); Và kết thúc Ví dụ 4: Viết thuật toán tính tổng 100 số tự nhiên đầu tiên S = 0; S1 = S + 1; S2 = S1 + 2; S3 = S2 + 3; ... S100 = S99 + 100 Xác định bài toán: Input: Dãy 100 số tự nhiên đầu tiên Output: Giá trị của tổng 1 + 2 + ... + 100 Mô tả thuật toán: Bước 1. SUM \(\leftarrow\) 0; i \( \leftarrow\) 0 Bước 2. i \( \leftarrow\) i + 1 Bước 3. Nếu i \(\leq\) 100, thì SUM \( \leftarrow\) SUM + 1 và quay lại Bước 2 Bước 4. Thông báo kết quả và kết thúc thuật toán Mô phỏng thuật toán với số liệu cụ thể: Với N=5: Ví dụ 5: Đổi giá trị của hai biến x, y Xác định bài toán: Input: Hai biến x, y có giá tri tương ứng là a và b Output: Hai biến x, y có giá trị tương ứng là b và a Mô tả thuật toán: Bước 1. \(z \leftarrow a\) {Sau bước này giá trị của z sẽ bằng a} Bước 2. \(x\leftarrow y\) {Sau bước này giá trị của x sẽ bằng b} Bước 3. \(y \leftarrow z\) {Sau bước này giá trị của y sẽ bằng giá trị của z, chính là a, giá trị ban đầu của biến x} Ví dụ 6: Cho hai số thực a, b. Hãy cho biết kết quả so sánh hai số đó dưới dạng "a lớn hơn b", "a nhỏ hơn b" hoặc "a bằng b" Xác định bài toán: Input: hai số thực a và b Output: kết quả so sánh Mô tả thuật toán: Bước 1. Nếu a >b, kết quả là "a lớn hơn b" và chuyển đến Bước 3 Bước 2. Nếu a < b, kết quả là "a nhỏ hơn b"; ngược lại, kết quả là "a bằng b" Bước 3. Kết thúc thuật toán Ví dụ 7: Tìm số lớn nhất trong dãy A các số: \(a_{1}, a_{2},...,a_{n}\) Xác định bài toán: Input: dãy A các số \(a_{1},a_{2},...a_{n}\space (n\geq1)\) Output: Giá trị MAX = max \(\left\{a_{1},a_{2},...,a_{n}\right\}\) Mô tả thuật toán: Bước 1. \(MAX \leftarrow a_{1}; \space i\leftarrow 1 \) Bước 2. \( i \leftarrow i + 1 \) Bước 3. nếu i > n, chuyển đến bước 5 Bước 4. Nếu \(a_{i} > MAX, \space MAX \leftarrow a_{i} \). Quay lại bước 2 Bước 5. Kết thúc thuật toán
