Tài liệu giáo khoa chuyên Tin (tập 1)

Chia sẻ: nguyenpc2011

Bộ Giáo dục và đào tạo đã ban hành chương trình chuyên tin học cho các lớp chuyên 10, 11, 12. Dựa theo các chuyên đề chuyên sâu trong chương trình nói trên, các tác giã biên soạn bo sách chuyên tin hc, bao gôm các vân đề cơ bản nhât vê câu trúc dữ liệu, thuật toán và cài dặt chương trình.

Bạn đang xem 20 trang mẫu tài liệu này, vui lòng download file gốc để xem toàn bộ.

Nội dung Text: Tài liệu giáo khoa chuyên Tin (tập 1)

Hå sÜ ®µm (Chñ biªn)
®ç ®øc ®«ng – lª minh hoµng – nguyÔn thanh hïng




tµi liÖu gi¸o khoa

chuyªn tin
quyÓn 1




Nhµ xuÊt b¶n gi¸o dôc viÖt nam
C«ng ty Cæ phÇn dÞch vô xuÊt b¶n Gi¸o dôc H Néi - Nh xuÊt b¶n Gi¸o dôc ViÖt Nam
gi÷ quyÒn c«ng bè t¸c phÈm.
349-2009/CXB/43-644/GD M sè : 8I746H9


2
L I NÓI ð U
B Giáo d c và ðào t o ñã ban hành chương trình chuyên tin h c cho các
l p chuyên 10, 11, 12. D a theo các chuyên ñ chuyên sâu trong chương trình
nói trên, các tác gi biên so n b sách chuyên tin h c, bao g m các v n ñ cơ
b n nh t v c u trúc d li u, thu t toán và cài ñ t chương trình.
B sách g m ba quy n, quy n 1, 2 và 3. C u trúc m i quy n bao g m: ph n
lí thuy t, gi i thi u các khái ni m cơ b n, c n thi t tr c ti p, thư ng dùng nh t;
ph n áp d ng, trình bày các bài toán thư ng g p, cách gi i và cài ñ t chương
trình; cu i cùng là các bài t p. Các chuyên ñ trong b sách ñư c l a ch n mang
tính h th ng t cơ b n ñ n chuyên sâu.
V i tr i nghi m nhi u năm tham gia gi ng d y, b i dư ng h c sinh chuyên tin
h c c a các trư ng chuyên có truy n th ng và uy tín, các tác gi ñã l a ch n,
biên so n các n i dung cơ b n, thi t y u nh t mà mình ñã s d ng ñ d y h c
v i mong mu n b sách ph c v không ch cho giáo viên và h c sinh chuyên
PTTH mà c cho giáo viên, h c sinh chuyên tin h c THCS làm tài li u tham kh o
cho vi c d y và h c c a mình.
V i kinh nghi m nhi u năm tham gia b i dư ng h c sinh, sinh viên tham gia
các kì thi h c sinh gi i Qu c gia, Qu c t H i thi Tin h c tr Toàn qu c,
Olympiad Sinh viên Tin h c Toàn qu c, Kì thi l p trình viên Qu c t khu v c
ðông Nam Á, các tác gi ñã l a ch n gi i thi u các bài t p, l i gi i có ñ nh
hư ng ph c v cho không ch h c sinh mà c sinh viên làm tài li u tham kh o
khi tham gia các kì thi trên.
L n ñ u t p sách ñư c biên so n, th i gian và trình ñ có h n ch nên ch c
ch n còn nhi u thi u sót, các tác gi mong nh n ñư c ý ki n ñóng góp c a b n
ñ c, các ñ ng nghi p, sinh viên và h c sinh ñ b sách ñư c ngày càng hoàn
thi n hơn .
Các tác gi




3
4
Chuyên ñ 1

THU T TOÁN
VÀ PHÂN TÍCH THU T TOÁN

1. Thu t toán
Thu t toán là m t trong nh ng khái ni m quan tr ng nh t trong tin h c. Thu t ng
thu t toán xu t phát t nhà khoa h c Ar p Abu Ja'far Mohammed ibn Musa al
Khowarizmi. Ta có th hi u thu t toán là dãy h u h n các bư c, m i bư c mô t
chính xác các phép toán ho c hành ñ ng c n th c hi n, ñ gi i quy t m t v n ñ .
ð hi u ñ y ñ ý nghĩa c a khái ni m thu t toán chúng ta xem xét 5 ñ c trưng sau
c a thu t toán:
• ð u vào (Input): Thu t toán nh n d li u vào t m t t p nào ñó.
• ð u ra (Output): V i m i t p các d li u ñ u vào, thu t toán ñưa ra các
d li u tương ng v i l i gi i c a bài toán.
• Chính xác: Các bư c c a thu t toán ñư c mô t chính xác.
• H u h n: Thu t toán c n ph i ñưa ñư c ñ u ra sau m t s h u h n (có
th r t l n) bư c v i m i ñ u vào.
• ðơn tr : Các k t qu trung gian c a t ng bư c th c hi n thu t toán ñư c
xác ñ nh m t cách ñơn tr và ch ph thu c vào ñ u vào và các k t qu
c a các bư c trư c.
• T ng quát: Thu t toán có th áp d ng ñ gi i m i bài toán có d ng
ñã cho.
ð bi u di n thu t toán có th bi u di n b ng danh sách các bư c, các bư c ñư c
di n ñ t b ng ngôn ng thông thư ng và các kí hi u toán h c; ho c có th bi u
di n thu t toán b ng sơ ñ kh i. Tuy nhiên, ñ ñ m b o tính xác ñ nh c a thu t
toán, thu t toán c n ñư c vi t b ng các ngôn ng l p trình. M t chương trình là s
bi u di n c a m t thu t toán trong ngôn ng l p trình ñã ch n. Trong tài li u này,
chúng ta s d ng ngôn ng t a Pascal ñ trình bày các thu t toán. Nói là t a
Pascal, b i vì nhi u trư ng h p, ñ cho ng n g n, chúng ta không hoàn toàn tuân


5
theo quy ñ nh c a Pascal. Ngôn ng Pascal là ngôn ng ñơn gi n, khoa h c, ñư c
gi ng d y trong nhà trư ng ph thông.
2,
Ví d : Thu t toán ki m tra tính nguyên t c a m t s nguyên dương
vi t trên ngôn ng l p trình Pascal.
function is_prime(n):boolean;
begin
for k:=2 to n-1 do
if (n mod k=0) then exit(false);
exit(true);
end;


2. Phân tích thu t toán
2.1. Tính hi u qu c a thu t toán
Khi gi i m t bài toán, chúng ta c n ch n trong s các thu t toán m t thu t toán mà
chúng ta cho là “t t” nh t. V y d a trên cơ s nào ñ ñánh giá thu t toán này “t t”
hơn thu t toán kia? Thông thư ng ta d a trên hai ti u chu n sau:
1. Thu t toán ñơn gi n, d hi u, d cài ñ t (d vi t chương trình).
2. Thu t toán hi u qu : Chúng ta thư ng ñ c bi t quan tâm ñ n th i gian
th c hi n c a thu t toán (g i là ñ ph c t p tính toán), bên c nh ñó
chúng ta cũng quan tâm t i dung lư ng không gian nh c n thi t ñ lưu
gi các d li u vào, ra và các k t qu trung gian trong quá trình
tính toán.
Khi vi t chương trình ch ñ s d ng m t s ít l n thì tiêu chu n (1) là quan tr ng,
nhưng n u vi t chương trình ñ s d ng nhi u l n, cho nhi u ngư i s d ng thì
tiêu chu n (2) l i quan tr ng hơn. Trong trư ng h p này, dù thu t toán có th ph i
cài ñ t ph c t p, nhưng ta v n s l a ch n ñ nh n ñư c chương trình ch y nhanh
hơn, hi u qu hơn.

2.2. T i sao c n thu t toán có tính hi u qu ?
Kĩ thu t máy tính ti n b r t nhanh, ngày nay các máy tính l n có th ñ t t c ñ
tính toán hàng nghìn t phép tính trong m t giây. V y có c n ph i tìm thu t toán
hi u qu hay không? Chúng ta xem l i ví d bài toán ki m tra tính nguyên t c a
2.
m t s nguyên dương
function is_prime(n):boolean;
begin


