Bài toán và thuật toán

chào mừng các em đến với tiết học
Giáo viên thực hiện: Nguyễn Thị Diền
A. Mục đích, yêu cầu:
1. Về kiến thức:
- Học sinh biết được khái niệm bài toán, thuật toán.
- Học sinh biết cách chỉ ra được Input và Output của
mỗi bài toán đưa ra.
2. Về tư tưởng, tình cảm:
- Học sinh biểu bài và hứng thú với bài học.
- Học sinh ngày càng yêu thích môn học hơn.
B. Phương pháp, phương tiện.
1. Phương pháp:
Kết hợp phương pháp giảng dạy như thuyết trình, vấn đáp, sử dụng phương tiện trực quan, ...
2. Phương tiện:
- Vở ghi lý thuyết, sách giáo khoa, sách tham khảo.
- Máy tính, máy chiếu hoặc hình ảnh về thuật toán.
Bài Toán Và Thuật Toán
Bài Toán Và Thuật Toán
1. Khái niệm bài toán:
Xét các yêu cầu sau :
 Giải phương trình bậc hai ax2+bx+c=0.
 Viết một dòng chữ ra màn hình máy tính.
 Quản lý các cán bộ trong một cơ quan.
 Tìm ước chung lớn nhất của hai số nguyên dương a và b.
 Xếp loại học tập các học sinh trong lớp.
Trong TIN HỌC
Trong TOÁN HỌC
Yêu cầu 1 và 4 được xem là bài toán
Tất cả các yêu cầu trên đều được xem là bài toán
Bài giảng
Trong các yêu cầu trên, yêu cầu nào được xem như là một bài toán?
Khái niệm bài toán trong
Tin học?
Bài toán là việc nào đó ta muốn máy tính thực hiện.
Khi máy tính giải bài toán cần quan tâm đến 2 yếu tố:
Bài Toán Và Thuật Toán
CÁC VÍ DỤ
VD1 : Giải phương trình bậc hai
ax2 + bx + c = 0 (a ≠ 0).
Input : Các số thực a,b,c (a ≠ 0)
Output : Số thực x thỏa : ax2+bx+ c = 0

VD2 : Tìm giá trị nhỏ nhất của các số trong một dãy số.
Input : Các số trong dãy số.
Output : Giá trị nhỏ nhất trong dãy số.
VD3 : Tìm ước chung lớn nhất của hai số nguyên dương a và b.
Input :
Output:

VD4 : Xếp loại học tập các học sinh trong lớp.
Input :
Output :
ƯCLN của a và b.
Hai số nguyên dương a và b.
?
?
?
?
Bảng điểm của học sinh.
Bảng xếp loại học tập.
Bài Toán Và Thuật Toán
VD5: Quản lí điểm trong một kì thi bằng máy tính.
Yêu cầu : Hãy xác định thông tin đưa vào (Input)
và thông tin cần lấy ra (Output)
? Input: SBD, Họ và tên, Văn, Toán, Lí, Anh.
? Output: Tổng điểm, Kết quả thi của học sinh.
Bài Toán Và Thuật Toán
TÓM LẠI
Khi dùng máy tính giải bài toán, ta cần quan tâm đến 2 yếu tố cơ bản:

Input: Các thông tin đã có.
Output: Các thông tin cần tìm từ Input.
Bài Toán Và Thuật Toán
2. Khái niệm thuật toán:
Chương trình
Input
Output
Muốn máy tính đưa ra Output từ Input
Thuật toán
BÀI TOÁN
Muốn viết chương trình
?
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 đó, từ Input của bài toán này, ta nhận được Output cần tìm.
Bài Toán Và Thuật Toán
MÔ TẢ CÁC THAO TÁC TRONG THUẬT TOÁN
Có 2 cách mô tả
Liệt kê
Dùng sơ đồ khối
Nêu ra tuần tự các thao tác cần tiến hành
Dùng một số biểu tượng thể hiện các thao tác
Bài Toán Và Thuật Toán
a. Liệt kê.
Ví dụ: Thuật toán tìm số lớn nhất trong dãy
MAX
SỐ LỚN NHẤT TRONG DÃY SỐ LÀ
Input: Nhập số chữ số và các số
Output: Chữ số lớn nhất ?
Bước 2: Max = a1, I  2
Bước 3: Nếu I > N thì chuyển đến bước 6
Bước 4: Nếu ai> Max thì max ai
Bước 5: i i+1, quay lại bước 3
Bước 6 Thông báo giá trị max, kết thúc
Bước 1: Nhập số chữ số N và các số a1,a2,…,an
i2
2>5 (sai)
i  3
3>5 (sai)
i  4
4>5 (sai)
i  5
5>5 (sai)
i  6
6>5 (Đúng)
Chuyển KN
Chuyển SDK
Bài Toán Và Thuật Toán
: Thể hiện các thao tác so sánh.
b. Dùng sơ đồ khối
Trong sơ đồ khối, người ta dùng một số biểu tượng thể hiện các thao tác như:
: Thể hiện các phép tính toán.
: Quy định trình tự thực hiện các thao tác.
: Thể hiện các thao tác nhập, xuất dữ liệu.
Bài Toán Và Thuật Toán
Đ
S
Đ
S
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
Max
i
A
7
7
5
5
5
5
4
3
2
6
7
4
1
5
N=5 ; A [ 5 1 4 7 6 ]
Max ? 5 ; i ? 2
2 > 5 ?
1> 5 ?
i  2+1
3 > 5 ?
4> 5 ?
i 3+1
4 > 5 ?
7 > 5 ?
Max 7
4
i 4+1
5 > 5 ?
7 > 7 ?
i 5+1
6 > 5 ?
Số lớn nhất của dãy là 7
Mô phỏng
thuật toán
Với i = 2
Với i = 3
Với i = 4
Với i = 5
VD1: Tìm nghiệm phương trình bậc nhất tổng quát: ax + b = 0
Nhập a, b
a = 0
x ?-b/a
Đưa ra x và kết thúc
Bước 1: Nhập a, b.
Bước 2: Nếu a = 0 thì quay lại bước 1, ngược lại thì qua bước 3.
Bước 3: Gán cho x giá trị -b/a, rồi qua bước 4.
Bước 4: Đưa ra kết quả x và kết thúc.
SƠ ĐỒ KHỐI
LIỆT KÊ
Bài Toán Và Thuật Toán
B7: Kết thúc.
B1: Bắt đầu;
B2: Nhập a, b, c;
B3: Tính ? = b2 - 4ac;
B4: Nếu ? < 0 => PT vô nghiệm => B7;
B5: Nếu ? = 0
=> PT có nghiệm kép x = -b/2a => B7;
B6: Nếu ? > 0
=> PT có hai nghiệm x1, x2 = (-b ? ??)/2a => B7;
VD2: Thuật toán giải phương trình bậc hai (a ? 0).
Cách 1: Liệt kê các bước
Bài Toán Và Thuật Toán
đ
s
Cách 2: S¬ ®å thuËt to¸n gi¶i ph­¬ng tr×nh bËc hai
2
B1
B2
B3
B4
B5
B6
s
đ
B7
Bài Toán Và Thuật Toán
a,b,c= 1 3 5
D = 3*3 - 4*5 = - 11
-11 < 0
PT vô nghiệm
KT
BD
S
PT có 2 nghiệm
x1, x2 = (-b ??? )/2a
Đ
S
D = b*b - 4*a*c
nhËp vµo a,b,c
 < 0
