Một sơ ví dụ về thuật toán Tin 6

1. Khái niệm bài toán

- Bài toán là một việc nào đó mà con người muốn máy tính thực hiện.

- Các yếu tố của một bài toán:

+ Input: Thông tin đã biết, thông tin đưa vào máy tính.

+ Output: Thông tin cần tìm, thông tin lấy ra từ máy tính.

- Ví dụ: Bài toán tìm ước chung lớn nhất của 2 số nguyên dương, khi đó:

+ Input: hai số nguyên dương A, B.

+ Output: ước chung lớn nhất của A và B

2. Khái niệm thuật toán

a) Khái niệm

Thuật toán là 1 dãy hữu hạn các thao tác được sắp xếp theo 1 trình tự xác định sao cho sau khi thực hiện dãy thao tác ấy, từ Input của bài toán, ta nhận được Output cần tìm.

b) Biểu diễn thuật toán

- Sử dụng cách liệt kê: nêu ra tuần tự các thao tác cần tiến hành.

- Sử dụng sơ đồ khối để mô tả thuật toán. 

c) Các tính chất của thuật toán

- Tính dừng: thuật toán phải kết thúc sau 1 số hữu hạn lần thực hiện các thao tác.

- Tính xác định: sau khi thực hiện 1 thao tác thì hoặc là thuật toán kết thúc hoặc là có đúng 1 thao tác xác định để được thực hiện tiếp theo.

- Tính đúng đắn: sau khi thuật toán kết thúc, ta phải nhận được Output cần tìm.

3. Một số ví dụ về thuật toán

Ví dụ 1: Kiểm tra tính nguyên tố của 1 số nguyên dương

• Xác định bài toán

- Input: N là một số nguyên dương;

- Output: ″N là số nguyên tố″ hoặc ″N không là số nguyên tố″.

Xem thêm: Hoán Vị, Chỉnh Hợp, Tổ Hợp Và Bài Tập Tổ Hợp Xác Suất Có Đáp Án