6
for k:=2 to n-1 do
if (n mod k=0) then exit(false);
exit(true);
end;
2 phép
D dàng nh n th y r ng, n u là m t s nguyên t chúng ta ph i m t
. Gi s m t siêu máy tính có th tính ñư c trăm nghìn t 10
toán phép
trong m t giây, như v y ñ ki m tra m t s kho ng 25 ch s m t kho ng
~3170 năm. Trong khi ñó, n u ta có nh n xét vi c th t2
1 là không c n thi t mà ch c n th t 2 ñ n √ , ta có:
ñn
function is_prime(n):boolean;
begin
for k:=2 to trunc(sqrt(n)) do
if (n mod k=0) then exit(false);
exit(true);
end;
{hàm sqrt(n) là hàm tính √ , trunc(x) là hàm làm tròn x }

~0.03 giây!
Như v y ñ ki m tra m t s kho ng 25 ch s m t kho ng

2.3. ðánh giá th i gian th c hi n thu t toán
Có hai cách ti p c n ñ ñánh giá th i gian th c hi n c a m t thu t toán. Cách th
nh t b ng th c nghi m, chúng ta vi t chương trình và cho ch y chương trình v i
các d li u vào khác nhau trên m t máy tính. Cách th hai b ng phương pháp lí
thuy t, chúng ta coi th i gian th c hi n thu t toán như hàm s c a c d li u vào
(c c a d li u vào là m t tham s ñ c trưng cho d li u vào, nó có nh hư ng
quy t ñ nh ñ n th i gian th c hi n chương trình. Ví d ñ i v i bài toán ki m tra
s nguyên t thì c c a d li u vào là s c n ki m tra; hay v i bài toán s p x p
dãy s , c c a d li u vào là s ph n t c a dãy). Thông thư ng c c a d li u
vào là m t s nguyên dương , ta s d ng hàm s trong ñó là c c a d
li u vào ñ bi u di n th i th c hi n c a m t thu t toán.
Xét ví d bài toán ki m tra tính nguyên t c a m t s nguyên dương (c d li u
2 thì ch c n m t l n th chia 2 ñ k t lu n
vào là ), n u là m t s ch n
3 không chia h t cho 2 nhưng l i chia
không ph i là s nguyên t . N u
h t cho 3 thì c n 2 l n th (chia 2 và chia 3) ñ k t lu n không nguyên t . Còn
n u là m t s nguyên t thì thu t toán ph i th c hi n nhi u l n th nh t.


7
Trong tài li u này, chúng ta hi u hàm s là th i gian nhi u nh t c n thi t ñ
th c hi n thu t toán v i m i b d li u ñ u vào c .
S d ng kí hi u toán h c ô l n ñ mô t ñ l n c a hàm . Gi s là m t s
nguyên dương, và là hai hàm th c không âm. Ta vi t
n u và ch n u t n t i các h ng s dương và , sao cho ,v i
mi .
N u m t thu t toán có th i gian th c hi n chúng ta nói r ng
thu t toán có th i gian th c hi n c p .
2 , ta có 2 2 3 1
Ví d : Gi s v im i
Vy , trong trư ng h p này ta nói thu t toán có th i gian th c hi n
cp .

2.4. Các quy t c ñánh giá th i gian th c hi n thu t toán
ð ñánh giá th i gian th c hi n thu t toán ñư c trình bày b ng ngôn ng t a
Pascal, ta c n bi t cách ñánh giá th i gian th c hi n các câu l nh c a Pascal.
Trư c tiên, chúng ta hãy xem xét các câu l nh chính trong Pascal. Các câu l nh
trong Pascal ñư c ñ nh nghĩa ñ quy như sau:
1. Các phép gán, ñ c, vi t là các câu l nh (ñư c g i là l nh ñơn).
2. N u S1, S2, ..., Sm là câu l nh thì
Begin S1; S2; …; Sm; End;
là câu l nh (ñư c g i là l nh h p thành hay kh i l nh).
3. N u S1 và S2 là các câu l nh và E là bi u th c lôgic thì
If E then S1 else S2;
là câu l nh (ñư c g i là l nh r nhánh hay l nh If).
4. N u S là câu l nh và E là bi u th c lôgic thì
While E do S;
là câu l nh (ñư c g i là l nh l p ñi u ki n trư c hay l nh While).
5. N u S1, S2,…,Sm là các câu l nh và E là bi u th c lôgic thì
Repeat
S1; S2; …; Sm;
Until E;
là câu l nh (ñư c g i là l nh l p ñi u ki n sau hay l nh Repeat)



8
6. N u S là l nh, E1 và E2 là các bi u th c cùng m t ki u th t ñ m ñư c
thì
For i:=E1 to E2 do S;
là câu l nh (ñư c g i là l nh l p v i s l n xác ñ nh hay l nh For).
ð ñánh giá, chúng ta phân tích chương trình xu t phát t các l nh ñơn, r i ñánh
giá các l nh ph c t p hơn, cu i cùng ñánh giá ñư c th i gian th c hi n c a
chương trình, c th :
1
1. Th i gian th c hi n các l nh ñơn: gán, ñ c, vi t là
2. L nh h p thành: gi s th i gian th c hi n c a S1, S2,…,Sm tương ng là
, ,..., . Khi ñó th i gian th c hi n c a l nh h p
, ,…,
thành là: .
3. L nh If: gi s th i gian th c hi n c a S1, S2 tương ng là
, . Khi ñó th i gian th c hi n c a l nh If là:
, .
4. L nh l p While: gi s th i gian th c hi n l nh S (thân c a l nh While) là
và là s l n l p t i ña th c hi n l nh S. Khi ñó th i gian th c
hi n l nh While là .
5. L nh l p Repeat: gi s th i gian th c hi n kh i l nh
Begin S1; S2;…; Sm; End;
là và là s l n l p t i ña. Khi ñó th i gian th c hi n l nh
Repeat là .
6. L nh l p For: gi s th i gian th c hi n l nh S là và là s
l n l p t i ña. Khi ñó th i gian th c hi n l nh For là .

2.5. M t s ví d
Ví d 1: Phân tích th i gian th c hi n c a chương trình sau:
var i, j, n :longint;
s1, s2 :longint;
BEGIN
{1} readln(n);
{2} s1:=0;
{3} for i:=1 to n do
{4} s1:=s1 + i;
{5} s2:=0;


9
{6} for j:=1 to n do
{7} s2:=s2 + j*j;
{8} writeln('1+2+..+',n,'=',s1);
{9} writeln('1^2+2^2+..+',n,'^2=',s2);
END.
Th i gian th c hi n chương trình ph thu c vào s .
1.
Các l nh {1}, {2}, {4}, {5}, {7}, {8}, {9} có th i gian th c hi n là
L nh l p For {3} có s l n l p là , như v y l nh {3} có th i gian th c hi n là
. Tương t l nh l p For {6} cũng có th i gian th c hi n là .
V y th i gian th c hi n c a chương trình là:
max 1, 1, , 1, , 1, 1
Ví d 2: Phân tích th i gian th c hi n c a ño n chương trình sau:
{1} c:=0;
{2} for i:=1 to 2*n do
{3} c:=c+1;
{4} for i:=1 to n do
{5} for j:=1 to n do
{6} c:=c+1;
Th i gian th c hi n chương trình ph thu c vào s .
1.
Các l nh {1}, {3}, {6} có th i gian th c hi n là
L nh l p For {2} có s l n l p là 2 , như v y l nh {2} có th i gian th c hi n là
.
L nh l p For {5} có s l n l p là , như v y l nh {5} có th i gian th c hi n là
. L nh l p For {4} có s l n l p là , như v y l nh {4} có th i gian th c hi n
là .
V y th i gian th c hi n c a ño n chương trình trên là:
max 1, ,
Ví d 3: Phân tích th i gian th c hi n c a ño n chương trình sau:
{1} for i:=1 to n do
{2} for j:=1 to i do
{3} c:=c+1;
Th i gian th c hi n chương trình ph thu c vào s .
1.
Các l nh {3} có th i gian th c hi n là


10
Khi i = 1, j ch y t 1 ñ n 1 l nh l p For {2} l p 1 l n
Khi i = 2, j ch y t 1 ñ n 2 l nh l p For {2} l p 2 l n

Khi i = , j ch y t 1 ñ n l nh l p For {2} l p ln
Như v y l nh {3} ñư c l p: 1 2 .. l n, do ñó l nh {1} có th i
gian th c hi n là
V y th i gian th c hi n c a ño n chương trình trên là:

