Bài 6: Xây dựng thuật toán
Thuật toán là gì?
Để giải quyết một vấn đề đặt ra hay một bài toán, người lập trình không chỉ có sử dụng một ngôn ngữ lập trình nào đó để lập trình, mà trước đó người lập trình phải trải qua nhiều giai đoạn trước khi lập trình. Lập trình viên phải hiểu rõ những dữ liệu gì được sử dụng, kết quả mong muốn của chương trình là gì và sử dụng phương pháp gì để có được kết quả đó từ dữ liệu đã biết. Các phương pháp đó phải có trình tự nhằm biến đổi dữ liệu đầu vào thành kết quả mong muốn. Trình tự để giải bài toán đó được gọi là thuật toán (algorithm). Về cơ bản, thuật toán được định nghĩa là một dãy hữu hạn các bước nhằm diễn tả quá trình xử lý dữ liệu đầu vào rồi đưa ra kết quả như mong muốn.
Tính chất của thuật toán
Các tính chất của thuật toán bao gồm:
- Đầu vào: đầu vào của thuật toán là dữ liệu bài toán cung cấp cho chương trình.
- Đầu ra: đầu ra của thuật toán là kết quả của yêu cầu cho bài toán đó.
- Tính chính xác: mỗi thuật toán phải đưa ra kết quả chính xác với mỗi đầu vào tương ứng.
- Tính hữu hạn: mỗi thuật toán cần đưa ra kết quả sau một số bước hữu hạn bước.
- Tính phổ thông: thuật toán phải giải quyết được một lớp các bài toán có cùng dạng, không đơn thuần là chỉ một bài toán cụ thể.
Phương pháp biểu diễn thuật toán
Các phương pháp biểu diễn thuật toán cơ bản gồm:
– Phương pháp liệt kê từng bước: các bước thực hiện ý tưởng giải quyết bài toán sẽ được liệt kê theo trình tự từ bước đầu tiên đến bước cuối cùng. Phương pháp này chỉ phù hợp với những dự án nhỏ, với các dự án lớn sẽ rất khó khăn trong việc áp dụng vì số lượng các bước là quá nhiều, gây khó khăn cho các công đoạn tiếp theo.
Ví dụ: Mô tả thuật toán tìm giá trị lớn nhất của một dãy hữu hạn các số nguyên. Thuật toán trên được minh hoạ theo phương pháp liệt kê từng bước như sau:
- Bước 1: Giả sử phần tử đầu tiên của dãy là phần tử có giá trị lớn nhất max.
- Bước 2: So sánh phần tử thứ hai với phần tử max nếu phần tử max nhỏ hơn thì đặt giá trị max bằng giá trị của phần tử thứ hai.
- Bước 3: Nếu vẫn còn các phần tử tiếp theo thì thực hiện lặp lại giống như bước 2.
- Bước 4: Thuật toán sẽ dừng lại nếu không còn phần tử nào chưa được xét duyệt. Phần tử max cuối cùng sẽ là giá trị lớn nhất của dãy.
– Phương pháp vẽ sơ đồ khối: khi sử dụng phương pháp này để biểu diễn thuật toán, mỗi thao tác của thuật toán sẽ được minh hoạ bằng các khối hình. Hình sau mô tả các khối được sử dụng khi xây dựng sơ đồ khối:
Các ký hiệu trong sơ đồ khối
Sơ đồ khối cho bài toán tính tổng từ 1 đến n
Sơ đồ khối cho bài toán tìm số lớn nhất trong 3 số nguyên
