133
CHNG III
GIAI QUYET BAỉI TOAN BAẩNG
MAY TNH
134
CHƯƠNG III
GIẢI QUYẾT BÀI TOÁN BẰNG MÁY
TÍNH
3.1 Kỹ thuật lập trình
3.2 Thuật toán và Thuật giải
3.3 Biểu diễn thuật toán
3.4 Các bước giải quyết bài toán trên
máy
135
3.1 Kyõ thuaät laäp trình
136
Khái quát
• Kỹ thuật xây dựng phần mềm chính là kỹ thuật
lập trình. Lập trình vừa là một kỹ thuật vừa là
một nghệ thuật.
• Lập trình (Programming) thực chất là điều
khiển - bằng một ngôn ngữ lập trình cụ thể -
cách xử lý thông tin trên máy theo yêu cầu của
bài toán đặt ra.
• Để lập trình, phải biết cách tổ chức dữ liệu
(nguyên liệu để máy xử lý) và cách thức xử lí dữ
liệu (thuật giải) để cho ra kết quả mong muốn.
137
PROGRAMMING
=
ALGORITHMS

có cấu trúc
141
3.2 Thuaọt toaựn
vaứ
Giaỷi thuaọt
142
KHAI NIEM THUAT TOAN
Là khái niệm cơ sở của Toán học và
Tin học
Thuật toán (Algorithm) là một hệ
thống chặt chẽ và rõ ràng các quy tắc
nhằm xác định một dãy các thao tác trên
nhng đối t-ợng, sao cho sau một số hu
hạn b-ớc thực hiện các thao tác ta đạt
đ-ợc mục tiêu định tr-ớc.
143
Ng-ời hoặc máy thực hiện
một thuật toán đ-ợc gọi là một
bộ xử lý.
Nh- vậy một bộ xử lý của
một thuật toán T nào đó là một
cơ chế có kh nng thực hiện
các thao tác trên các đối t-ợng
theo một trỡnh tự do T quy định.
144
Cùng một bài toán có thể có
nhiều thuật toán khác nhau.
Thuật toán đơn giaỷn, dễ
hiểu, có độ chính xác cao, đ-ợc
baỷo đaỷm về mặt toán học, dễ

-Tr-ờng hợp DELTA > 0 :tính hai nghiệm phân biệt:
X1, X2
thông báo nghiệm ; kết thúc thuật toán.
147
DELTA
DELTA
Thuật toán Hoocne tính giá trị của đa thức :
Cho P
n
(X)=A
n
X
n
+ A
n-1
X
n-1
+ +A
1
X
1
+A
0
Tính P
n
(c) ?
P
n
(c)=( ((A
n

X
n-1
+ +A
1
X
1
+A
0
Viết đa thức d-ới dạng :
P
n
(c)=( ((A
n
.c +A
n-1
).c + A
n-2
) ).c + A
0
Chỉ bao gồm các phép nhân, cộng liên tiếp
P
2
(c)=(A
2
.c +A
1
).c + A
0
P
3

nhất.
Trong cùng một điều kiện, hai bộ xử lý
khác nhau hoặc hai lần thao tác khác nhau
phi cho cùng một kết qu khi thực hiện cùng
một thuật toán.
Các ng-ời khác nhau cùng sử dụng một
thuật toán, sẽ hành động giống nhau cho dù
họ không hiểu gỡ về bn chất và ý nghĩa của
vấn đề.
TNH XAC ẹềNH
152
Thuật toán có hiệu lực nh- nhau đối với
các bài toán cùng loại, có cùng miền áp dụng
thuật toán.
Thuật toán Hooc-ne có tính hàng loạt trên
tập s thc R v bất kỡ đa thức đại số bậc nào.
Thuật toán Gii phng trỡnh bc 2 khụng
có tính hàng loạt nếu số liệu gán cho a, b,c nhập
từ bàn phím.
Chẳng hạn khi nhập a=0 hoặc a không
phi là số .
TNH HAỉNG LOAẽT
153
Thuật toán phi bao gồm nhng thao
tác mà máy có thể thực hiện đ-ợc.
Mỏy tớnh chỉ có thể thực hiện đ-ợc
nhng phép toán số học, các phép so sánh,
các phép logic, các phép nhập xuất thông tin
tiêu chuẩn.
Thuật toán Hooc-ne có tính kh thi.

CÁC TÍNH CHẤT TRÊN
157
CẤU TRÚC CƠ BẢN CỦA
THUẬT TOÁN