Bài t p
1.1. Phân tích th i gian th c hi n c a ño n chương trình sau:
for i:=1 to n do
if i mod 2=0 then c:=c+1;
1.2. Phân tích th i gian th c hi n c a ño n chương trình sau:
for i:=1 to n do
if i mod 2=0 then c1:=c1+1
else c2:=c2+1;
1.3. Phân tích th i gian th c hi n c a ño n chương trình sau:
for i:=1 to n do
if i mod 2=0 then
for j:=1 to n do c:=c+1
1.4. Phân tích th i gian th c hi n c a ño n chương trình sau:
a:=0;
b:=0;
c:=0;
for i:=1 to n do
begin
a:=a + 1;
b:=b + i;
c:=c + i*i;
end;
1.5. Phân tích th i gian th c hi n c a ño n chương trình sau:
i:=n;
d:=0;


11
while i>0 do
begin
i:=i-1;
d:=d + i;
end;
1.6. Phân tích th i gian th c hi n c a ño n chương trình sau:
i:=0;
d:=0;
repeat
i:=i+1;
if i mod 3=0 then d:=d + i;
until i>n;
1.7. Phân tích th i gian th c hi n c a ño n chương trình sau:
d:=0;
for i:=1 to n-1 do
for j:=i+1 to n do d:=d+1;
1.8. Phân tích th i gian th c hi n c a ño n chương trình sau:
d:=0;
for i:=1 to n-2 do
for j:=i+1 to n-1 do
for k:=j+1 to n do d:=d+1;
1.9. Phân tích th i gian th c hi n c a ño n chương trình sau:
d:=0;
while n>0 do
begin
n:=n div 2;
d:=d+1;
end;
1.10. Cho m t dãy s g m s nguyên dương, xác ñ nh xem có t n t i m t dãy
con liên ti p có t ng b ng hay không?
a) ðưa ra thu t toán có th i gian th c hi n .
b) ðưa ra thu t toán có th i gian th c hi n .
c) ðưa ra thu t toán có th i gian th c hi n .




12
Chuyên ñ 2

CÁC KI N TH C CƠ B N

1. H ñ m
H ñ m ñư c hi u là t p các kí hi u và quy t c s d ng t p các kí hi u ñó ñ bi u
1 , các kí hi u ñư c
di n và xác ñ nh giá tr các s . Trong h ñ m cơ s
dùng có các giá tr tương ng 0, 1, . . , 1. Gi s có bi u di n:
… 1 0, …
1 2 1 2

1 s các ch s bên trái, là s các ch s bên ph i d u phân chia
trong ñó
ph n nguyên và ph n phân c a s và các ph i tho mãn ñi u ki n
0 .
Khi ñó giá tr c a s ñư c tính theo công th c:
... ... 1
Chú ý: ð phân bi t s ñư c bi u di n h ñ m nào ngư i ta vi t cơ s làm ch
s dư i c a s ñó. Ví d : là bi u di n h ñm .

1.1. Các h ñ m thư ng dùng:
H th p phân (h cơ s 10) dùng 10 kí hi u 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
28,910 = 2 × 101 + 8 × 100 + 9 × 10-1
Ví d :
H nh phân (h cơ s 2) ch dùng hai kí hi u 0, 1
102= 1 × 21 + 0 × 20 = 210
Ví d :
101,12= 1 × 22 + 0 × 21 + 1 × 20 + 1 × 2-1 =5,5
H cơ s mư i sáu, còn g i là h hexa, s d ng các kí hi u 0, 1, 2, 3, 4, 5, 6, 7, 8,
9, A, B, C, D, E, F, trong ñó A, B, C, D, E, F có các giá tr tương ng 10, 11, 12,
13, 14, 15 trong h th p phân
Ví d : AF016 = 10 × 162 + 15 × 161 + 0 × 160 =280010




13
1.2. Chuy n ñ i bi u di n s h th p phân sang h ñ m cơ s khác
ð chuy n ñ i bi u di n m t s h th p phân sang h ñ m cơ s khác, trư c h t
ta tách ph n nguyên và ph n phân r i ti n hành chuy n ñ i t ng ph n, sau ñó
ghép l i.
Chuy n ñ i bi u di n ph n nguyên: T (1) ta l y ph n nguyên:
... đó 0 .
Do 0 0
nên khi chia cho thì ph n dư c a phép chia ñó là còn
1 s là: ...
1 2
1 1 . Tương t 1 là ph n dư c a
thương s
phép chia 1 cho . Quá trình ñư c l p cho ñ n khi nh n ñư c thương b ng 0.
Chuy n ñ i bi u di n ph n phân: T (1) ta l y ph n sau d u ph y:
... .
1 ...
Ta nh n th y 1 chính là phân nguyên c a k t qu phép nhân, còn ph n phân c a
k t qu là 2 ... . Quá trình ñư c l p cho ñ n khi
nh n ñ s ch s c n tìm.

2. S nguyên t
1 là s nguyên t n u có ñúng hai ư c s là 1 và .
M t s t nhiên
Ví d các s nguyên t : 2, 3, 5, 7, 11, 13, 17, 19, 23, …

2.1. Ki m tra tính nguyên t
1 có là s nguyên t không, ta ki m tra
a) ð ki m tra s nguyên dương
2 1) mà là ư c c a ( chia h t
xem có t n t i m t s nguyên
) thì không ph i là s nguyên t , ngư c l i là s nguyên t .
1 không ph i là s nguyên t , ta luôn có th tách
Nu
à2 1. Vì √ . Do ñó,
nên
1 là không c n thi t, mà ch c n ki m tra t 2
vi c ki m tra v i t 2 ñ n
ñ n√ .
function is_prime(n:longint):boolean;
var k :longint;
begin
if n=1 then exit(false);



14
for k:=2 to trunc(sqrt(n)) do
if (n mod k=0) then exit(false);
exit(true);
end;
Hàm is_prime(n) trên ti n hành ki m tra l n lư t t ng s nguyên trong ño n
[2, √ ], ñ c i ti n, c n gi m thi u s các s c n ki m tra. Ta có nh n xét, ñ ki m
1 có là s nguyên t không, ta ki m tra xem có t n
tra s nguyên dương
2 √ ) mà là ư c c a thì không ph i là s
t i m t s nguyên t
nguyên t , ngư c l i là s nguyên t . Thay vì ki m tra các s là nguyên t ta
s ch ki m tra các s có tính ch t gi ng v i tính ch t c a s nguyên t , có th
s d ng m t trong hai tính ch t ñơn gi n sau c a s nguyên t :
1) Tr s 2 và các s nguyên t là s l .
2) Tr s 2, s 3 các s nguyên t có d ng 6 1 (vì s có d ng 6 2 thì
chia h t cho 2, s có d ng 6 3 thì chia h t cho 3).
Hàm is_prime2(n) dư i ñây ki m tra tính nguyên t c a s b ng cách ki m
tra xem có chia h t cho s 2, s 3 và các s có d ng 6 1 trong ño n [5, √ ].
function is_prime2(n:longint):boolean;
var k,sqrt_n:longint;
begin
if (n=2)or(n=3) then exit(true);
if (n=1)or(n mod 2=0)or(n mod 3=0) then exit(false);
sqrt_n:=trunc(sqrt(n));
k:=-1;
repeat
inc(k,6);
if (n mod k=0)or(n mod (k+2)=0) then break;
until k>sqrt_n;
exit(k>sqrt_n);
end;
b) Phương pháp ki m tra s nguyên t theo xác su t
T ñ nh lí nh Fermat:
nu là s nguyên t và là s t nhiên thì
Ta có cách ki m tra tính nguyên t c a Fermat:


15
n u2 2 thì không là s nguyên t
n u2 2 thì nhi u kh năng là s nguyên t
Ví d :
2 9 512 9 8 2, do ñó s 9 không là s nguyên t .
2 3 8 3 2, do ñó nhi u kh năng 3 là s nguyên t , th c t 3 là s
nguyên t .
2 11 2048 11 2, do ñó nhi u kh năng 11 là s nguyên t , th c
t 11 là s nguyên t .

,
2.2. Li t kê các s nguyên t trong ño n
trong ño n 1,
Cách th nh t là th l n lư t các s , r i ki m tra tính nguyên
t ca .
procedure generate(N:longint);
var m :longint;
begin
for m:=2 to N do
if is_prime(m) then writeln(m);
end;
Cách này ñơn gi n nhưng ch y ch m, ñ c i ti n có th s d ng các tính ch t c a
s nguyên t ñ lo i b trư c nh ng s không ph i là s nguyên t và không c n
ki m tra các s này.
Cách th hai là s d ng sàng s nguyên t , như sàng Eratosthene, li t kê ñư c các
s nguyên t nhanh, tuy nhiên như c ñi m c a cách này là t n nhi u b nh . Cách
làm ñư c th c hi n như sau:
Trư c tiên xoá b s 1 ra kh i t p các s nguyên t . S ti p theo s 1 là s 2, là s
nguyên t , xoá t t c các b i c a 2 ra kh i b ng. S ñ u tiên không b xoá sau s 2
(s 3) là s nguyên t , xoá các b i c a 3... Gi i thu t ti p t c cho ñ n khi g p s
nguyên t l n hơn √ thì d ng l i. T t c các s chưa b xoá là s nguyên t .
{$M 1100000}
procedure Eratosthene(N:longint);
const MAX = 1000000;
var i,j :longint;
Prime :array [1..MAX] of byte;
begin



