Cùng học Pascal

CHƯƠNG I
THUẬT TOÁN
I. Khái niệm thuật toán.
1. Khái niệm: Thuật toán là một hệ thống chặt chẽ và rõ ràng các qui tắc nhằm xác định một dãy các thao tác trên những lớp đối tượng sao cho sau một số hữu hạn bước thực hiện các thao tác đó ta đạt được mục đích đề ra.
2. Ví dụ: Một hộp kín chứa hữu hạn các viên bi có kích thước khác nhau. Hãy tìm ra thuật toán tìm viên bi lớn nhất, biết rằng mỗi lần chỉ được bốc 1 viên.
- Thuật toán được trình bày như sau:
B1: Bốc một viên bi bất kỳ.
B2: Kiểm tra xem hộp đã rỗng chưa?
- Nếu đúng chuyển qua bước 4.
- Nếu sai chuyển sang bước 3.
B3: Bốc tiếp một viên bi khác, so sánh 2vieen bi và giữ lại viên lớn hơn rồi chuyển sang B2.
B4: Viên bi hiện tại là viên bi lớn nhất, kết thúc.
Rõ ràng theo thuật toán trên, một hộp nào đó có chứa các viên bi – lần lượt làm theo các bước đó ta sẽ tìm ra viên lớn nhất.
II. Các tính chất của thuật toán.
1. Tính phổ dụng: Thuật toán không chỉ để giải quyết một bài toán riêng lẻ mà được dùng để giải quyết một lớp các bài toán, các bài toán cùng loại.
2. Tính hữu hạn: Thuật toán phải được kết thúc sau một số hữu hạn bước thực hiện các thao tác. Một thuật toán không có tính hữu hạn là không khả thi.
3. Tính xác định: Thuật toán đòi hỏi mỗi bước thao tác phải rõ ràng và xác định một cách đơn trị bước tiếp theo.
4. Tính hiệu quả: Thể hiện ở các yếu tố sau:
-Tính đúng đắn.
- Tính tối ưu: Tiết kiệm thời gian thực hiện, tiết kiệm bộ nhớ.
III. Các đại lượng của thuật toán.
1. Đại lượng vào: Là những đại lượng cho trước làm cơ sở cho việc hình thành nên bài toán (Giả thiết).
2. Đại lượng ra: Thường là kết quả sau khi đã thực hiện xong thuật toán và đó cũng là yêu cầu của bài toán.
3. Đại lượng trung gian: Là các đại lượng tham gia vào quá trình để giải bài toán nhưng không phải là đại lượng vào cũng không phải là đại lượng ra.
Ví dụ: Để đổi giá trị của hai số cho nhau a và b.
- Đại lượng vào: hai số a và b
- Đại lượng ra: hai số a và b với giá trị ngược lại.
- Đại lượng trung gian: dùng một đại lương trung gian để lưu một giá trị a hoặc b.

4. Hằng, biến, kiểu.
Để biểu diễn các đại lượng nêu trên của thuật toán ta sử dụng các hằng, biến và phải có kiểu nhất định.
- Hằng: Là đại lượng không thay đổi trong quá trình thực hiện thuật toán.
- Biến: Là đại lượng có thể thay đổi giá trị trong quá trình thực hiện thuật toán
- Kiểu: Là tập hợp các giá trị (miền trị) mà các đại lượng có thể nhận, đồng thời với việc qui định các phép toán tác động trên đó.
IV. Biểu diễn của thuật toán.
1. Các dạng biểu diễn của thuật toán: Có thể biểu diễn thuật toán bằng 3 dạng sau:
- Liệt kê các bước.
- Cấu trúc theo ngôn ngữ qui ước của thuật toán.
- Sơ đồ khối.
2. Biểu diễn thuật toán bằng sơ đồ khối: Đây là dạng biểu diễn có cấu trúc trực quan, rõ ràng.
a, Các kí hiệu dùng để biểu diễn thuật toán.



Dùng để chỉ sự bắt đầu hoặc kết thúc thuật toán





Dùng để chỉ việc nhập dữ liệu và ghi dữ liệu ra màn hình





Dùng để biểu diễn các thao tác của thuật toán.



Dùng để kiểm tra điều kiện.



Dùng để chỉ hướng đi của thuật toán.


Ngoài ra ta còn sử dụng kí hiệu := để biểu diễn cho việc gán giá trị cho các biến.
b, Ví dụ 1: Vẽ sơ đồ thuật toán để giải phương trình: ax + b = 0.
- Dữ liệu vào: a, b.
- Dữ liệu ra là nghiệm hoặc một câu thông báo.











Ví dụ 2: Sơ đồ thuật toán để giải bài toán tính tổng:
S = 1 + 2 + 3 + … + n.
(Với n nguyên dương bất kỳ và không dùng công thức S = n(n +1)/2)



















V. Một số thuật toán đơn