GV: Đặng Bá
Sáu
1
CHƯƠNG TRÌNH TIN HỌC LỚP 10
Chương I
Bài 4. BÀI TOÁN và
THUẬT TOÁN
GV: Đặng Bá Sáu 2
•
Xét các yêu c u sau :ầ
1. Gi i ph ng trình b c hai axả ươ ậ
2
+bx+c=0
2. Vi t m t dòng ch ra màn hình máy tính.ế ộ ữ
3. Qu n lý các cán b trong m t c quan.ả ộ ộ ơ
4. Tìm c chung l n nh t c a hai s nguyên ướ ớ ấ ủ ố
d ng a và b.ươ
5. X p lo i h c t p các h c sinh trong l p.ế ạ ọ ậ ọ ớ
I. BÀI TOÁN
I. BÀI TOÁN
Trong TIN HỌCTrong 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
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?
GV: Đặng Bá Sáu 3
Khái niệm
Khái niệm
bài toán

bài toán
trong
trong
Tin học?
Tin học?
Bài toán là vi c nào ó ta mu n ệ đ ố
máy tính th c hi n.ự ệ
GV: Đặng Bá Sáu 4
TIN HỌC
Đưa vào máy
thông tin gì
Cần lấy ra
thông tin gì
TOÁN HỌC?
TOÁN HỌC?
Các yếu tố cần quan tâm khi
Các yếu tố cần quan tâm khi
giải một bài toán
giải một bài toán
 Trong Tin h c, phát bi u m t bài toán, ta c n ọ để ể ộ ầ
trình bày rõ Input và Output c a bài toán ó.ủ đ
TOÁN HỌC
-
Giả thiết
-
Kết luận
THUẬT NGỮ
Input

Output

GV: Đặng Bá
Sáu
5
CÁC VÍ DỤ
VD1 : Giải phương trình bậc hai
ax
2
+ bx + c = 0 (a ≠ 0).

Input : Các số thực a,b,c (a ≠ 0)

Output : Số thực x thỏa : ax
2
+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ố.
GV: Đặng Bá
Sáu
6
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 :
UCLN của a và b.
Hai số nguyên dương a và b.
CÁC VÍ DỤ (tt)
?
?
?
?
Bảng điểm của học sinh.
Bảng xếp loại học tập.
GV: Đ ng Bá Sáu ặ 7
Nêu m t bài toán và ộ
ch rõ Input, Output ỉ
c a bài toán đó?ủ
Xem thêm các ví dụ trong SGK/24, 25
GV: Đặng Bá Sáu
8
TÓM LẠI
Một bài toán được cấu tạo bởi 2 thành phần cơ bản :

Input (Các thông tin đã có)

Output (Các thông tin cần tìm từ Input)
GV: Đặng Bá Sáu 9
II. THUẬT TOÁN
II. THUẬT TOÁN

Hướng dẫn các thao tác cho máy
thực hiện để tìm ra lời giải
Bài toán
Input Output
Bằng cách nào?
Giải bài toán
Thuật toán
GV: Đặng Bá Sáu 10
Input Output
THUẬT TOÁN
(Thao tác 1Thao tác 2 Thao tác n)
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
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ác thao tác được sắp xếp theo một
trình tự xác định.
•
Sau khi thực hiện dãy thao tác đó, từ
Input ta tìm được Output của bài toán.
GV: Đặng Bá Sáu 11
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
GV: Đặng Bá
Sáu
12
Giải toán thông thường:

Nếu a = 0 thì ( ) không
phải là pt bậc nhất.
+ Neáu b = 0 thì () voâ
s nghieäm.ố
+ Neáu b ≠ 0 thì ( ) voâ
nghieäm.

Nếu a ≠ 0 thì ( ) có
nghiệm x = -b/a.
a) LIỆT KÊ
LIỆT KÊ :
•
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.
VD : Tìm nghiệm phương trình bậc nhất tổng
quát : ax + b = 0 ()
GV: Đặng Bá
Sáu
13
: 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 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
GV: ng Bỏ Sỏu 14
VD: Tỡm nghim phng trỡnh bc nht tng quỏt : ax + b = 0
Nhaọp a, b
a = 0
x = -b/a
Sai
ẹuựng
ẹửa ra x vaứ keỏt thuực

Bc 1 : Nhp a, b.


Bc 2 : Nu a = 0 thỡ
quay li bc 1, ngc
li thỡ qua bc 3.