16
fillchar(Prime,sizeof(Prime),0);
for i:=2 to trunc(sqrt(N)) do
if Prime[i]=0 then
begin
j:=i*i;
while j0 do begin
a:=a mod b;
tmp:=a; a:=b; b:=tmp;
end;
exit(a);
end;

3.4. B i s chung nh nh t c a hai s
B i s chung nh nh t (BSCNN) c a hai s ñư c tính theo công th c:

,
, ,


4. Lí thuy t t p h p
4.1. Các phép toán trên t p h p
1. Ph n bù c a trong , kí hi u , là t p h p các ph n t c a không
thu c :
:
2. H p c a và , kí hi u , là t p h p các ph n t ho c thu c vào
ho c thu c vào :



18
:
3. Giao c a và , kí hi u , là t p h p các ph n t ñ ng th i thu c c

: à
\ , là t p h p các ph n t thu c t p
4. Hi u c a và , kí hi u là
nhưng không thu c .
\ : à

4.2. Các tính ch t c a phép toán trên t p h p
1. K t h p



2. Giao hoán



3. Phân b



4. ð i ng u




4.3. Tích ð -các c a các t p h p
Tích ð -các ghép hai t p h p:
|
, ,
Tích ð -các m r ng ghép nhi u t p h p:
|
… , ,…, , 1, 2, . . ,

4.4. Nguyên lí c ng
Nu và là hai t p h p r i nhau thì
| | || ||
Nguyên lí c ng m r ng cho nhi u t p h p ñôi m t r i nhau:


19
, ,…,
Nu là m t phân ho ch c a t p thì:
|| | | | | | |

4.5. Nguyên bù tr
Nu và không r i nhau thì
| | || || | |
Nguyên lí m r ng cho nhi u t p h p:
, ,…,
Gi s là các t p h u h n:
| |
… 1
trong ñó là t ng ph n t c a t t c các giao c a t pl yt t p ñã cho

4.6. Nguyên lí nhân
, ,…,
N u m i thành ph n c a b có th t k thành ph n có kh
1, 2, … , , thì s b s ñư c t o ra là tích s c a các kh năng
năng l a ch n
..
này
M t h qu tr c ti p c a nguyên lí nhân:
| … | | | | | … | |

4.7. Ch nh h p l p
, ,…,
Xét t p h u h n g m ph n t
M t ch nh h p l p ch p ca ph n t là m t b có th t g m ph n t c a ,
các ph n t có th l p l i. M t ch nh h p l p ch p ca có th xem như m t
ph n t c a tích ð cac . Theo nguyên lí nhân, s t t c các ch nh h p l p ch p
ca s là .



4.8. Ch nh h p không l p
M t ch nh h p không l p ch p ca ph n t là m t b có th t g m
thành ph n l y t ph n t c a t p ñã cho. Các thành ph n không ñư c l p l i.
ð xây d ng m t ch nh h p không l p, ta xây d ng d n t ng thành ph n ñ u tiên.
Thành ph n này có kh năng l a ch n. M i thành ph n ti p theo, s kh năng



20
l a ch n gi m ñi 1 so v i thành ph n ñ ng trư c, do ñó, theo nguyên lí nhân, s
1… 1.
ch nh h p không l p ch p ca s là
!
1… 1
!

4.9. Hoán v
M t hoán v c a ph n t là m t cách x p th t các ph n t ñó. M t hoán v c a
ph n t ñư c xem như m t trư ng h p riêng c a ch nh h p không l p khi
. Do ñó s hoán v c a ph n t là !

4.10. T h p
M t t h p ch p c a ph n t là m t b không k th t g m thành
ph n khác nhau l y t ph n t c a t p ñã cho.
1… 1 !
! ! !
M t s tính ch t
-
1
-
(v i0
- )


5. S Fibonacci
S Fibonacci ñư c xác ñ nh b i công th c sau:
0
1
2
M t s ph n t ñ u tiên c a dãy s Fibonacci:
0 1 2 3 4 5 6 …
0 1 1 2 3 5 8 …
S Fibonacci là ñáp án c a các bài toán:
a) Bài toán c v vi c sinh s n c a các c p th như sau:
- Các con th không bao gi ch t;



21
- Hai tháng sau khi ra ñ i, m i c p th m i s sinh ra m t c p th con (m t ñ c,
m t cái);
- Khi ñã sinh con r i thì c m i tháng ti p theo chúng l i sinh ñư c m t c p con
m i.
Gi s t ñ u tháng 1 có m t c p m i ra ñ i thì ñ n gi a tháng th n s có bao
nhiêu c p.
Ví d , n = 5, ta th y:
Gi a tháng th 1:
1 c p (c p ban ñ u)
Gi a tháng th 2:
1 c p c p (ban ñ u v n chưa ñ )
Gi a tháng th 3:
2 c p (c p ban ñ u ñ ra thêm 1
c p con)
Gi a tháng th 4:
3 c p (c p ban ñ u ti p t c ñ )
Gi a tháng th 5: 5 c p.
1 thanh DOMINO có kích thư c 2×1 ph kín b ng có
b) ð m s cách x p
kích thư c 2 1.
Ví d : Có t t c 8 cách khác nhau ñ x p các thanh DOMINO có kích thư c 2x1
6, 8.
ph kín b ng 2x5




Hàm tính s Fibonacci th b ng phương pháp l p s d ng công th c
2 và 0, 1.
vi
function Fibo(n : longint):longint;
var fi_1, fi_2, fi, i :longint;
begin



22
if n0 do begin



60
while Sk do begin
;
Sk:=Sk – {xk};
if (x1, x2,…,xk) là nghi m then ;
k:=k+1;
;
end;
k:=k-1; // quay lui
end;
end;
Trên th c t , thu t toán quay lui vét c n thư ng ñư c dùng b ng mô hình ñ quy
như sau:
procedure Backtrack(i);// xây d ng thành ph n th i
begin
;
for xi Si do begin
;
if (tìm th y nghi m) then
else Backtrack(i+1);
;
end;
end;
Khi áp d ng lư c ñ t ng quát c a thu t toán quay lui cho các bài toán c th , có
ba v n ñ quan tr ng c n làm:


, ,…, ,… .
- Tìm cách bi u di n nghi m c a bài toán dư i d ng m t dãy các ñ i
tư ng ñư c ch n d n t ng bư c
- Xác ñ nh t p các ng c viên ñư c ch n làm thành ph n th i c a
nghi m. Ch n cách thích h p ñ bi u di n .
- Tìm các ñi u ki n ñ m t vector ñã ch n là nghi m c a bài toán.