Mô phỏng thuật toán giải phương trình bậc hai
Bộ TEST 1:
a,b,c= 1 2 1
D = 2*2 - 4*1*1 = 0
PT vô nghiệm
PT có nghiệm x=-b/2a
KT
BD
S
PT có 2 nghiệm
x1, x2 = (-b ??? )/2a
Đ
S
D = b*b - 4*a*c
nhËp vµo a,b,c
 < 0
Mô phỏng thuật toán giải phương trình bậc hai
Bộ TEST 2:
Đ
 = 0
PT có nghiệm kép x=-1
KT
BD
S
Đ
S
 < 0
Mô phỏng thuật toán giải phương trình bậc hai
Bộ TEST 3:
Đ
 = 0
PT có 2 nghiệm
x1, x2 = (-b ??? )/2a
PT có nghiệm x1 = 3
x2 = 2
PT có nghiệm x=-b/2a
PT vô nghiệm
D = 25 - 24 = 1
D = b*b - 4*a*c
a,b,c= 1 -5 6
nhËp vµo a,b,c
Thuật toán có các tính chất:
- 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 các thao tác.
- Tính xác định: Sau khi thực hiện một thao tác thì hoặc là thuật toán kết thúc hoặc là có đúng một 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.
Ví dụ: Với thuật toán tìm Max đã xét:
- Tính dừng: Vì giá trị của i mỗi lần tăng lên 1 nên sau N lần thì i > N, khi đó kết quả phép so sánh ở bước 3 xác định việc đưa ra giá trị Max rồi kết thúc.
- Tính xác định: Thứ tự thực hiện các bước của thuật toán được mặc định là tuần tự nên sau bước 1 là bước 2, sau bước 2 là bước 3. Kết quả các phép so sánh trong bước 3 và bước 4 đều xác định duy nhất bước tiếp theo cần thực hiện.
- Tính đúng đắn: Vì thuật toán so sánh Max với từng số hạng các dãy số và thực hiện Max  ai nếu ai > Max nên sau khi so sánh hết N số hạng của dãy thì Max là giá trị lớn nhất.
CỦNG CỐ
* Bài học hôm nay các em cần nắm những nội dung chính sau:
- Bài toán là việc mà con người muốn máy tính thực hiện.
- Muốn giải một bài toán trước tiên phải xác định được Input và
Output:
+ Input: Thông tin đưa vào máy.
+ Output: Thông tin muốn lấy từ máy.
- Thuật toán là một dãy hữu hạn các thao tác được sắp xếp tuần
tự mà khi thực hiện nó thì từ Input đưa vào ta sẽ lấy được
Output.
- Thuật toán có 2 dạng: Liệt kê và Sơ đồ khối
* Một số câu hỏi trắc nghiệm::
Câu 1: Khi sử dụng máy tính giải bài toán:
a. Ta chỉ cần xác định Input
b. Ta cần xác định: Input, Output
c. Ta chỉ cần xác định Output
d. Cả ba ý trên.
Câu 2: Input của bài toán giải phương trình bậc hai
ax2 + bx + c = 0 là:
a. x, a, b, c b. a, b, c
c. a, b d. x, a, c
* Bài tập về nhà:
- Ôn tập lại bài học hôm nay.
- Làm các bài tập trong SGK trang 44
- Chuẩn bị trước phần bài còn lại.