TIN H?C (INFORMATICS)
SỞ GD-ĐT QUẢNG TRỊ
TRƯỜNG THPT LAO BẢO
Gv: Lê Quang Vinh
Chúc một tiết học đạt hiệu quả cao!
KIỂM TRA BÀI CŨ
1/ Nêu khái niệm bài toán tin học. Hai đại lượng cơ bản trong bài toán tin học là gì?
1/ Khái niệm bài toán:
2/ Xác định Input và Output của bài toán tìm giá trị lớn nhất trong 3 số nguyên.

- Input:

- Output:
Ba số nguyên a, b, c.
Giá trị lớn nhất trong 3 số a, b, c.
Để tìm Output ta phải trải qua một quá trình tính toán, biến đổi Input. Quá trình đó được gọi là Thuật toán.

Băi 4: BÀI TOÁN VÀ THUẬT TOÁN (Tiết 1)
Làm thế nào để tìm được Output?

Băi 4: BÀI TOÁN VÀ THUẬT TOÁN
Thuật toán (algorithm):
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 một 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.
1/ Khái niệm bài toán:
2/ Khái niệm thuật toán:
*/ Khái niệm:
(SGK)
TIẾT 11
(Tiết 2)
Tiết 11:
Băi 4: BÀI TOÁN VÀ THUẬT TOÁN (Tiết 2)
1/ Khái niệm bài toán:
2/ Khái niệm thuật toán:
*/ Khái niệm:
(SGK)
*/ Ví dụ về thuật toán:
Ví dụ: Tìm giá trị lớn nhất của một dãy số nguyên:
*/ Xác định bài toán:
- Input:
- Output:
Số nguyên dương N và dãy số nguyên a1, ..., aN.
Giá trị lớn nhất Max của dãy số..
*/ Ý tưởng tiến hành:
- Khởi tạo giá trị Max = a1;
- Lần lượt với i tăng từ 2 đến N và so sánh từng giá trị của ai với giá trị Max, nếu ai > Max thì cho Max nhận giá trị mới là ai.
*/ Thuật toán: (Theo cách liệt kê từng bước)
Bước 1: Nhập N và dãy a1 ... aN;
Bước 2: Max ? a1, i ? 2;
Bước 3: Nếu i > N thì đưa ra giá trị Max rồi kết thúc.
Bước 4:
Bước 4.1: Nếu ai > Max thì Max ? ai;
Bước 4.2: i ? i + 1 rồi quay lại Bước 3;
Tiết 11:
Băi 4: BÀI TOÁN VÀ THUẬT TOÁN (Tiết 2)
1/ Khái niệm bài toán:
2/ Khái niệm thuật toán:
*/ Khái niệm:
(SGK)
*/ Ví dụ về thuật toán:
Ví dụ: Tìm giá trị lớn nhất của một dãy số nguyên:
*/ Thuật toán: (Theo cách liệt kê từng bước)
Bước 1: Nhập N và dãy a1 ... aN;
Bước 2: Max ? a1, i ? 2;
Bước 3: Nếu i > N thì đưa ra giá trị Max rồi kết thúc.
Bước 4:
Bước 4.1: Nếu ai > Max thì Max ? ai;
Bước 4.2: i ? i + 1 rồi quay lại Bước 3;
*/ Chú ý:
Mũi tên ? được hiểu là thay đổi giá trị của biến bên trái bằng giá trị của biểu thức bên phải (phép gán).
Giá trị của i thay đổi (tăng) từ 2 đến N + 1.
Được biểu thị bằng thao tác: i ? i + 1.
Tiết 11:
Băi 4: BÀI TOÁN VÀ THUẬT TOÁN (Tiết 2)
1/ Khái niệm bài toán:
2/ Khái niệm thuật toán:
*/ Khái niệm:
(SGK)
*/ Ví dụ về thuật toán:
*/ Các khối chức năng và mũi tên trong sơ đồ khối:
*/ 2 cách mô tả thuật toán:
- Liệt kê từng bước.
- Sơ đồ khối.
Hình thoi thể hiện thao tác so sánh
Hình chữ nhật thể hiện các phép tính toán
Hình ô van thể hiện thao tác nhập, xuất dữ liệu
Mũi tên thể hiện trình tự thực hiện các thao tác
Tiết 11:
Băi 4: BÀI TOÁN VÀ THUẬT TOÁN (Tiết 2)
1/ Khái niệm bài toán:
2/ Khái niệm thuật toán:
*/ Khái niệm:
(SGK)
*/ Ví dụ về thuật toán:
Ví dụ: Tìm giá trị lớn nhất của một dãy số nguyên:
*/ Thuật toán: (Theo cách dùng sơ đồ khối)
Nhập N và dãy a1, ... aN
Max  a1, i  2
i > N?
ai > Max?
Max  ai
i  i + 1
Đưa ra Max
rồi kết thúc
*/ 2 cách mô tả thuật toán:
- Liệt kê từng bước.
- Sơ đồ khối.
Tiết 11:
Băi 4: BÀI TOÁN VÀ THUẬT TOÁN (Tiết 2)
1/ Khái niệm bài toán:
2/ Khái niệm thuật toán:
*/ Khái niệm:
(SGK)
*/ Ví dụ về thuật toán:
Ví dụ: Tìm giá trị lớn nhất của một dãy số nguyên:
*/ Thuật toán: (Theo cách dùng sơ đồ khối)
Nhập N và dãy a1, ... aN
Max  a1, i  2
i > N?
ai > Max?
Max  ai
i  i + 1
Đưa ra Max
rồi kết thúc
*/ 2 cách mô tả thuật toán:
- Liệt kê từng bước.
- Sơ đồ khối.
Tiết 11:
Băi 4: BÀI TOÁN VÀ THUẬT TOÁN (Tiết 2)
1/ Khái niệm bài toán:
2/ Khái niệm thuật toán:
*/ Khái niệm:
(SGK)
*/ Ví dụ về thuật toán:
Ví dụ: Tìm giá trị lớn nhất của một dãy số nguyên:
*/ Thuật toán: (Theo cách dùng sơ đồ khối)
Nhập N và dãy a1, ... aN
Max  a1, i  2
i > N?
ai > Max?
Max  ai
i  i + 1
Đưa ra Max
rồi kết thúc
*/ 2 cách mô tả thuật toán:
- Liệt kê từng bước.
- Sơ đồ khối.
Tiết 11:
Băi 4: BÀI TOÁN VÀ THUẬT TOÁN (Tiết 2)
1/ Khái niệm bài toán:
2/ Khái niệm thuật toán:
*/ Khái niệm:
(SGK)
*/ Ví dụ về thuật toán:
Ví dụ: Tìm giá trị lớn nhất của một dãy số nguyên:
Nhập N = 8 và dãy a1= 5, a2 = 1, a3 = 4,
a4 = 7, a5 = 6, a6 = 12, a7 = 15, a8 = 10
Max  a1(5), i  2
i > N
ai > Max?
i  i + 1
ai = a2 = 1, Max = 5
i = 2 +1 = 3
i = 2, N = 8
*/ 2 cách mô tả thuật toán:
- Liệt kê từng bước.
- Sơ đồ khối.
Tiết 11:
Băi 4: BÀI TOÁN VÀ THUẬT TOÁN (Tiết 2)
1/ Khái niệm bài toán:
2/ Khái niệm thuật toán:
*/ Khái niệm:
(SGK)
*/ Ví dụ về thuật toán:
Ví dụ: Tìm giá trị lớn nhất của một dãy số nguyên:
Nhập N = 8 và dãy a1= 5, a2 = 1, a3 = 4,
a4 = 7, a5 = 6, a6 = 12, a7 = 15, a8 = 10
Max  a1(5), i  2
i > N
ai > Max?
i  i + 1
ai = a3 = 4, Max = 5
i = 3 +1 = 4
i = 3, N = 8
*/ 2 cách mô tả thuật toán:
- Liệt kê từng bước.
- Sơ đồ khối.
Tiết 11:
Băi 4: BÀI TOÁN VÀ THUẬT TOÁN (Tiết 2)
1/ Khái niệm bài toán:
2/ Khái niệm thuật toán:
*/ Khái niệm:
(SGK)
*/ Ví dụ về thuật toán:
Ví dụ: Tìm giá trị lớn nhất của một dãy số nguyên:
Nhập N = 8 và dãy a1= 5, a2 = 1, a3 = 4,
a4 = 7, a5 = 6, a6 = 12, a7 = 15, a8 = 10
Max  a1(5), i  2
i > N
ai > Max?
i  i + 1
ai = a4 = 7, Max = 5
i = 4 +1 = 5
i = 4, N = 8
Max  ai
Max = a4 = 7
*/ 2 cách mô tả thuật toán:
- Liệt kê từng bước.
- Sơ đồ khối.
Tiết 11:
Băi 4: BÀI TOÁN VÀ THUẬT TOÁN (Tiết 2)
1/ Khái niệm bài toán:
2/ Khái niệm thuật toán:
*/ Khái niệm:
(SGK)
*/ Ví dụ về thuật toán:
Ví dụ: Tìm giá trị lớn nhất của một dãy số nguyên:
Nhập N = 8 và dãy a1= 5, a2 = 1, a3 = 4,
a4 = 7, a5 = 6, a6 = 12, a7 = 15, a8 = 10
Max  a1(5), i  2
i > N
ai > Max?
i  i + 1
ai = a5 = 6, Max = 7
i = 5 +1 = 6
i = 5, N = 8
*/ 2 cách mô tả thuật toán:
- Liệt kê từng bước.
- Sơ đồ khối.
Tiết 11:
Băi 4: BÀI TOÁN VÀ THUẬT TOÁN (Tiết 2)
1/ Khái niệm bài toán:
2/ Khái niệm thuật toán:
*/ Khái niệm:
(SGK)
*/ Ví dụ về thuật toán:
Ví dụ: Tìm giá trị lớn nhất của một dãy số nguyên:
Nhập N = 8 và dãy a1= 5, a2 = 1, a3 = 4,
a4 = 7, a5 = 6, a6 = 12, a7 = 15, a8 = 10
Max  a1(5), i  2
i > N
ai > Max?
i  i + 1
ai = a6 = 12, Max = 7
i = 6 +1 = 7
i = 6, N = 8
Max  ai
Max = a6 = 12
*/ 2 cách mô tả thuật toán:
- Liệt kê từng bước.
- Sơ đồ khối.
Tiết 11:
Băi 4: BÀI TOÁN VÀ THUẬT TOÁN (Tiết 2)
1/ Khái niệm bài toán:
2/ Khái niệm thuật toán:
*/ Khái niệm:
(SGK)
*/ Ví dụ về thuật toán:
Ví dụ: Tìm giá trị lớn nhất của một dãy số nguyên:
Nhập N = 8 và dãy a1= 5, a2 = 1, a3 = 4,
a4 = 7, a5 = 6, a6 = 12, a7 = 15, a8 = 10
Max  a1(5), i  2
i > N
ai > Max?
i  i + 1
ai = a7 = 15, Max = 12
i = 7 +1 = 8
i = 7, N = 8
Max  ai
Max = a7 = 15
*/ 2 cách mô tả thuật toán:
- Liệt kê từng bước.
- Sơ đồ khối.
Tiết 11:
Băi 4: BÀI TOÁN VÀ THUẬT TOÁN (Tiết 2)
1/ Khái niệm bài toán:
2/ Khái niệm thuật toán:
*/ Khái niệm:
(SGK)
*/ Ví dụ về thuật toán:
Ví dụ: Tìm giá trị lớn nhất của một dãy số nguyên:
Nhập N = 8 và dãy a1= 5, a2 = 1, a3 = 4,
a4 = 7, a5 = 6, a6 = 12, a7 = 15, a8 = 10
Max  a1(5), i  2
i > N
ai > Max?
i  i + 1
ai = a8 = 10, Max = 15
i = 8 +1 = 9
i = 8, N = 8
*/ 2 cách mô tả thuật toán:
- Liệt kê từng bước.
- Sơ đồ khối.
Tiết 11:
Băi 4: BÀI TOÁN VÀ THUẬT TOÁN (Tiết 2)
1/ Khái niệm bài toán:
2/ Khái niệm thuật toán:
*/ Khái niệm:
(SGK)
*/ Ví dụ về thuật toán:
Ví dụ: Tìm giá trị lớn nhất của một dãy số nguyên:
Nhập N = 8 và dãy a1= 5, a2 = 1, a3 = 4,
a4 = 7, a5 = 6, a6 = 12, a7 = 15, a8 = 10
Max  a1(5), i  2
i > N
Max = 15
i = 9, N = 8
Đưa ra Max = 15
rồi kết thúc
*/ 2 cách mô tả thuật toán:
- Liệt kê từng bước.
- Sơ đồ khối.
Chương trinh ví dụ
Tiết 11:
Băi 4: BÀI TOÁN VÀ THUẬT TOÁN (Tiết 2)
1/ Khái niệm bài toán:
2/ Khái niệm thuật toán:
*/ Khái niệm:
(SGK)
*/ Ví dụ về thuật toán:
*/ 2 cách mô tả thuật toán:
- Liệt kê từng bước.
- Sơ đồ khối.
Thuật toán có các tính chất sau:
- Tính dừng: Thuật toán phải kết thúc sau một số hữu hạn lần thực hiện.
VD: giá trị i tăng nên sau N lần thì i > N => Kết thúc.
- Tính xác định: Sau một thao tác tìh hoặc là kết thúc thuật toán hoặc là thực hiện thao tác tiếp theo.
VD: Sau bước 1 sẽ là bước 2, sau bước 4.2 sẽ là bước 3.
- Tính đúng đắn: Thuật toán kết thúc phải tìm ra được Output cần tìm.
VD: Max được lần lượt so sánh với từng giá trị trong dãy số và Max ? ai khi ai > Max nên ta sẽ nhận được Max mong muốn.
*/ Các tính chất của thuật toán:
Ví dụ thuật toán sau:
Bước 1: Viết lên bảng chữ "10A1";
Bước 2: Xoá bảng.
Bước 3: Quay lại bước 1.
Tiết 11:
Băi 4: BÀI TOÁN VÀ THUẬT TOÁN (Tiết 2)
1/ Khái niệm bài toán:
2/ Khái niệm thuật toán:
*/ Khái niệm:
(SGK)
*/ Ví dụ về thuật toán:
Bài tập:
Diễn tả thuật toán cho bài toán tìm tất cả các ước số dương của một số nguyên dương.
*/ 2 cách mô tả thuật toán:
- Liệt kê từng bước.
- Sơ đồ khối.
Ý tưởng thuật toán:
- Cho i tăng từ 1 đến N. Nếu N chia hết cho i thì i là ước số của N.
- Input:

