Bài giảng Tin học Lớp 11 - Bài toán và thuật toán - Võ Văn Tú

Bài giảng 
BÀI TOÁN VÀ THUẬT TOÁN 
Chương trình Tin học 10 
Giáo viên: Võ Văn Tú 
Trường THPT Hai Bà Trưng 
Email: vvtu.hbt@hue.edu.vn 
BỘ GIÁO DỤC VÀ ĐÀO TẠO QUỸ LAWRENCE S.TING 
Cuộc thi quốc gia Thiết kế bài giảng e-Learning lần thứ 4 
-------------------- 
Điện thoại: 0123.240.9981 
Tháng 11/2016 
Số 14, đường Lê Lợi, Phường Vĩnh Ninh, TP Huế, tỉnh Thừa Thiên Huế 
Giấy phép bài dự thi: CC-BY-SA 
Bài 4. 
MỤC TIÊU 
BÀI TOÁN VÀ THUẬT TOÁN 
- Hiểu các thao tác cơ bản của thuật toán tìm giá trị lớn nhất của một dãy số nguyên; 
- Biết cách xác định các thành phần của bài toán; 
- Biết cách mô tả thuật toán theo cách liệt kê hoặc sơ đồ khối; 
- Hiểu cách thực hiện thuật toán với dãy số cụ thể trên thuật toán đã xây dựng. 
- Biết các khái niệm bài toán và thuật toán; 
KHÁI NIỆM BÀI TOÁN 
Ví dụ: 
Giải phương trình bậc 2 một ẩn: ax 2 + bx + c = 0 (a ≠ 0) 
Giải hệ phương trình bậc nhất hai ẩn: 
Input: 
Output: 
a, b, c (a ≠ 0) 
Phương trình vô nghiệm hoặc phương trình có nghiệm 
Input: 
Output: 
a 1 , b 1 , c 1 , a 2 , b 2 , c 2 
Hệ phương trình vô nghiệm hoặc có nghiệm (x, y ) thỏa mãn hệ phương trình. 
KHÁI NIỆM THUẬT TOÁN 
Ví dụ: Giải phương trình bậc 2 một ẩn: 
Tính Δ = b 2 - 4ac 
Nếu Δ < 0 thì phương trình vô nghiệm 
Nếu Δ ≥ 0 thì phương trình có nghiệm 
ax 2 + bx + c = 0 (a ≠ 0) 
Xác định các hệ số a, b, c 
4 thao tác 
 
 
 
 
Tính Δ = b 2 - 4ac 
Nếu Δ < 0 thì phương trình vô nghiệm 
Nếu Δ ≥ 0 thì phương trình có nghiệm 
Xác định và nhập các hệ số a, b, c 
Xác định và nhập các hệ số a, b, c 
a, b, c 
phương trình vô nghiệm 
phương trình có nghiệm 
Thuật toán để giả 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. 
Tìm giá trị lớn nhất của một dãy số nguyên 
Bài toán: Cho dãy A gồm n số nguyên a 1 , a 2 , , a n . Hãy tìm giá trị lớn nhất có trong dãy A . 
Ví dụ: 
Cho dãy A gồm 7 số nguyên: 12, 22, 66, 43, 75, 61, 54 
Giá trị lớn nhất của dãy A là: 75 
Tương ứng: 
n = 7 
a 1 a 2 a 3 a 4 a 5 a 6 a 7 
12 22 66 43 75 61 54 
Dãy A: 
Xin chúc mừng bạn! Nháy chuột để tiếp tục. 
Đồng ý 
Chọn lại 
* Xác định bài toán 
- Input: 
Tìm giá trị lớn nhất của một dãy số nguyên 
Bài toán: Cho dãy A gồm n số nguyên a 1 , a 2 , , a n . Hãy tìm giá trị lớn nhất có trong dãy số nguyên A. 
Số nguyên A, n và dãy số nguyên a 1 , a 2 , , a n 
Số nguyên dương n và dãy số nguyên a 1 , a 2 , , a n 
Dãy số nguyên a 1 , a 2 , , a n 
Rất tiếc! Chưa phải là phương án chính xác. Thử lại! 
A) 
B) 
C) 
Chính xác! Nháy chuột để tiếp tục 
Rất tiếc! Cố gắng tiếp nhé bạn! 
Đồng ý 
Làm lại 
* Xác định bài toán 
- Input: Số nguyên dương n và dãy số nguyên a 1 , a 2 , , a n . 
- Output: 
Tìm giá trị lớn nhất của một dãy số nguyên 
Bài toán: Cho dãy A gồm n số nguyên a 1 , a 2 , , a n . Hãy tìm giá trị lớn nhất có trong dãy số nguyên A. 
Dãy số nguyên A 
Giá trị lớn nhất của dãy số nguyên A 
Tìm giá trị lớn nhất của dãy số nguyên A 
A) 
B) 
C) 
* Xác định bài toán 
- Input: Số nguyên dương n và dãy số nguyên a 1 , a 2 , , a n . 
- Output: Giá trị lớn nhất (Max) của dãy số nguyên A. 
Tìm giá trị lớn nhất của một dãy số nguyên 
Bài toán: Cho dãy A gồm n số nguyên a 1 , a 2 , , a n . Hãy tìm giá trị lớn nhất có trong dãy số nguyên A. 
Quả thứ hai 
Quả thứ ba 
 0 g 
