BAØI TOAÙN
VAØ
THUAÄT TOAÙN
•
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. KHÁI NiỆM BÀI TOÁN
I. KHÁI NiỆM 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?
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

Các thông tin đã
có
OUTPUT
Các thông tin cần
tìm từ Input
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ố.
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

Input Output
Bằng cách nào?
Giải bài toán
Thuật toán
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.
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


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
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ấ

Khởi tạo giá trị Min = 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ị Min, nếu Min>a
i
thì Min
nhận giá trị mới là a
i
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.

thì đặt Min  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.
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
Mô phỏng thuật toán Min
Mô phỏng thuật toán Min
Dãy

a) XÁC ĐỊNH BÀI TOÁN
a) XÁC ĐỊNH BÀI TOÁN
•
Input : Số nguyên dương N
Input : Số nguyên dương N
và dãy N số nguyên a
và dãy N số nguyên a
1
1
,….,a
,….,a
N
N
.
.
•
Output: Giá trị lớn nhất (Max)
Output: Giá trị lớn nhất (Max)
của dãy số
của dãy số
b) Ý TƯỞNG
b) Ý TƯỞNG
•
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á