Bc 3 : Gỏn cho x
giỏ tr -b/a, ri qua
bc 4.

Bc 4 : a ra kt
qu x v kt thỳc.
S KHI
LIT Kấ
GV: Đặng Bá Sáu 15
Ta c n di n t thu t toán b ng m t ầ ễ ả ậ ằ ộ
ngôn ng sao cho máy tính có th hi u và ữ ể ể
th c hi n c, ngôn ng ó g i là ự ệ đượ ữ đ ọ
ngôn ng l p trìnhữ ậ . K t qu di n t ế ả ễ ả
thu t toán nh v y g i là ậ ư ậ ọ ch ng trìnhươ .
LƯU Ý
GV: Đặng Bá Sáu 16
III. VÍ DỤ VỀ THUẬT TOÁN
III. VÍ DỤ VỀ THUẬT TOÁN
Bài toán 1 :
Cho dãy s g m N s sau (N = 5):ố ồ ố
11 6 20 4 8
Tìm giá tr NH NH T c a dãy s trên ?ị Ỏ Ấ ủ ố
GV: Đặng Bá Sáu 17
HƯỚNG DẪN:
-
Gọi Min là giá trò nhỏ nhất cần

tìm.
-
Gán Min bằng giá trò phần tử đầu
tiên của dãy.

-
Lần lượt so sánh Min với các
phần tử tiếp theo trong dãy. Tại
mỗi vò trí so sánh :
+ Nếu Min lớn hơn giá trò phần
tử cần so sánh trong dãy thì lấy giá
trò của phần tử đó gán lại cho Min.
- Khi so sánh đến phần tử cuối
cùng trong dãy số thì Min sẽ mang
giá trò nhỏ nhất của dãy.
Gán i = 2
11 6 20 4 8
Min
Min=11
Min=6
Min=4
Giá trò nhỏ nhất: 4
Biến i lưu trữ vị trí
tiếp theo mà Min sẽ
so sánh
+ Tăng i lên 1 đơn vị
GV: Đặng Bá Sáu 18
SƠ ĐỒ KHỐI :
SƠ ĐỒ KHỐI :
Nhập N và dãy a

1
,…, a
N
Min = a
1
, i = 2
i <=N
Min > a
i
Min = a
i
i = i+1
Đưa ra Min
rồi kết thúc
Sai
Đúng
Đúng
Sai
GV: Đặng Bá Sáu 19
LIỆT KÊ
LIỆT KÊ

Bước 1 : Nhập N và dãy a
1
,…, a
N
.

Bước 2 : Đặt Min= a
1

, i=2;

Bước 3 : Nếu i<=N thì thực hiện bước 4, nếu
không thì chuyển đến bước 5.

Bước 4 :
4.1. Nếu Min > a
i
thì đặt Max=a
i
.
4.2. Tăng i một đơn vò rồi quay về bước 3

Bước 5 : Đưa ra Min rồi kết thúc.
GV: Đặng Bá Sáu 20
Bài toán 2 :
Tìm giá tr L N NH T c a m t dãy s v i Input và ị Ớ Ấ ủ ộ ố ớ
Output nh sau:ư
•
Input : S nguyên d ng N và dãy N s ố ươ ố
a
1
, ,a
N
.
•
Output : Giá tr l n nh t (Max) c a dãy s .ị ớ ấ ủ ố
Mô t thu t toán gi i bài toán này theo c 2 cách ả ậ để ả ả
li t kêệ và dùng s kh iơ đồ ố .
4. VÍ DỤ VỀ THUẬT TOÁN (tt)

4. VÍ DỤ VỀ THUẬT TOÁN (tt)
GV: Đặng Bá Sáu 21
CÁC THUẬT NGỮ CHÍNH
CÁC THUẬT NGỮ CHÍNH


Là việc nào đó ta muốn
máy tính thực hiện
Các thông tin đã có
(các giả thiết)
Các thông tin cần tìm
từ Input (kết luận)
*Một dãy hữu hạn các thao tác.
*Các thao tác được sắp xếp theo
một trình tự xác định.
*Sau khi thực hiện dãy thao tác
đó, từ Input ta tìm được Output
của bài toán.
Dùng các biểu tượng qui
ước để thể hiện các thao
tác trong thuật toán
•
Bài toán
•
Input
•
Output
•
Thuật toán
•

Sơ đồ khối
BÀI TẬP VỀ
NHÀ
Bài 1, 3, 4, 5, 6
trang 27 – 28
(SGK)