1.2. M t s ví d áp d ng
1.2.1. T h p
M t t h p ch p k c a n là m t t p con k ph n t c a t p n ph n t .
Ch ng h n t p {1,2,3,4} có các t h p ch p 2 là:
{1,2}, {1,3, {1,4, {2,3}, {2,4}, {3,4}


61
Vì trong t p h p các ph n t không phân bi t th t nên t p {1,2} cũng là t p
{2,1}, do ñó, ta coi chúng ch là m t t h p.
Bài toán: Hãy xác ñ nh t t c các t h p ch p k c a t p n ph n t . ð ñơn gi n ta
ch xét bài toán tìm các t h p c a t p các s nguyên t 1 ñ n n. ð i v i m t t p
h u h n b t kì, b ng cách ñánh s th t c a các ph n t , ta cũng ñưa ñư c v bài
toán ñ i v i t p các s nguyên t 1 ñ n n.
Nghi m c a bài toán tìm các t h p ch p k c a n ph n t ph i tho mãn các ñi u
ki n sau:
, ,…,
l y giá tr trong t p 1,2, …
- Là m t vector

v i m i giá tr i t 1 ñ n 1 (vì t p h p không
-
- Ràng bu c:
phân bi t th t ph n t nên ta s p x p các ph n t theo th t tăng
d n).

1ñn
Ta có: 1 , do ñó t p (t p các ng c viên ñư c ch n

1, ta thêm vào 0.
làm thành ph n th i) là t . ð ñi u này ñúng cho c
trư ng h p
Sau ñây là chương trình hoàn ch nh, chương trình s d ng mô hình ñ quy ñ sinh
t t c các t h p ch p c a .
program ToHop;
const MAX =20;
type vector =array[0..MAX]of longint;
var x :vector;
n,k :longint;
procedure GhiNghiem(x:vector);
var i :longint;
begin
for i:=1 to k do write(x[i],' ');
writeln;
end;
procedure ToHop(i:longint);
var j:longint;
begin
for j := x[i-1]+1 to n-k+i do begin
x[i] := j;
if i=k then GhiNghiem(x)
else ToHop(i+1);



62
end;
end;
BEGIN
write('Nhap n, k:'); readln(n,k);
x[0]:=0;
ToHop(1);
END.
Ví d v Input / Output c a chương trình:
n = 4, k=2 1. 1 2
2. 1 3
3. 1 4
4. 2 3
5. 2 4
6. 3 4
Theo công th c, s lư ng t h p ch p k=2 c a n=4 là:
1… 1 !
6
! ! !
1.2.2. Ch nh h p l p
Ch nh h p l p ch p k c a n là m t dãy k thành ph n, m i thành ph n là m t ph n
t c a t p n ph n t , có xét ñ n th t và không yêu c u các thành ph n khác
nhau.
M t ví d d th y nh t c a ch nh h p l p là các dãy nh phân. M t dãy nh phân
ñ dài m là m t ch nh h p l p ch p m c a t p 2 ph n t {0,1}. Các dãy nh phân
ñ dài 3:
000, 001, 010, 011, 100, 101, 110, 111.
Vì có xét th t nên dãy 101 và dãy 011 là 2 dãy khác nhau.
Như v y, bài toán xác ñ nh t t c các ch nh h p l p ch p k c a t p n ph n t yêu
c u tìm các nghi m như sau:
, ,…,
- Là m t vector
l y giá tr trong t p 1,2, …
-
- Không có ràng bu c nào gi a các thành ph n.




63
Chú ý là cũng như bài toán tìm t h p, ta ch xét ñ i v i t p n s nguyên t 1 ñ n
n. N u ph i tìm ch nh h p không ph i là t p các s nguyên t 1 ñ n n thì ta có th
ñánh s các ph n t c a t p ñó ñ ñưa v t p các s nguyên t 1 ñ n n.
{s d ng m t m ng x[1..n] ñ bi u di n ch nh h p l p.
Th t c ñ quy sau sinh t t c ch nh h p l p ch p k c a n}
procedure ChinhHopLap(i:longint);
var j:longint;
begin
for j := 1 to n do begin
x[i] := j;
if i=k then GhiNghiem(x)
else ChinhHopLap(i+1);
end;
end;
Ví d v Input/Output c a chương trình:
n = 2, k=3 1. 1 1 1
2. 1 1 2
3. 1 2 1
4. 1 2 2
5. 2 1 1
6. 2 1 2
7. 2 2 1
8. 2 2 2
Theo công th c, s lư ng ch nh h p l p ch p k=3 c a n=2 là:
2 8

1.2.3. Ch nh h p không l p
Khác v i ch nh h p l p là các thành ph n ñư c phép l p l i (t c là có th gi ng
nhau), ch nh h p không l p ch p k c a t p n (k n) ph n t cũng là m t dãy k
thành ph n l y t t p n ph n t có xét th t nhưng các thành ph n không ñư c
phép gi ng nhau.
Ví d : Có n ngư i, m t cách ch n ra k ngư i ñ x p thành m t hàng là m t ch nh
h p không l p ch p k c a n.
M t trư ng h p ñ c bi t c a ch nh h p không l p là hoán v . Hoán v c a m t t p
n ph n t là m t ch nh h p không l p ch p n c a n. Nói m t cách tr c quan thì


64
hoán v c a t p n ph n t là phép thay ñ i v trí c a các ph n t (do ñó m i g i là
hoán v ).
Nghi m c a bài toán tìm các ch nh h p không l p ch p k c a t p n s nguyên t 1
ñ n n là các vector tho mãn các ñi u ki n:
, ,…,
- có k thành ph n:
l y giá tr trong t p 1,2, …
-
- Ràng bu c: các giá tr ñôi m t khác nhau, t c là v im i .
Sau ñây là chương trình hoàn ch nh, chương trình s d ng mô hình ñ quy ñ sinh
t t c các ch nh h p không l p ch p c a ph n t .
program ChinhHopKhongLap;
const MAX =20;
type vector =array[0..MAX]of longint;
var x :vector;
:array[1..MAX]of longint; { m ng d ñ ki m
d
soát ràng bu c các giá tr ñôi m t khác nhau, v im i }
n,k :longint;
procedure GhiNghiem(x:vector);
var i :longint;
begin
for i:=1 to k do write(x[i],' ');
writeln;
end;
procedure ChinhHopKhongLap(i:longint);
var j:longint;
begin
for j := 1 to n do
if d[j]=0 then begin
x[i] := j;
d[j] := 1;
if i=k then GhiNghiem(x)
else ChinhHopKhongLap(i+1);
d[j] := 0;
end;
end;
BEGIN
write('Nhap n, k(k');
write(f,bestSolution[1]);
close(f);

75
end;
BEGIN
input;
init;
branchBound(2);
output;
END.
Chương trình trên là m t gi i pháp nhánh c n r t thô sơ gi i bài toán TSP, có th
có nhi u cách ñánh giá nhánh c n ch t hơn n a làm tăng hi u qu c a chương
trình.

2.3. Bài toán máy rút ti n t ñ ng ATM
Bài toán
20 t ti n có giá , ,…,
M t máy ATM hi n có . Hãy tìm cách tr ít
t nh t v i s ti n ñúng b ng .
D li u vào t file “ATM.INP” có d ng:

, ,…,
- Dòng ñ u là 2 s và
- Dòng th 2 g m s
K t qu ra file “ATM.OUT” có d ng: N u có th tr ti n ñúng b ng thì ñưa ra
s t ít nh t c n tr và ñưa ra cách tr , n u không ghi -1.
ATM.INP ATM.OUT
10 390 5
200 10 20 20 50 50 50 50 100 100 20 20 50 100 200
Gi i

, ,…,
Như ta ñã bi t, nghi m c a bài toán là m t dãy nh phân ñ dài , gi s ñã xây

, ,…,
d ng ñư c thành ph n , ñã tr ñư c và s d ng t . ð
ñánh giá ñư c các nghi m m r ng c a , ta nh n th y:
- Còn ph i tr
- Gi là giá cao nh t trong các t ti n còn l i (
,.., thì ít nh t c n s d ng thêm t n a.

Do ñó, n u mà l n hơn ho c b ng s t c a cách tr t t nh t hi n có
, ,…,
thì không c n m r ng các nghi m c a n a.




76
const MAX =20;
fi ='ATM.INP';
fo ='ATM.OUT';
type vector =array[1..MAX]of longint;
var t,tmax :array[1..MAX]of longint;
x,xbest :vector;
c,cbest :longint;
n,s,sum :longint;
procedure input;
var f :text;
i :longint;
begin
assign(f,fi); reset(f);
readln(f,n, s);
for i:=1 to n do read(f,t[i]);
close(f);
end;
procedure init;
var i :longint;
begin
tmax[n]:=t[n];
for i:=n-1 downto 1 do begin
tmax[i]:=tmax[i+1];
if tmax[i]Js[i].d then exit(false);
t:=t+Js[i].p;
end;
exit(true);
end;
procedure Greedy;
var i,j :longint;
Js2 :TArrJobs;
begin
for i:=1 to n-1 do
for j:=i+1 to n do
if jobs[i].p > jobs[j].p then
swap(jobs[i],jobs[j]);
fillchar(d,sizeof(d),0);
m:=0;
for i:=1 to n do begin
Js2:=Js;
Js2[m+1]:=jobs[i];
if check(Js2,m+1) then begin
m:=m+1;
Js:=Js2;
d[i]:=1;
end;
end;
//writeln(m);
for i:=1 to n do
if d[i]=0 then begin
m:=m+1;
Js[m]:=jobs[i];
end;
end;


87
procedure printResult;
var f :text;
i :longint;
begin
assign(f,fo); rewrite(f);
for i:=1 to n do write(f,Js[i].name,' ');
close(f);
end;
BEGIN
input;
Greedy;
printResult;
END.
Chú ý: Thu t toán tham ăn trình bày trên luôn cho phương án t i ưu.

4. Chia ñ tr (Divide and Conquer)
4.1. Phương pháp
Tư tư ng c a chi n lư c chia ñ tr như sau: Ngư i ta phân bài toán c n gi i thành
các bài toán con. Các bài toán con l i ñư c ti p t c phân thành các bài toán con
nh hơn, c th ti p t c cho t i khi ta nh n ñư c các bài toán con ho c ñã có thu t
gi i ho c là có th d ràng ñưa ra thu t gi i. Sau ñó ta tìm cách k t h p các
nghi m c a các bài toán con ñ nh n ñư c nghi m c a bài toán con l n hơn, ñ
cu i cùng nh n ñư c nghi m c a bài toán c n gi i. Thông thư ng các bài toán con
nh n ñư c trong quá trình phân chia là cùng d ng v i bài toán ban ñ u, ch có c
c a chúng là nh hơn.
Thu t toán chia ñ tr có th bi u di n b ng mô hình ñ quy như sau:
procedure DivideConquer(A,x); // tìm nghi m x c a bài toán A
begin
if (A ñ nh ) then Solve(A)
else begin
Phân A thành các bài toán con A1, A2, …, Am;
for i:=1 to m do DivideConquer(Ai, xi);
K t h p các nghi m xi (i=1,2,..,m) c a các bài toán
con Ai ñ nh n ñư c nghi m c a bài toán A;
end;
end;



88
Trong th t c trên, Solve(A) là thu t gi i bài toán A trong trư ng h p A có c ñ
nh .
Trong thu t toán tìm ki m nh phân và thu t toán s p x p nhanh-QuickSort (
chuyên ñ s p x p) là hai thu t toán ñư c thi t k d a trên chi n lư c chia ñ tr .
Sau ñây, chúng ta s tìm hi u m t s ví d minh h a cho phương pháp chia ñ tr .

4.2. Bài toán tính
Bài toán: Cho s và s nguyên dương , tính
Cách 1: S d ng thu t toán l p, m t phép nhân ñ tính
procedure power(a,n:longint;var p:longint);
{giá tr an s ñư c lưu vào bi n p}
var i : longint;
begin
p:=1;
for i:=1 to n do p:=p*a;
end;
var a, n, p : longint;
BEGIN
write('Nhap a, n:'); readln(a, n);
power(a,n,p);
write(p);
END.
2)
Cách 2: Áp d ng kĩ thu t chia ñ tr , ta tính d a vào (trong ñó
như sau:
- n u ch n:
- n unl :
ð tính ta l i d a vào , quá trình chia nh cho ñ n khi nh n ñư c bài
toán tính thì d ng.
Ví d : tính 913
bài toán ñư c tính d a trên bài toán con 9 , ta có 9 9 9
bài toán 96 ñư c tính d a trên bài toán con 93, ta có 9 9 9
-

bài toán 93 ñư c tính d a trên bài toán con 91, ta có 9 9 9 9
-
-
Th t c ñ quy power(a,n,p) sau th hi n ý tư ng trên.
procedure power(a,n:longint; var p:longint);
var tmp : longint;


89
begin
if (n=1) then p:=a
else begin
power(a,n div 2,tmp);
if (n mod 2=1) then p:=tmp*tmp*a
else p:=tmp*tmp;
end;
end;
ho c vi t dư i d ng hàm như sau:
function power(a,n:longint):longint;
var tmp : longint;
begin
if (n=1) then exit(a)
else begin
tmp:=power(a,n div 2);
if (n mod 2=1) then exit(tmp*tmp*a)
else exit(tmp*tmp);
end;
end;
ð ñánh giá th i gian th c hi n thu t toán, ta tính s phép nhân ph i s d ng, g i
là s phép nhân th c hi n, ta có:
1 0
1 1 1
2
2 22 2
2 2
Như v y, thu t toán chia ñ tr m t không quá 2 phép nhân, nh hơn r t
nhi u so v i phép nhân.

4.3. Bài toán
1. . 1. .
ñ t giá tr l n nh t mà 1
Bài toán: Cho m ng s nguyên , c n tìm
.
Ví d : m ng g m 6 s 4, 2, 5, 8, 1, 7 thì ñ l ch c n tìm là: 6
, , ñ ph c t p
Cách 1: Th t t c các c p ch s
procedure find(var maxDiff:longint);
var i,j :longint;



90
begin
maxDiff:=0;
for i:=1 to n do
for j:=i to n do
if a[j]-a[i]>maxDiff then maxDiff:=a[j]-a[i];
end;
Cách 2: Áp d ng kĩ thu t chia ñ tr , ta chia m ng 1. .
1 . . và 1 . . trong ñó 2, ta có:
thành hai m ng con

1. .
1 ..
1. .
1 .. 1. .

c a hai m ng con 1. . và 1 . . , ta s d ràng xác ñ nh ñư c giá tr
N u tìm ñư c ñ l ch , giá tr l n nh t và giá tr nh nh t

1. . ). ð tìm ñ l ch, giá tr l n nh t và giá tr nh nh t c a hai m ng
con 1. . và 1 . . , ta l i ti p t c chia ñôi chúng. Quá trình phân nh
bài toán d ng l i khi ta nh n ñư c bài toán m ng con ch có 1 ph n t . T phương
pháp ñã trình bày trên, ta xây d ng th t c ñ quy
find2(l,r,maxDiff,maxValue,minValue)
..
tìm giá tr ñ l ch, giá tr l n nh t, giá tr nh nh t trên m ng vi
1 .
const MAXN
=100000;
fi ='';
fo ='';
var a :array[1..MAXN]of longint;
n :longint;
maxdiff
:longint;
tmp1,tmp2
:longint;
procedure find2(l,r:longint;var
maxDiff,maxValue,minValue :longint);
var mid :longint;
maxD1, maxV1, minV1 :longint;
maxD2, maxV2, minV2 :longint;
begin
if l=r then begin
maxDiff:=0;
maxValue:=a[r];


91
minValue:=a[r];
end
else begin
mid:=(l+r) div 2;
find2(l, mid, maxD1, maxV1,minV1);
find2(mid+1, r, maxD2, maxV2, minV2);
maxDiff:=maxV2 - minV1;
if maxDiff < maxD1 then maxDiff := maxD1;
if maxDiff < maxD2 then maxDiff := maxD2;
if maxV1 > maxV2 then
maxValue:=maxV1 else maxValue:=maxV2;
if minV1 < minV2 then
minValue:=minV1 else minValue:=minV2;
end;
end;
procedure input;
var f :text;
i :longint;
begin
assign(f,fi); reset(f);
readln(f,n);
for i:=1 to n do read(f,a[i]);
close(f);
end;
BEGIN
input;
find2(1,n,maxDiff,tmp1,tmp2);
writeln(maxDiff);
END.
1. .
Gi là s phép toán c n th c hi n trên m ng ph n t , ta có:
0 1
1
2 2
2 , b ng phương pháp th ta có:
Gi s ,
2 2 2 22 2
2 2 2 2 2 2 2 1
2 1 2 2 2 1 1



92
ð ph c t p thu t toán là:

4.4. Lát n n
22 10 b khuy t m t ph n tư t i
Hãy lát n n nhà hình vuông c nh
góc trên ph i (khuy t ph n 2) b ng nh ng viên g ch hình thư c th t o b i 3 ô
vuông ñơn v .




N n nhà G ch hình thư c th M t cách lát n n
Gi i. Ta chia n n nhà thành 4 ph n (hình bên
ph i), m i ph n có hình d ng gi ng v i hình

v y, n u có th lát n n v i kích thư c 2 thì ta
ban ñ u nhưng có c nh gi m ñi m t n a. Như

hoàn toàn có th lát n n v i kích thư c 2 .
Th t c ñ quy cover(x,y,s,t) dư i ñây

1,2,3,4 có t a ñ trái trên là , .
s lát n n có kích thư c , b khuy t ph n

const MAXSIZE =1 shl 10;
var a :array[1..MAXSIZE,1..MAXSIZE]of longint;
count,k :longint;
procedure cover(x,y,s,t:longint);
begin
if s = 2 then begin
inc(count);
if t1 then a[x,y]:=count;
if t2 then a[x,y+1]:=count;
if t3 then a[x+1,y]:=count;
if t4 then a[x+1,y+1]:=count;
exit;


93
end;
if t=1 then begin
cover(x,y+s div 2,s div 2,3);
cover(x+s div 2,y,s div 2,2);
cover(x+s div 2,y+s div 2,s div 2,1);
cover(x+s div 4,y+s div 4,s div 2,1);
end;
if t=2 then begin
cover(x,y,s div 2,4);
cover(x+s div 2,y,s div 2,2);
cover(x+s div 2,y+s div 2,s div 2,1);
cover(x+s div 4,y+s div 4,s div 2,2);
end;
if t=3 then begin
cover(x,y,s div 2,4);
cover(x,y+s div 2,s div 2,3);
cover(x+s div 2,y+s div 2,s div 2,1);
cover(x+s div 4,y+s div 4,s div 2,3);
end;
if t=4 then begin
cover(x,y,s div 2,4);
cover(x+s div 2,y,s div 2,2);
cover(x,y+s div 2,s div 2,3);
cover(x+s div 4,y+s div 4,s div 2,4);
end;
end;
procedure output;
var i,j :longint;
f :text;
begin
assign(f,'cover.out'); rewrite(f);
for i:=1 to 1 shl k do
begin
for j:=1 to 1 shl k do write(f,a[i,j],' ');
writeln(f);
end;



94
close(f);
end;
BEGIN
write('k=');readln(k);
cover(1,1,1 shl k,2);
output;
END.
Ví d v Input / Output c a chương trình:
k=3 11330000
14430000
2 4 13 13 0 0 0 0
2 2 13 16 0 0 0 0
5 5 14 16 16 15 9 9
5 8 14 14 15 15 12 9
6 8 8 7 10 12 12 11
6 6 7 7 10 10 11 11

4.5. Tháp Hà N i
Cho 3 cái c c và ñĩa có kích thư c
khác nhau. Ban ñ u c ñĩa ñ u c c1
và ñư c x p theo th t ñĩa to dư i,
ñĩa nh trên. Hãy di chuy n c ñĩa t
c c 1 sang c c 3 theo quy t c sau:
- M t l n ch ñư c chuy n m t ñĩa
- Trong quá trình chuy n ñĩa, có th s
d ng c c 2 làm c c trung gian và m t
ñĩa ch ñư c ñ t lên m t ñĩa l n hơn.
Gi i
ð chuy n ñĩa t c c 1 sang c c 3 ta s th c hi n như sau:
1 ñĩa t c c 1 sang c c 2, s d ng c c 3 làm c c trung gian
- chuy n
- chuy n 1 ñĩa t c c 1 sang c c 3
1 ñĩa t c c 2 sang c c 3, s d ng c c 1 làm c c trung gian
- chuy n



95
procedure move(n :longint;src,dst,tmp:longint);
begin
if n = 1 then writeln('move ',src,' ',dst)
else begin
move(n-1,src,tmp,dst);
move(1,src,dst,tmp);
move(n-1,tmp,dst,src);
end;
end;

4.6. Bài toán s p x p m ng b ng thu t toán tr n (Merge Sort)
1. .
Bài toán: Cho m ng s nguyên , c n s p x p các ph n t c a m ng theo
th t tăng d n.
Gi i: Ta chia m ng 1. . thành hai m ng con 1. . và 1 . . trong
2. Gi s , hai m ng con 1. . và 1 . . ñã ñư c s p x p
tăng d n, ta s tr n hai m ng con ñ ñư c m ng 1. . cũng s p x p tăng d n.
ñó

ð s p x p hai m ng con 1. . và 1 . . ta l i ti p t c chia ñôi chúng.
.. v i 1
. ð s p x p c m ng 1. . , ta ch c n g i th t c này v i 1,
Th t c ñ quy MergeSort(i,j) s p x p tăng d n m ng con
.
procedure MergeSort(i,j:longint);
var k : longint;
begin
if (i a[i]) and (L[j] > L[jmax]) then jmax
:= j;
L[i] := L[jmax] + 1; {Lưu ñ dài dãy con tăng dài nh t b t ñ u t i ai}
T[i] := jmax; {Lưu v t: ph n t ñ ng li n sau ai trong dãy con tăng
dài nh t ñó là ajmax}
end;



101
Writeln('Length of result : ', L[0] - 2);{Chi u dài dãy con
tăng dài nh t}
i := T[0]; {B t ñ u truy v t tìm nghi m}
while i n + 1 do
begin
Writeln('a[', i, '] = ', a[i]);
i := T[i];
end;
end;
begin
Enter;
Optimize;
end.

5.4. Dãy con chung dài nh t
Cho hai s nguyên dương , 0 , 100 và hai dãy s nguyên: A1,
A2,..., AM và B1, B2,..., B N. Tìm m t dãy dài nh t C là dãy con chung dài nh t c a
hai dãy A và B, nh n ñư c t A b ng cách xoá ñi m t s s h ng và cũng nh n
ñư c t B b ng cách xoá ñi m t s s h ng.
D li u vào trong file LCS.INP có d ng:
+ Dòng th nh t ch a M s A1, A2,..., AM
+ Dòng th hai ch a N s B1, B2,..., B N.
D li u ra trong file LCS.OUT có d ng:
+ Dòng th nh t ghi s k là s s h ng c a dãy C.
+ Dòng th hai ch a k s là các s h ng c a dãy C.
Gi i
C n xây d ng m ng L[0..M, 0..N] v i ý nghĩa: L[i, j] là ñ dài c a dãy chung dài
nh t c a hai dãy A[0.. i] và B[0..j].
ðương nhiên n u m t dãy là r ng (s ph n t là 0) thì dãy con chung cũng là r ng
vì v y L[0, j] = 0 ∀j, j = 1.. N, L[i, 0] = 0 ∀i, i = 1.. M. V i M ≥ i > 0 và N ≥ j >
0 thì L[i, j] ñư c tính theo công th c truy h i sau:
L[i,j] = Max{L[i, j-1], L[i-1, j], L[i-1, j-1] + x}
(v i x = 0 n u A[i] ≠ B[j] , x=1 n u A[i]=B[j])




102
const fi = 'LCS.INP';
fo = 'LCS.OUT';
MaxMN = 100;
var f : text;
a,b : array[0..MaxMN] of longint;
l : array[0..MaxMN,0..MaxMN] of longint;
m,n : longint;
p : array[0..MaxMN] of longint;
count : longint;
procedure Enter;
var f : text;
begin
m := 0;
n := 0;
assign(f,fi);
reset(f);
while not eoln(f) do
begin
inc(m);
read(f,a[m]);
end;
readln(f);
while not eoln(f) do
begin
inc(n);
read(f,b[n]);
end;
close(f);
end;
function max(x,y : longint) : longint;
begin
if x>y then max := y
else max := y;
end;
procedure Optimize;
var i,j : longint;
begin
for i:=1 to m do l[i,0] := 0;
for j:=1 to n do l[0,j] := 0;
for i:=1 to m do
for j:=1 to n do
begin

103
if a[i]=b[j] then l[i,j] := l[i-1,j-1] + 1
else l[i,j] := max(l[i,j-1],l[i-1,j]);
end;
end;
procedure Trace;
var f : text;
i,j : longint;
begin
assign(f,fo);
rewrite(f);
writeln(f,l[m,n]);
i := m;
j := n;
fillchar(p,sizeof(p),0);
count:= 0;
while (i>0) and (j>0) do
begin
if a[i]=b[j] then
begin
inc(count);
p[count] := a[i];
dec(i);
dec(j);
end
else if l[i,j]=l[i,j-1] then dec(j)
else dec(i);
end;
for i:=count downto 1 do write(f,p[i],' ');
close(f);
end;
BEGIN
Enter;
Optimize;
Trace;
END.

5.5. Bài toán cái túi
Trong siêu th có n gói hàng (n ≤ 100), gói hàng th i có tr ng lư ng là Wi ≤ 100
và tr giá Vi ≤ 100. M t tên tr m ñ t nh p vào siêu th , s c c a tên tr m không th
mang ñư c tr ng lư ng vư t quá M ( M ≤ 100). H i tên tr m s l y ñi nh ng gói
hàng nào ñ ñư c t ng giá tr l n nh t.


104
Gi i
N u g i B[i, j] là giá tr l n nh t có th có b ng cách ch n trong các gói {1, 2, ...,
i} v i gi i h n tr ng lư ng j. Thì giá tr l n nh t khi ñư c ch n trong s n gói v i
gi i h n tr ng lư ng M chính là B[n, M].
1. Công th c tính B[i, j].
V i gi i h n tr ng lư ng j, vi c ch n t i ưu trong s các gói {1, 2, ...,i - 1, i} ñ
có giá tr l n nh t s có hai kh năng:
N u không ch n gói th i thì B[i, j] là giá tr l n nh t có th b ng cách ch n

trong s các gói {1, 2, ..., i - 1} v i gi i h n tr ng lư ng là j. T c là B[i, j] =
B[i - 1, j]
N u có ch n gói th i (t t nhiên ch xét t i trư ng h p này khi mà Wi ≤ j) thì

B[i, j] b ng giá tr gói th i là Vi c ng v i giá tr l n nh t có th có ñư c b ng
cách ch n trong s các gói {1, 2, ..., i - 1} v i gi i h n tr ng lư ng j - Wi. T c
là v m t giá tr thu ñư c: B[i, j] = Vi + B[i - 1, j - Wi]
Vì theo cách xây d ng B[i, j] là giá tr l n nh t có th nên nó s là max trong hai
giá tr thu ñư c trên.
2. Cơ s quy ho ch ñ ng:
D th y B[0, j] = giá tr l n nh t có th b ng cách ch n trong s 0 gói = 0.
3. Tính b ng phương án:
B ng phương án B g m n + 1 dòng, M + 1 c t, trư c tiên ñư c ñi n cơ s quy
ho ch ñ ng: Dòng 0 g m toàn s 0. S d ng công th c truy h i, dùng dòng 0 tính
dòng 1, dùng dòng 1 tính dòng 2, v.v... ñ n khi tính h t dòng n.
0 1 ... M
0 0 0 0 0
1
2
... ...
n




105
4. Truy v t:
Tính xong b ng phương án thì ta quan tâm ñ n b[n, M] ñó chính là giá tr l n nh t
thu ñư c khi ch n trong c n gói v i gi i h n tr ng lư ng M. N u b[n, M] = b[n -
1, M] thì t c là không ch n gói th n, ta truy ti p b[n - 1, M]. Còn n u b[n, M] ≠
b[n - 1, M] thì ta thông báo r ng phép ch n t i ưu có ch n gói th n và truy ti p
b[n - 1, M - Wn]. C ti p t c cho t i khi truy lên t i hàng 0 c a b ng phương án.
const
max = 100;
var
W, V : array[1..max] of longint;
B : array[0..max, 0..max] of longint;
n, M : longint;
procedure Enter;
var
i: longint;
begin
Write('n = '); Readln(n);
for i := 1 to n do
begin
Writeln('Pack ', i);
Write(' + Weight : '); Readln(W[i]);
Write(' + Value : '); Readln(V[i]);
end;
Write('M = '); Readln(M);
end;
procedure Optimize;
var
i, j: longint;
begin
FillChar(B[0], SizeOf(B[0]), 0);
for i := 1 to n do
for j := 0 to M do
begin
B[i, j] := B[i - 1, j];
if (j >= W[i]) and (B[i, j] < B[i-1,j-W[i]] + V[i])
then
B[i, j] := B[i - 1, j - W[i]] + V[i];
end;



106
end;
procedure Trace;
begin
Writeln('Max Value : ', B[n, M]);
Writeln('Selected Packs: ');
while n 0 do
begin
if B[n, M] B[n - 1, M] then
begin
Writeln('Pack ', n, ' W = ', W[n], ' Value = ', V[n]);
M := M - W[n];
end;
Dec(n);
end;
end;
BEGIN
Enter;
Optimize;
Trace;
END.


Bài t p
10 h c sinh (các tên ñôi m t khác nhau) và
4.1. Cho danh sách tên c a
m t s nguyên dương . Hãy li t kê t t c các cách ch n h c sinh
trong h c sinh.
Ví d :
D li u vào K t qu ra
4, 2, sách Có 6 cách ch n 2 h c sinh trong
danh
4 h c sinh:
tên h c sinh như sau:
1. An Binh
An
2. An Hong
Binh
3. An Minh
Hong
4. Binh Hong
Minh
5. Binh Minh
6. Hong Minh



107
10 là m t dãy …
0,1 , 1,2, . . , . Hãy li t kê t t c các dãy nh phân ñ dài
4.2. M t dãy nh phân ñ dài trong ñó


D li u vào K t qu ra
3 Có 8 dãy nh phân ñ dài 3
1. 000
2. 001
3. 010
4. 011
5. 100
6. 101
7. 110
8. 111
4.3. Cho xâu S (ñ dài không vư t quá 10) ch g m các kí t ñn (các kí
t trong xâu S ñôi m t khác nhau). Hãy li t kê t t c các hoán v khác nhau
c a xâu S.
D li u vào K t qu ra
S='XYZ' Có 6 hoán v khác nhau c a 'XYZ'
1. XYZ
2. XZY
3. YXZ
4. YZX
5. ZXY
6. ZYX
20 ,hãy li t kê t t c các xâu ñ dài
4.4. Cho s nguyên dương ch g m
2 kí t ho c mà không có 2 kí t nào ñ ng c nh nhau.
D li u vào K t qu ra
4 Có 8 xâu ñ dài 4
1. AAAA
2. AAAB
3. AABA
4. ABAA
5. ABAB



108
6. BAAA
7. BAAB
8. BABA
10 s nguyên , , … ,
1
4.5. Cho dãy s gm và m t s nguyên
dương ). Hãy ñưa ra m t cách chia dãy s thành nhóm mà
các nhóm có t ng b ng nhau.
D li u vào K t qu ra
N=5, S=3 nhóm 1: 4, 6
Dãy s a: nhóm 2: 1, 9
1, 4, 6, 9, 10 nhóm 3: 10
4.6. M t xâu X = x1x2..xM ñư c g i là xâu con c a xâu Y = y1y2..yN n u ta có th
nh n ñư c xâu X t xâu Y b ng cách xoá ñi m t s kí t , t c là t n t i m t
dãy các ch s :
1 , ,…,
ñ
2 5 7.
Ví d : X='adz' là xâu con c a xâu Y='baczdtz';
Nh p vào m t xâu S (ñ dài không quá 15, ch g m các kí t 'a' ñ n 'z'), hãy
li t kê t t c các xâu con khác nhau c a xâu S.
D li u vào K t qu ra
S='aba' Có 6 xâu con khác nhau c a 'aba'
1. a
2. b
3. aa
4. ab
5. ba
6. aba
10 , li t kê t t c các cách khác nhau ñ t
4.7. Cho s nguyên dương
d u ngo c m và d u ngo c ñóng ñúng ñ n?
D li u vào K t qu ra
3 Có 5 cách
, , , ,




109
10 s nguyên dương , , … , 10 . Tìm s nguyên
4.8. Cho
dương nh nh t sao cho không phân tích ñư c dư i d ng t ng c a m t
s các s (m i s s d ng không quá m t l n) thu c s trên.
D li u vào K t qu ra
n=4 13
Dãy s a:
1, 2, 3, 6
4.9. Cho xâu S (ñ dài không vư t quá 10) ch g m các kí t ñn (các kí
t trong xâu S không nh t thi t ph i khác nhau). Hãy li t kê t t c các hoán
v khác nhau c a xâu S.
D li u vào K t qu ra
S='ABA' Có 3 hoán v khác nhau c a 'ABA'
1. AAB
2. ABA
3. BAA
4.10. Bài toán mã ñi tu n
Cho bàn c ô, tìm cách di chuy n m t quân mã (mã di chuy n theo
lu t c vua) trên bàn c xu t phát t ô (1,1) ñi qua t t c các ô, m i ô qua
ñúng m t l n.
Ví d : N=5
1 24 13 18 7

14 19 8 23 12

9 2 25 6 17

20 15 4 11 22

3 10 21 16 5

4.11. S siêu nguyên t là s nguyên t mà khi b m t s tuỳ ý các ch s bên
ph i c a nó thì ph n còn l i v n t o thành m t s nguyên t .
Ví d : 2333 là m t s siêu nguyên t có 4 ch s vì 233, 23, 2 cũng là các
s nguyên t .



110
Cho s nguyên dương N (0< N
Đề thi vào lớp 10 môn Toán |  Đáp án đề thi tốt nghiệp |  Đề thi Đại học |  Đề thi thử đại học môn Hóa |  Mẫu đơn xin việc |  Bài tiểu luận mẫu |  Ôn thi cao học 2014 |  Nghiên cứu khoa học |  Lập kế hoạch kinh doanh |  Bảng cân đối kế toán |  Đề thi chứng chỉ Tin học |  Tư tưởng Hồ Chí Minh |  Đề thi chứng chỉ Tiếng anh
Theo dõi chúng tôi
Đồng bộ tài khoản