Microsoft Word 202010211526475f8ff0c7a1d85 cac-dang-bai-toan-thuat-toan-tin-hoc-10-2020-phan-1 (1). doc

 
Thư viện đề thi – Thư viện đề kiểm tra online hot nhất
Trang chủ: 
https://tailieu.com/
 | Email: 
info@tailieu.com
 | 
https://www.facebook.com/KhoDeThiTaiLieuCom

Tóm tắt lý thuyết: 
 
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. 
Một số ví dụ về thuật toán 

 
Thư viện đề thi – Thư viện đề kiểm tra online hot nhất
Trang chủ: 
https://tailieu.com/
 | Email: 
info@tailieu.com
 | 
https://www.facebook.com/KhoDeThiTaiLieuCom

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ố″. 
• Ý tưởng: 
- Đị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″ 
- 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ố. 
- 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