- Output:
Số nguyên dương N.
Tất cả các số là ước số của N.
*/ Các tính chất của thuật toán:
Tiết 11:
Băi 4: BÀI TOÁN VÀ THUẬT TOÁN (Tiết 2)
1/ Khái niệm bài toán:
2/ Khái niệm thuật toán:
*/ Khái niệm:
(SGK)
*/ Ví dụ về thuật toán:
Bài tập:
Diễn tả thuật toán cho bài toán tìm tất cả các ước số dương của một số nguyên dương.
*/ 2 cách mô tả thuật toán:
- Liệt kê từng bước.
- Sơ đồ khối.
Theo cách liệt kê từng bước
Bước 1: Nhập N;
Bước 2: i ? 1;
Bước 3: Nếu i > N thì kết thúc.
Bước 4: Nếu N chia hết cho i thì thông báo i là ước số.
Bước 5: i ? i + 1 rồi quay lại Bước 3;
*/ Các tính chất của thuật toán:
Tiết 11:
Băi 4: BÀI TOÁN VÀ THUẬT TOÁN (Tiết 2)
1/ Khái niệm bài toán:
2/ Khái niệm thuật toán:
*/ Khái niệm:
(SGK)
*/ Ví dụ về thuật toán:
*/ Thuật toán: (Theo sơ đồ khối)
Nhập N
i  1
i > N?
N chia hãút i?
i  i + 1
Kết thúc
*/ 2 cách mô tả thuật toán:
- Liệt kê từng bước.
- Sơ đồ khối.
Viết ra ước số i
*/ Các tính chất của thuật toán:
Tiết 11:
Băi 4: BÀI TOÁN VÀ THUẬT TOÁN (Tiết 2)
1/ Khái niệm bài toán:
2/ Khái niệm thuật toán:
*/ Khái niệm:
(SGK)
*/ Ví dụ về thuật toán:
*/ Thuật toán: (Theo sơ đồ khối)
Nhập N
i  3
i  N?
N chia hãút i?
i  i + 1
Kết thúc
*/ 2 cách mô tả thuật toán:
- Liệt kê từng bước.
- Sơ đồ khối.
Viết ra ước số i
*/ Các tính chất của thuật toán:
Tiết 11:
Băi 4: BÀI TOÁN VÀ THUẬT TOÁN (Tiết 2)
1/ Khái niệm bài toán:
2/ Khái niệm thuật toán:
*/ Khái niệm:
(SGK)
*/ Ví dụ về thuật toán:
*/ Thuật toán: (Theo sơ đồ khối)
Nhập N
i  1
i > N?
N chia hãút i?
i  i + 1
Kết thúc
*/ 2 cách mô tả thuật toán:
- Liệt kê từng bước.
- Sơ đồ khối.
Viết ra ước số i
Bài toán xác định tính nguyên tố của một số nguyên dương
*/ Các tính chất của thuật toán:
TIN H?C (INFORMATICS)
Lớp làm bài tập 4, 5 (trang 44 SGK);
Chuẩn bị nội dung tiếp theo của bài.