* Ý tưởng 
Tìm giá trị lớn nhất của một dãy số nguyên 
Quả bưởi nặng nhất là: 
Quả thứ nhất 
467 g 
635 g 
 ? g 
467 g 
635 g 
582 g 
- Khởi tạo giá trị Max = a 1 . 
- Lần lượt với i từ 2 đến n, so sánh giá trị số hạng a i với giá trị Max, nếu a i > Max thì Max nhận giá trị mới là a i . 
Bước 1. Nhập số nguyên dương n và dãy số nguyên a 1 , a 2 , , a n 
Tìm giá trị lớn nhất của một dãy số nguyên 
* Thuật toán liệt kê 
Bước 1. Nhập số nguyên dương n và dãy số nguyên a 1 , a 2 , , a n 
Bước 2. Max  a 1 ; i  2; 
Tìm giá trị lớn nhất của một dãy số nguyên 
* Thuật toán liệt kê 
467 g 
Bước 1. Nhập số nguyên dương n và dãy số nguyên a 1 , a 2 , , a n 
Bước 2. Max  a 1 ; i  2; 
Bước 3. Nếu i > n thì thông báo giá trị lớn nhất (Max) rồi kết thúc 
Tìm giá trị lớn nhất của một dãy số nguyên 
* Thuật toán liệt kê 
467 g 
Bước 1. Nhập số nguyên dương n và dãy số nguyên a 1 , a 2 , , a n 
Bước 2. Max  a 1 ; i  2; 
Bước 3. Nếu i > n thì thông báo giá trị lớn nhất (Max) rồi kết thúc 
Bước 4. Nếu a i > Max thì Max  a i 
Tìm giá trị lớn nhất của một dãy số nguyên 
* Thuật toán liệt kê 
635 g 
Bước 1. Nhập số nguyên dương n và dãy số nguyên a 1 , a 2 , , a n 
Bước 2. Max  a 1 ; i  2; 
Bước 3. Nếu i > n thì thông báo giá trị lớn nhất (Max) rồi kết thúc 
Bước 4. Nếu a i > Max thì Max  a i 
Bước 5. i  i + 1 rồi quay lại bước 3 
Tìm giá trị lớn nhất của một dãy số nguyên 
* Thuật toán liệt kê 
 0 g 
Chính xác! Nháy chuột để tiếp tục 
Sai rồi! Hãy thử lạn nhé! 
Đồng ý 
Làm lại 
a i < Max 
a i = Max 
a i ≠ Max 
a i > Max 
 Giá trị của Max sẽ thay đổi nếu số hạng thứ i (a i ) với Max như thế nào? 
CÂU HỎI 
A) 
B) 
C) 
D) 
Các khối dùng để mô tả thuật toán 
Nhập / xuất dữ liệu 
Tính toán 
So sánh 
Trình tự thực hiện của thuật toán 
Bước 1. Nhập số nguyên dương n và dãy số nguyên a 1 , a 2 , , a n 
Bước 2. Max  a 1 ; i  2; 
Bước 3. Nếu i > n thì thông báo giá trị lớn nhất (Max) rồi kết thúc 
Bước 4. Nếu a i > Max thì Max  a i 
Bước 5. i  i + 1 rồi quay lại bước 3 
Tìm giá trị lớn nhất của một dãy số nguyên 
Nhập số nguyên dương n và dãy số nguyên a 1 , a 2 , , a n 
Max  a 1 ; i  2 
i  i + 1 
i > n ? 
thông báo giá trị lớn nhất (Max) rồi kết thúc 
Đ 
a i > Max ? 
Max  a i 
Đ 
S 
S 
* Thuật toán sơ đồ khối 
Tìm giá trị lớn nhất của một dãy số nguyên 
* Thực hiện thuật toán với dãy số nguyên cụ thể 
Các tính chất của thuật toán 
- Tính dừng 
- Tính xác định 
- Tính đúng đắn 
Chính xác! Nháy chuột để tiếp tục 
Gần đúng rồi! Hãy thử lại thêm 1 lần nữa nhé! 
Đồng ý 
Làm lại 
23 
77 
53 
92 
 Cho dãy A gồm 8 số nguyên: 23 62 77 61 53 82 92 73 
 Sau khi giá trị i tăng đến 5 đồng thời thuật toán vừa thực hiện xong bước 4 ( Nếu a i > Max thì Max  a i ), thì lúc này giá trị của Max là bao nhiêu? 
CÂU HỎI 
A) 
B) 
C) 
D) 
Củng cố kiến thức đã học 
BÀI TOÁN VÀ THUẬT TOÁN 
BÀI TOÁN 
THUẬT TOÁN 
Khái niệm bài toán 
Các thành phần 
Input 
Output 
Liệt kê 
Sơ đồ khối 
Khái niệm thuật toán 
Mô tả thuật toán 
TÀI LIỆU THAM KHẢO 
 - Sách giáo khoa Tin học 10 
 - Chuẩn kiến thức kỹ năng Tin học 
 - Hình ảnh và phim về phần mềm mô phỏng thuật toán (của cùng tác giả) 
 - Âm thanh nhạc nền Music Box Dancer (của Richard Clayderman)