TRNG I HC S PHM HÀ NI
TRUNG TÂM GIÁO DC T XA
NGUYN V QUC HNG
NGUYN QUNH DIP MT S PHNG PHỄP C BN
TRONG THIT K GII THUT VÀ
ỄNH GIỄ  PHC TP THUT
TOÁN

HÀ NI ậ 2012
Chng 1. Dn nhp Nguyn V Quc Hng-Nguyn Qunh Dip
1 CHNG 1
DN NHP
1.1 Algorithm?
T algorithm đc đt ra t th k th 9 bi nhà toán hc Bat
(Iran) Abu Ja’fa Mohammed ibn Khowarizmi đc hiu đn gin là tp
các quy tc cha đng các phép tính toán đc thc hin bng tay hoc
máy móc, trong tài liu này ta luôn hiu là gii thut đc xây dng cho
máy tính.


981
2943_

1962
1962__

_2943
981___

__3924
1210554

1210554
Hình 1.1. Nhân 2 s nguyên ln
Ta nhn thy rng, hai gii thut này là tng đng, thuc loi
phân lp, mt gii thut th ba khác hn đc gi là nhân theo kiu Nga
đc trình bày nh sau:
981
1234
1234
490
2468

245
4936
4936
122
9872


đ dài bng nhau (s dng s 0 cho thêm vào đu), đ dài là mt ly tha
ca 2 (1, 2, 4, 6, 8, …).  nhân 0981 vi 1234 , đu tiên ta nhân tng
na ca ca các toán hng vi nhau: na bên trái ca toán hng nhân (09)
đc nhân vi ln lt na bên trái ca toán hng kia (12 và 34), ri tip
tc na bên phi ca nó cng đc nhân nh vy. Ta có 4 phép nhân, kt
qu đc sp xp và cng li xem Hình 1.3.
Toán hng nhân Trt Kt qu
i) 09 12 4 108
ii) 09 34 2 306
iii) 81 12 2 972
iv) 81 34 0 2754
1210554
Hình 1.3. Phép nhân kiu chia đ tr
Cng vi cách thc nh vy, chúng ta li áp dng đi vi các
phép nhân 09 x 12, 09 x 34, 81 x 12 và 81 x 34. Chng hn, phép nhân 09
x 12 đc thc hin nh sau:
Chng 1. Dn nhp Nguyn V Quc Hng-Nguyn Qunh Dip
4

Toán hng nhân Trt Kt qu
i) 0 1 2 0
ii) 0 2 1 0.
iii) 9 1 1 9.
iv) 9 2 0 18
108
Hình 1.4. Phép nhân kiu chia đ tr
Phép nhân đc tin hành nh vy đc gi là thc hin theo gii
thut chia đ tr (divide and conquer), đ nhân hai s nguyên ln ta đã
chia nh ra, cui cùng ch thc hin phép nhân hai s có mt ch s và
các phép cng.

2
là các câu lnh
* Câu lnh tuyn:
case
B1 : S1;
B2 : S2;

Bn : Sn
else
Sn+1
end case
Chng 1. Dn nhp Nguyn V Quc Hng-Nguyn Qunh Dip
6

* Câu lnh lp:
for <tên bin> := m to n do S
for <tên bin> := m downto n do S
While B do S
Repeat <các câu lnh> until B
Trong đó: S là câu lnh, B là biu thc logic, m và n (các giá tr đm
đc) là các giá tr khi đu và kt thúc.
* Vào, ra:
read (<danh sách bin>)
write (<danh sách bin>)
* M đu và Kt thúc chng trình:
begin end.
* Chng trình con hàm:
function <tên hàm> (<danh sách tham s>) :
kiu d liu;
<chng trình>