Trong lớp 10 bộ môn tin học chúng ta đã học những khái niệm cơ bản về “Thuật toán” rồi đúng không? Hôm nay mình sẽ tổng hợp lại kiến thức về “thuật toán trong tin học“ cho những ai cần tìm nhé!.
1. Thuật toán trong tin học là gì?
– Thuật toán để giải một bài toán là một 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 ra Output cần tìm.
2. Các tính chất của thuật toán:
– Tính xác định: các bước giải phải rõ ràng không gây ra sự lẫn lộn hoặc nhập nhằng.
– Tính dừng: Thuật toán phải dừng lại sau một số bước giải.
– Tính đúng: Kết quả sau khi thực hiện thuật giải phải là kết quả đúng dựa theo một định nghĩa hoặc một kết quả cho trước.
3. Tính hiệu quả:
- Phải sử dụng dung lượng bộ nhớ là nhỏ nhất.
- Số phép toán ít nhất.
- Thuật toán dễ hiểu không?
- Dễ khai báo trên máy tính.
4. Biểu diễn thuật toán?
* Sơ đồ khối:
Bài tập ví dụ:
* 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ố
– Định nghĩa: “Một số nguyên dương N là số nguyên tố nếu nó chỉ có đúng hai ước là 1 và N”
* Tính chất:
- Nếu N = 1 thì N không là số nguyên tố
- Nếu 1 < N < 4 thì N là số nguyên tố
* Ý tưởng
- – N<4: Xem như bài toán đã được giải quyết
- – N≥4: Tìm ước i đầu tiên > 1 của N
- + Nếu i < N thì N không là số nguyên tố (vì N có ít nhất 3 ước 1, i, N)
- + Nếu i = N thì N là số nguyên tố
Xây dựng thuật toán:
a) Cách liệt kê:
Bước 1: Nhập số nguyên dương N
Bước 2: Nếu N=1 thì thông báo “N không là số nguyên tố”, kết thúc;
Bước 3: Nếu N<4 thì thông báo “N là số nguyên tố”, kết thúc;
Bước 4: i← 2;
Bước 5: Nếu i là ước của N thì đến bước 7
Bước 6: i← i+1 rồi quay lại bước 5; ( tăng i lên 1 đơn vị)
Bước 7: Nếu i = N thì thông báo “N là số nguyên tố”, ngược lại thì thông báo “N không là số nguyên tố”, kết thúc;
b) Sơ đồ khối:
Lưu ý: Nếu N ≥ 4 và không có ước trong phạm vi từ 2 đến phần nguyên căn bậc 2 của N thì N là số nguyên tố
5. Kết luận:
Ok vậy là bài viết này mình đã giới thiệu xong hết cho mọi người về “Thuật toán trong tin học? SGK tin học lớp 10” chúc các bạn có những kiến thức thú vị.
