VIETBOOK
Trang 1

Olimpic lập trình
I.1. Các bài toán Olimpic

Trong Olimpic Tin học Mat-Xcơ-va, ngời ta ra cho học sinh phổ thông một số nhóm bài toán. Số
các bài toán dao động từ 5 đến 11 bài. Các bài toán luôn luôn có mức điểm khác nhau, xếp theo trật tự dễ
dần và khi tính điểm chỉ lấy 3 lời giải tốt nhất. Các thí sinh đợc báo trớc tất cả những điều này. Những bài
đầu tiên có thể là khá khó, còn những bài cuối cùng mang tính chất khích lệ. Kỳ thi kéo dài 4 giờ, lời giải có
thể viết trên bất kỳ ngôn ngữ nào. Trớc khi giải nhất thiết phải viết thuật giải bằng lời. Điều này làm cho
việc đọc chơng trình dễ dàng. Tính rõ ràng của thuật toán, việc tiết kiệm số các thao tác, tính ngắn gọn của
chơng trình đợc cho thêm điểm, còn việc lập trình sử dụng mảng thừa và có lỗi bị hạ thấp điểm.
Trong phát biểu các bài toán và trình bày thuật toán qui ớc dùng các ký hiệu sau đây: Các mảng A
1
,
A
2
, A
n
đợc ký hiệu là A[1:n] với A[i] là các phần tử của nó. Cũng nh vậy kí hiệu A[1:m,1:n] và A[i,j]
cho mảng hai chiều v.v
Số lợng các phần tử của mảng và chỉ số các phần tử của mảng là các số tự nhiên, còn lại là các số
thực ( nghĩa là số với dấu phẩy động), nếu không có ớc định nào khác.
Nếu ở đầu bài nói rằng Cho mảng A[1:n] thì học sinh cần viết chơng trình tự nhập số n, tạo mảng
n phần tử và nhập giá trị của các phần tử này. Nếu trong ngôn ngữ ( Ví dụ ngôn ngữ Pascal ) không có
mảng động, thì cần chấp nhận n<100 và lập mảng 100 phần tử, nhng chỉ nhập giá trị cho n phần tử cho
trớc. Cũng nh thế đối với mảng 2 chiều và nhiều chiều hơn. Tuy nhiên thí sinh đợc phép giả thiết phần
chơng trình đợc viết là một phần của chơng trình bao nó trong đó mảng đã đợc tạo lập và các phần tử
của mảng đã đợc nạp từ trớc. Nhng thí sinh cần nói rõ điều này. Tất cả các câu trả lời đều phải đợc đa
ra màn hình hoặc máy in. Một lần nữa cần nhấn mạnh rằng lời giải phải là chơng trình, không thể thay

Có thể viết số tự nhiên M cho trớc dới dạng tổng các bình phơng của hai số tự nhiên hay không ?
Hãy viết chơng trình giải bài toán này.
80.2.3 Các số khác nhau
Cho trớc mảng số A[1:m]. Tìm và in ra số các số khác nhau trong mảng này.
Ví dụ trong mảng 5,7,5 có hai số khác nhau ( 5 và 7 ).
80.3.1 Số có tổng các chữ số cho trớc
Viết chơng trình in ra tất cả các số ở hệ cơ số 10 có ba chữ số mà tổng các chữ số bằng một số tự
nhiên cho trớc.
80.3.2 M + 1 ở hệ nhị phân
Số nguyên không âm M đợc cho bởi mảng các chữ số nhị phân là a
0
, a
1
, a
2
, a
n-1
: M = a
n-
1
.2
n-1
+ + a
1
.2 + a
0
Trong đó a
i
bằng 0 hoặc 1 ( i = 0,1,2, n-1 ) Hãy viết mảng các chữ số nhị phân của M+1.
80.3.3 Cực đại của các cực tiểu :

VIETBOOK
Trang 3

Cho mảng số A[1:n] . Hãy tìm độ dài của dãy con lớn nhất gồm các phần tử liên tiếp toàn số không.
Olimpic 82

Các thí sinh đợc giao 6 bài toán theo trật tự dễ dần. Chỉ tính điểm 3 bài.
82.1 Hình chữ nhật .
Trên giấy kẻ ô khổ 100 x 100 ô, có vẽ một số hình chữ nhật. Mỗi hình chữ nhật đợc tạo từ các ô
nguyên vẹn, các hình khác nhau không chồng lên nhau và không tiếp xúc nhau.
( hình 1.2 )
Cho mảng kích thớc 100 x 100, trong đó phần tử A[i,j] = 1 nếu ô [i,j] thuộc một hình chữ nhật nào
đó, còn A[i,j] = 0 trong trờng hợp ngợc lại.
Hãy viết chơng trình tính và in ra số các hình chữ nhật.
82.2 Các phân số đợc sắp thứ tự
In theo trật tự tăng dần tất cả các phân số tối giản trong khoảng (0, 1) có các mẫu số không vợt quá
7.
82.3 Tổng theo tập con :
Cho trớc mảng số nguyên A[1: n] và số M . Tìm tập hợp các phần tử A[i
1
], A[i
2
], A[i
k
]
1<=i
1


CM Soft 70 NCT F2 Q10
CM Soft 70 NCT F2 Q10
VIETBOOK
Trang 4 Olimpic 83
Các thí sinh đợc giao 5 bài theo trật tự dễ dần. Chỉ có 3 bài đợc tính điểm.
83.1. Đảo bit :
Số nguyên m đợc viết trong hệ cơ số 2 theo trật tự ngợc lại. Số nhận đợc viết trong hệ thập phân,
đợc coi là giá trị của hàm B(m).
Hãy in giá trị B(m) với m=512,513,514, 1023.
Thí dụ, ba giá trị đầu tiên cần in là :
1; 513; 257;
83.2. Hình tam giác và điểm :
Cho trớc trong hệ toạ độ vuông góc các điểm (X
1
,Y
1
), (X
2
,Y
2
),(X
3
,Y
3
) là đỉnh của một tam giác và
X,Y là toạ độ của một điểm. Hãy xác định xem điểm đó có nằm trong tam giác hay không ( bỏ qua sai số

dụ, đối với phép hoán vị P = (5,9,1,8,2,6,4,7,3) của các số 1,2, ,9 thì bảng nghịch thế sẽ là T =
(2,3,6,4,0,2,2,1,0).
Hãy viết chơng trình sao cho theo bảng nghịch thế cho trớc phục hồi đợc hoán vị ban đầu.
84.2 Con đờng:
Cho trớc các số tự nhiên n>=2 và mảng các số thực A[1 : m,1: m,1: n-1]. Hãy tìm giá trị nhỏ nhất
của tổng [ R= A]i
1
,i
2
,1]+ A[i
2
,i
3
,2] + + A[i
n-1
,i
n
,i
n-1
] với các bộ số nguyên tố có thể có 1<= i
1
,
i
2
in<=m.


CM Soft 70 NCT F2 Q10
CM Soft 70 NCT F2 Q10
VIETBOOK

85.1 Dạng tổng :
In tất cả các cách viết số tự nhiên N dới dạng tổng các số tự nhiên. Việc đổi chỗ các số hạng không
đợc coi là một cách mới.
85.2. Các phần tử bằng nhau :
Cho trớc mảng số nguyên A[1:m, 1:n]. Mỗi dòng của mảng đợc xếp theo thứ tự tăng dần, nghĩa là
A[i,1] <= A[i,2] với tất cả các
i = 1,2,3, ,m.
Hãy tìm và in số có mặt ở tất cả các dòng và in ra " Không" nếu số nh vậy không có.
85.3. Số không thể tách đợc .
Cho trớc mảng số tự nhiên P[1:n]. Hãy tìm số tự nhiên nhỏ nhất không thể viết dới dạng tổng các
phần tử thuộc mảng P. Tổng có thể chỉ gồm một số hạng, nhng mỗi phần tử của mảng chỉ đợc tham gia
vào đó một lần.
85.4. Tứ diện.
Trên các mặt của hai tứ diện đều bằng nhau M và N có viết các số M
1
, M
2
, M
3
, M
4
và N
1
, N
2
, N
3
, N
4


- Nếu 5 số giống nhau, thì in số 1, nếu không
- Nếu có 4 số giống nhau, thì in số 2, nếu không
- Nếu có 3 số giống nhau và còn 2 số còn lại cũng giống nhau, thì in số 3, nếu không
- Nếu chỉ có 3 số giống nhau, thì in số 4, nếu không
- Nếu có 1 cặp số giống nhau thì in số 6, nếu không thì in số 7.
86.3. Cái trống.
Theo hình tròn viết 12 số a
1
, , a
12
. Nếu viết chúng từ số hiệu k, thì nhận đợc vec tơ x
k
= (a
k
,
a
k+1
, , a
k+11
)
Trong đó a
13
đợc hiểu là a
1
, a
14
đợc hiểu là a
2

Vec tơ x

87.1. Ba lô :
Từ n vật chọn ra các vật sao cho tổng khối lợng của chúng nhỏ hơn 30 kg, còn giá trị còn lại là lớn
nhất. In tổng giá trị của các vật thể đã đợc chọn.
Cụ thể là cho 2 mảng số dơng A[1:n] và B[1;n]. Chọn các chỉ số khác nhau đôi một i
1
,i
2
, i
k
sao
cho
A[i
1
] + A[i
2
] + + A[i
k
] <30
B[i
1
] + B[i
2
] + + B[i
k
] = m là lớn nhất.
Chỉ cần in giá trị m
Chú ý
: Có thể giả thiết rằng các vật thể đã đợc sắp xếp theo trật tự tăng dần hoặc giảm dần theo khối
lợng A[i], theo giá trị B[i], theo giá trị A[i]/B[i] hoặc một dấu hiệu bất kỳ nào khác.
87.2 Nửa bội.

].
Olimpic 88
Thí sinh đợc giao 5 bài theo trật tự dễ dần. Chỉ tính điểm 3 bài.


CM Soft 70 NCT F2 Q10
CM Soft 70 NCT F2 Q10
VIETBOOK
Trang 8

88.1. Lớn bên phải.
Cho trớc mảng số dơng A[1:n]. Đối với mọi phần tử A[i] hãy chọn trong số các phần tử về bên
phải A[i] và lớn hơn A[i] chỉ số nhỏ nhất j rồi thay giá trị A[i] bằng A[j].
Nếu không tìm đợc phần tử A[j] nh vậy thì thay thế A[i] bằng 0. In lại mảng đã nhận đợc.
Điều kiện bắt buộc
: số phép tính ở lời giải cần phải là O(n) chứ không phải là O(n
2
). Có thể sử dụng mảng
phụ.
Giải thích :

Ví dụ mảng 2,9,8,5,9,3,4,5,2, sai khi thay trở thành mảng 9,0,9,9,0,4,5,0,0.
88.2. Đa thức.
Tính các hệ số a[0], a[1], , a[n-1] của đa thức
P(x) = a[0] + a[1]*x + a[2]*x
2
+ + a[n-1]*x
n-1
+ x
n

Phần hai - Thuật toán
Trong phần này trình bày các thuật giải. Với một số bài thuật giải đợc trình bày có thể dễ dàng
chuyển sang chơng trình, với một số bài khác đó mới chỉ là ý tởng giải, có lúc là chú giải, giải thích
chơng trình. Nhng trong mọi trờng hợp chúng tôi cố gắng làm cho việc đọc chơng trình đợc dễ dàng,
trình bày phơng pháp lập trình đúng đợc ghi nhớ. Số lợng các phép toán của thuật giải chính xác đến
một bội hằng.
ôlimpic 80
80.1.1. Những số nguyên tố đến M :
Để tăng tốc độ tính toán ta nên dùng một mảng chứa những số nguyên tố thu đợc và kiểm tra xem
số đang xét chia hết của phần tử đã nạp trong bảng hay cha. Số chẵn hiển nhiên không phải xét. Bảng cần
có kích thớc tối đa là phần tử. Vì thế những bảng 1000 phần tử sẽ đủ để chứa những số nguyên tố đến
4.000.000.
80.1.2. Hoán vị :
Đặc trng của bài toán bài là ở chỗ, cần thu đợc tất cả các hoán vị. Điều này sẽ làm giảm đáng kể
số lợng thao tác so với bài toán chọn toàn bộ. Tuy nhiên thử tởng tợng là toàn bộ các hoán vị của các số
1,2,3, m đợc sắp xếp theo trật tự từ điển để tìm cách đa vào một hoán vị xây dựng các hoán vị tiếp
theo bằng cách, xuất phát từ hoán vị đầu tiên xây dựng các hoán vị tiếp theo. Cụ thể là với mỗi hoán vị P = (
p1,p2, ,pm ) của các số 1,2, ,m, chúng ta cũng làm phép đổi chỗ nh vậy (A(p1),A(p2), ,A(pm))
của những số A cho trớc.
Để xây dựng trực tiếp hoán vị tiếp theo hoán vị cho trớc P = ( p
1
, p
2
, ,p
m
) chúng ta duyệt các số
p
1
, p
2

,
q
2
, , q
m
) sẽ là hoán vị cần tìm đợc. Hình vẽ 1.4 Thật vậy, P < Q bởi vì (i-1) thành phần đầu tiên của
chúng trùng nhau và p
1
<q
1
( bởi vì theo cách chọn lựa của mình q
i
= p
j
>p
i
). Trong i thành phần đầu tiên
P là lớn nhất, còn Q nhỏ nhất, bởi vì trong P các thành phần giảm dần , còn Q - tăng dần. Cuối cùng nếu
hoán vị R nằm giữa P và Q, thì i -1 thành phần đầu tiên của nó trùng với các thành phần P và Q, còn
thành phần r
i
= p
1
hay q
i
, bởi vì trong i-1 thành phần đầu tiên đã chiếm chỗ không có những số nằm giữa p
i

và q
i

Trong chơng trình điều này đợc thực hiện nh sau : Ta dùng mảng P chứa các hoán vị hiện tại.
Trớc tiên lấp dần bởi hoán vị đầu tiên của chúng P=(1,2, ,m) và gắn hoán vị đồng nhất (a
1
, a
2
, ,a
m
) của
các thành phần của mảng A cho trớc. Giả sử hoán vị P nhận đợc và hoán vị đáp ứng nó A đợc in. Trong
phần tơng ứng của chơng trình sẽ tìm phần tử p
i
< p
i+1
với chỉ số lớn nhất i. Nếu không có i đó, thì hoán vị
P là cuối cùng. Nếu có i ta sẽ tìm chỉ số lớn nhất j > i mà p
i
< p
j
, rồi đổi chỗ pi và p
j
, sau đó dãy p
i+1
, p
i+2

80.1.3. Nâng luỹ thừa nhanh
Bình thờng để tính a
k
ngời ta đa vào biến số b, ban đầu gán b:=1 rồi thực hiện nhiều lần các
phép toán : k:=k-1;
B:=b*a .


CM Soft 70 NCT F2 Q10
CM Soft 70 NCT F2 Q10
VIETBOOK
Trang 11

Khi biến cố k trở thành 0 (điều này đòi hỏi k vòng) ta sẽ có b=a
k
ý tởng làm gọn cách tính là nh sau . Ban đầu ta đặt b=1.
Nếu k lẻ , ta thực hiện phép toán :
K:=k-1, b:=b*a
Nếu k chẵn, ta sử dụng đồng nhất thức :
Ak = ( a
2
)
k/2
để biến đổi :
k:=k/2 ; a := a*a
khi k = 0 , biến b sẽ chứa giá trị phải tìm
Để chứng minh ta lí hiệu giá trị cần tìm ak là w và đặt b=1, khi đó ak * b = w (*)
Nếu k lẻ, thì các phép thế : k = k-1 , b = b*a không phá vỡ dấu đẳng thức (*). Nếu k chẵn thì
các phép thế k = k/2, a = a*2 cũng không phá vỡ, nghĩa là b = w. Vậy b là giá trị cần tìm.
80.1.4. Các phép tính số học :

6
a
6
6 và w = B
6
Tiếp theo khi lựa chọn các khả năng, ta sẽ cho a6 biến thiên dần theo 1, 2, 3, 4 và v.v
Thuật toán này đợc thể hiện trong chơng trình 80.1.4. Chúng ta giải thích một số ý trong phơng
án BASIC nó ở ngôn ngữ Basic. Các biến m và n biểu thị cho các số 35 và 6. Những dòng đầu tiên của
chơng trình (đến dòng số 60) tốt nhất. Các dòng đó làm công việc khởi động để các toán tử bắt đầu từ dòng
số 60 và các toán tử dùng cho sự lựa chọn phơng án kế tiếp, khởi trị cho phơng án đầu tiên.
Chúng ta xem chơng trình từ dòng số 60. Số hạng đầu tiên a
i
đợc chọn từ dãy a
n
, a
n-1
, ,a
2
không
bằng 4. Nó tăng lên 1 còn tất cả những số hạng trớc nó đợc gán là 1. Bây giờ B
i
đợc tính theo B
i-1
và sau
đó tất cả các thành phần còn lại B
i+1
, B
i+2
, ,B
n

thử nghiệm không phải với các phần tử trớc đó mà với các phần tử sau nó, đến khi gặp sự trùng đầu tiên. Số
lần do đó sẽ giảm từ m*n đễn m*k, với m là số lợng các số, còn k là số các số khác nhau trong mảng cho
trớc. Chơng trình 80.2.3-2 thực hiện điều đó.
80.3.1. Tổng cho trớc các chữ số .
Tất nhiên là có thể dùng 3 vòng FOR lồng nhau :
FOR i:=0 to 9 do
FOR j:=0 to 9 do
FOR k:=1 to 9 do
If i+j+k = n then
WRITELN ( i+10*j + 100*k );
Tuy nhiên lời giải này là tồi vì nó chứa 900 vòng lặp trong khi đó chỉ cần 100 là đủ.
Lời giải tốt hơn chứa đựng vòng lặp kép theo i và j còn k tính theo tổng cho n: k=n-i-j.
Thêm vào sự kiểm tra 1<=k <=9, chúng ta thu đợc chơng trình 80.3.1.
Bạn đọc có thể hoàn thiện chơng trình bằng cách kiểm tra điều kiện n<=27 và còn có thể tăng tốc
độ tính trong trờng hợp n<18.
80.3.2. M+1 trong hệ nhị phân
Chúng ta duyệt các số a
0
, a
1
, thay thế 1 bằng 0 đến số 0 đầu tiên ta thay nó bằng 1 và khi đó
ngừng việc thay thể các số. Cần lu ý rằng lời giải có thể bao gồm n+1 số, chữ chứ không phải n nh trong
điều kiện của đầu bài .
80.3.3. MAX của các MIN
Chơng trình đợc lập sao cho tránh đợc sự xem xét riêng lẻ dòng đầu tiên và mỗi phần tử đầu tiên
của dòng. Ngoài ra, việc xử lý dòng đang xét sẽ dừng khi ta đã biết rằng dòng đó không thể chứa phần tử
cần kiếm.
80.3.4. Hoán vị của 0, 1, 2
Bài toán này không đòi hỏi sự hoán vị, chỉ cần đếm xem có bao nhiêu số 0, 1, 2 trong mảng và điền
vào mảng theo yêu cầu của đầu bài.

Chúng ta chia vòng xoáy ốc thành 4 phần : đoạn ngang từ phải sang trái và đoạn thẳng đứng từ trên
xuống, đoạn ngang từ phải sang trái và đoạn thẳng đứng từ dới lên trên. Trong chơng trình mỗi đoạn
đợc xử lý riêng và đợc nối kết với đoạn khác. Chơng trình kết thúc sau khi đã nạp phần tử cuối cùng k=
n*n
81.4. Các số lập từ các chữ số khác nhau
Chơng trình 81.4. khá rõ ràng
81.5. Chơng trình 81.5 đơn giản.
olimpic 82
82.1.Hình chữ nhật
Ta nhận thấy số lợng hình chữ nhật chính là số lợng các góc tây bắc tức là góc trái trên của
chúng. Chỉ cần không nhầm lẫn trong trờng hợp góc ở trên biên . Các chơng trình 82.1 và 82.1-2 khắc
phục khó khăn trên theo hai cách khác nhau. Lu ý bạn đọc nào muốn làm rút gọn chơng trình 82.1, bằng
việc sử dụng biểu thức ( i > 1 and A[i-1,j] = 0). Biểu thức có chứa lỗi cú pháp khi i = 1 nếu chỉ số bắt đầu
từ 1.
82.2. Sắp xếp phân số
Chơng trình không dùng mảng phụ và không đòi hỏi sự kiểm tra tính tối giản của phân số. Để làm
việc này ta xét phân số m/n và đặt ban đầu m=0, n=1. Chúng ta in m/n, sau đó trong số tất cả các phân số
a/b, lớn hơn m/n và b<=p ( với điều kiện p = 7 ). Chúng ta chọn phân nhỏ nhất. Nếu có i/j <1 thì thay thế
phân số m/n bởi phân số i/j và tiếp tục quá trình này v.v
Chúng ta chỉ ra vai trò đặc điểm của chơng trình :
Với các mẫu số cho trớc b=2, ,p, ta có thể xác định tử số theo a theo công thức a= m*b/n +1. Phân số
m/n khi đó sẽ là tối giản vì nó có mẫu số nhỏ nhất trong tất cả các mẫu số nhỏ nhất trong các phân số bằng
nó. Lu ý thêm rằng để so sánh hai phân số a/b và i/j ta không nên dùng phép chia sẽ phát sinh sai số mà
dùng phép nhân:
(a/b)<(m/n) nếu a*j <b*i.


CM Soft 70 NCT F2 Q10
CM Soft 70 NCT F2 Q10
VIETBOOK

82.5 Điểm yên ngựa
Nếu M
i
là min của các phần tử A
ij
ở dòng i, còn M
j
là Max của các phần a
ij
ở cột j thì M
i
<=A
ij
<M
j
.
Điều này cho phép ta có một vài nhận xét sau đây :
a/ Min ở bất kỳ dòng nào không lớn hơn Max ở bất kỳ cột khác, nghĩa là luôn có : M
i
<M
j
.
b/ Nếu đối với bất kỳ i và j nào thoả mãn đẳng thức M
i
=M
j
thì Max của Min trùng với Min của Max,
còn của giao của dòng i với cột j sẽ có điểm yên ngựa.
M
i

512 1000000000 00000000001 1
513 1000000001 10000000001 513
514 1000000010 01000000001 257
515 1000000011 11000000001 769
516 1000000100 00100000001 129

1023 1111111111 11111111111 1023

Chúng ta thấy rằng chữ số hàng cao nhất của m=512 trong hệ nhị phân biểu thị bởi số 1 , và chữ số
hàng đơn vị của số B(m) tơng ứng các giá trị đó sẽ là
1. Các số hạng sau của dãy là 256 và 2. Hệ số hàng cao nhất của số m luôn là 1 bởi vì m>=512. Ta
khử nó và thay thế bằng số m-512 và mang một đơn vị vào trong B(m). Trong chữ số tiếp theo, đơn vị của
số m sẽ là 1 nếu giá trị mới của m >=256. Nếu nó tồn tại chúng ta khử nó và mang vào trong B(m) số 2.
Chúng ta sẽ kiểm tra sự có mặt của số 1 ở hàng tiếp theo Điều này dẫn đễn chơng trình 83.1. Lu ý rằng
vòng lặp sẽ kết thúc khi m=0.
Chơng trình phải dùng đến 512*10 lần lặp. Chơng trình sẽ nhanh hơn khi xây dựng B(m+1) theo
B(m). Nhìn vào cách viết ở hệ nhị phân giá trị B(m) có thể hình dung rằng khi xây dựng B(m+1) cần phải
duyệt B(m) từ trái sang phải và thay 1 bằng 0 ( nghĩa là phải trừ từ B(m) số 512, 256, ) đến số 0 đầu tiên ta
phải thay thế nó bằng 1 và sẽ nhận đợc số B(m+1). Chơng trình tính một nửa số m theo một vòng, số 7
theo 3 vòng Tất cả sẽ ít hơn 512 * 2 vòng. Chơng trình 83.1-2 đợc xây dựng nh vậy.
83.2. Tam giác và điểm
Chúng ta nhận thấy nh sau : Nếu điểm M(x,y) nằm trên đờng thẳng L12 qua M
1
(x
1
,y
1
) và
M
2

1
)*(y-y
1
) = 0
Rõ ràng đối với điểm M(x,y) không nằm trên đờng thẳng L12 thì F
12
(x,y)<>0, hơn nữa dễ kiểm tra
F
12
(x,y)<0 đối với điểm nằm bên trái đờng thẳng L12 (Nếu xét theo phơng từ M
1
đến M
2
) và F
12
(xy)>0
đối với điểm năm bên phải L12. Điều đó có nghĩa là điểm M nằm trong tam giác (M
1
,M
2
,M
3
) khi và chỉ khi
3 số:
F
12
(x,y), F
23
(x,y), F
31

1
, M
2
, M
3
và xác định hàm :
Q(i,j) = sin [(x-x[i]*(y[j]-y[i]) (x[j]-x[i]*(y-y[i])]
Gọi hàm này 3 lần chúng ta tính đợc 3 số t
1
, t
2
, t
3
sau đây :
t
1
= Q(1,2), t
2
= Q(2,3), t
3
= Q(3,1)
Nếu t
1
, t
2
, t
3
bằng nhau thì điểm M nằm trong tam giác, nếu không thì nằm ngoài hoặc ở trên cạnh.
Lời giải khác của bài toán này dựa trên sự so sánh diện tích của tam giác. Chúng ta kí hiệu diện tích
tam giác (M

2
+ S
3
> 1,000001*S. Thừa số 1,000001 cần để tính sai số của phép tính.
83.3. Mê cung .
Bài toán quen thuộc này dễ dàng biến đổi. Lời giải chia ra làm hai phần : Tìm con đờng để ra và in
con đờng Ngợc lại , từ lối ra đến xuất phát của du khách.
Lời giải đơn giản của phần thứ nhất nh sau : Ta viết ở các ô A[i,j], nơi xuất phát của du khách số 2
và đặt k = 2. Chúng ta xét tất cả các ô A của mê cung. Đối với đó, nếu gặp số 0, thì ta xét bốn ô liền kề ô đó.
Nếu có ít nhất một trong chúng chứa số k ( lúc này bằng 2 ) thì ta viết vào ô ấy số k+1.
Bây giờ tăng k lên k+1 và lại xét toàn thể các ô A. Quá trình này kết thúc khi số đợc viết ở ô giới
hạn ( lối ra đã tìm đợc ) hoặc sau khi đã xét toàn bộ các ô A số đã cho không đợc viết vào một ô mới nào
(không có lối ra). Có bao nhiêu lần duyệt các ô thì có bấy nhiêu ô ở trên đờng đi ngắn nhất.
Dễ dàng làm tốt hơn thuật toán trên. ở mỗi bớc đi sẽ xem xét tất cả các ô A của mê cung nh trớc.
Nếu trong một ô nào đó ta gặp số không, còn ở ô bên cạnh bất kỳ có số k >=2 thì chúng ta viết vào ô A số
k+1. Rõ ràng lời giải này là phần đầu của bài toán, nhng nếu trôi chảy, thì ở đây lời giải tìm ra nhanh hơn.
Chơng trình sẽ hiệu quả hơn, khi bắt đầu từ ô đầu tiên (nơi bắt đầu số 2 đợc ghi), tìm ra ô bên
cạnh đầu tiên là bỏ trống( nghĩa là với số 0 ). Ghi vào đó số 3 và tìm ô trống bên cạnh viết số 4.v.v Quá
trình sẽ kết thúc nếu đạt danh giới ( có lối ra ) hoặc không có ô trống bên cạnh (ô cụt). Nếu ô cụt là xuất
phát (nơi ghi số 2)thì không có lối ra. Nếu ô cụt khác ô xuất phát và ở đó ghi K >2 , thì ta viết vào đó số 1 (
làm nó không đi qua đợc ) và chuyển sang ô bên cạnh ô đó với số k-1. Ô nh vậy là có và duy nhất. Lời
giải trình bày ở chơng trình 83.3. ở đó dễ dàng nhận ra sơ đồ chung của sự lựa chọn các tình huống.
Có thể làm gọn hơn nữa chơng trình để giải bài toán Mê cung, nếu ta dùng kỹ thuật đệ qui. Điều
này đợc thực hiện ở chơng trình 83.3-2. Tuy nhiên viết chơng trình nh thế dễ hơn là đọc nó.
Các thuật toán đã trình bày (ngoài thuật toán đầu tiên) có thể tìm ra con đờng không ngắn nhất. Để
tiết kiệm tìm kiếm con đờng ngắn nhất trong Mê cung có thể dùng thêm hai mảng X và Y để ghi nhận toạ
độ (x,y) của các ô cần xét. Kỹ thuật này đợc gọi là tìm kiếm theo bề rộng.
Đầu tiên ở X, Y ta ghi toạ độ của ô xuất phát của du khách. ở mỗi bớc, từ mảng X, Y ta xét các toạ
độ các ô hiện có ( với số hiệu b ) còn các ô tự do bên cạnh, theo trật tự bất kỳ, đợc viết tiếp vào X, Y ( với
số hiệu e ). Nh thế danh sách sẽ đợc xử lý ở phía đầu và thêm vào ở phía cuối.

) ), do đó là ớc số chung của cặp (m
2
, m
3
) với
m
3
= m
1
- (m
1
/m
2
) * m
2
Là số d của phép chia m
1
cho m
2
, nh thế hiển nhiên m
3
< m
2
. Điều ngợc lại cũng đúng: ớc
chung nào của (m2,m3) cũng là ớc chung của ( m
1
,m
2
). Do đó ( m
1

k
sẽ là ớc số chung lớn nhất của các số ban đầu m
1
, m
2
.
Tuy nhiên nếu n không lớn ta có thể trực tiếp chọn i/j = m/n với mẫu số nhỏ nhất j, nghĩa là phân số
đó tối giản. Chỉ cần kiểm tra đẳng thức giữa các phân số không theo quan hệ bằng nhau mà theo đẳng thức
của các tích i*n = j*m. Điều này đợc trình bày trong chơng trình 83.5-2.
Chú ý rằng chơng trình 83.5-2 có thể đòi hỏi n phép tính, trong khi đó 83.5 luôn cần bậc log
2
n
phép tính.
Olimpic 84
84.1. Nghịch thế .
Làm sạch mảng P bởi số 0. Chúng ta lấy số lần lợt i=1, 2, , n và số T
1
. Chúng ta đi theo các phần
tử P
1
, P
2
, đến khi gặp đợc T
i+1
phần tử 0, và viết vào phần tử cuối trong chúng số i.
84.2. Con đờng.
Ta không thể duyệt tất cả các tình huống i
1
, i
2

, i
2
, 1]) với mọi i
1

B[2, i
3
] = min ( B[1,i
2
] + A[i
2
,i
3
,2]) với mọi i
2 B[n-1, i
n
] = min ( B[n-2, i
n-1
] + A[i
n-1
, i
n
, i
n-2
] với mọi i
n-1


làm điều đó ta tìm k=i/j ( k>=j), còn nếu j là ớc số của i thì ta sẽ tính không đến j mà đến k. Cần chú ý để
không có ớc số nào đợc lấy 2 lần ( khi j=k). Thuật toán này thực hiện ở chơng trình 84.3-2.
84.4. Chu kì của phân số.
Lời giải phụ thuộc nhiều một số điều không nhắc tới trong đầu bài.
Khi chia số tự nhiên M cho số tự nhiên N ta đợc phần nguyên của thơng và số d :
I = M/N , k = M - i * N ;
Để giải bài toán trớc hết ta loại bỏ từ phân số M/N phần nguyên của nó, bằng cách thay thế số chia M bởi
số d :
M = M - M/N * N.
Bây giờ chúng ta có thể tuần tự nhận đợc các chữ số của số thơng và số d của phân số :
I = 10 * M/N ; m = 10 * M - i * N và v.v
Mỗi số d không vợt quá N, do vậy sẽ không có nhiều hơn N số d khác nhau và chúng bắt đầu lặp
lại. Khi số d bắt đầu lặp lại thì các thơng số bắt đầu lặp lại và các chu kì đợc bắt đầu. Để tìm đợc phần
lặp lại, đơn giản hơn hết là dựa vào mảng D[1:N]. Viết vào đó các số d theo trật tự nhận đợc và so sánh
mỗi số d mới với tất cả các số d trớc.
Lời giải trên đáng tin cậy, nhng không hay, nó đòi hỏi k phép so sánh và xử lý k lần theo phép tính
số d và có thể cần dùng đến n
2
/2 phép so sánh đến tất cả các số d. Hơn nữa ở tất cả các máy hiện đại lấy
phần nguyên M và N khoảng 10
16
, nhng phải mất hàng năm vào việc thực hiện 10
16
phép tính. Vì thế nếu
ta quyết định đa vào mảng D có N số ta sẽ khởi tạo nó và đánh dấu sự xuất hiện của số d lần lợt thứ M
trong phần tử D[M]. Khi đó việc kiểm tra số d theo k mới chỉ cần một phép so sánh. Thuật toán trên thực
hiện ở chơng trình 84.4.
Lời giải này còn nhợc điểm. Số N có thể lớn bao nhiêu tuỳ ý, sao cho N phép tính có thể tiến hành,
nhng đa vào bộ nhớ toán tử mảng N không thể đợc. Chúng ta sẽ tìm kiếm chu kỳ mà không cần đa ra
mảng cho số d.

+ trong đó m
1
>= m
2
>=
Chúng ta sắp xếp các kết quả phân tích, giả sử :
n = m'
1
+ m'
2
+ m'
3
+ (m')
n = m''
1
+ m''
2
+ m''
3
+ (m'')
là hai phép phân tích. Chúng ta sẽ coi rằng phép phân tích m' sẽ u thế hơn phép phân tích m'', nếu ở cặp
đầu tiên khác nhau có m'
1
<>m''
1
và m'
1
>m''
1
, nghĩa là : m'

m
k
đến số hạng đầu tiên m
k
lớn hơn 1

. Nếu không có số nh vậy thì phép phân tích thu đợc (*) là cuối cùng và công việc kết thúc. Cho rằng số
hạng m
k
> 1 đã tìm thấy. Giảm m
k
đi một đơn vị và bỏ những đơn vị tiếp theo nó, chúng ta làm giảm toàn
tổng đó một giá trị s = 1+i-k. Bây giờ, đối với j = k+1, k+2, Chúng ta lần lợt xác định các giá trị mới của
các số hạng m
j
. Nếu s > m
k
thì chúng ta đặt m
j
= m
k
và giảm s đi giá trị m
k
. Nếu s<=m
k
thì đặt m
j
= s và ở
đây ta kết thúc một phép phân tích số n ra số hạng.
85.2. Các phần tử bằng nhau :

thay thể các phần tử j[i] bằng các phần tử A[i,0]. Nhng thay thể mảng giúp việc j[1:m] có thể đa vào dòng
giúp việc io[1:m]. Ban đầu dòng đầu tiên của mảng đợc đa vào, còn số các phần tử của dòng io giả định
bằng n. Tiếp theo các dòng i=2, 3, , m của mảng A đợc so sánh với dòng io. ở dòng io chỉ còn lại các
phần tử (và đợc chuyển dịch lên đầu) đợc gặp ở dòng i, còn số n
0
các phần tử còn lại ở dòng io nhận giá
trị mới. Nếu n
0
ở bớc nào đó bằng không, thì không có các phần tử bằng nhau, còn nếu không io[1] sẽ là
phần tử cần tìm kiếmThuật toán này đợc thực hiện ở chơng trình 85.2-2. ở đây trong ngôn ngữ Basic hay
Pascal thay thế các phần tử io[j] bằng các phần tử A(0,j) (tơng ứng với A[0,j]).
85.3. Số không tách đợc.
Bài toán này hay hơn việc có thể chỉ ra từ cách nhìn đầu tiên, vì nó đợc giải sau n*n ( thậm chí sau
n*log n ) phép toán. Đây là lời giải có thể có. Đặt s = 1 và xem xét có hay không trong mảng P phần tử
P[j]<= s nào đó. Nếu không có phần tử nh thế, thì S sẽ là lời giải. Nếu tìm đợc phần tử nh vậy thì thêm
vào giá trị của nó tới S nghĩa là S:= S + P[j]. Loại P[j] khỏi mảng và một lần nữa tìm kiếm, tìm thấy hay
không phần tử trong số còn lại không vợt quá giá trị mới của S và cứ nh thế. Có thể chứng minh bằng qui
nạp ( bạn hãy tự làm điều này ) sẽ tìm thấy nhng số không đợc thiết lập đầu tiên. Thực tế lần lợt ở các
bớc i=1, 2, cần phải xem xét phần tử của mảng P bắt đầu từ P[i], còn phần tử tìm thấy P[j] thay thành
P[i].
Để tiết kiệm số các phép toán (trong trờng hợp các số trong mảng không đợc sắp xếp ), có thể sắp xếp lại
làm cho mảng có trật tự, sau đó so sánh với S sẽ chỉ cần thực hiện với một phần tử của mảng P. Thuật toán
trên đợc thực hiện ở các chơng trình 85.3, 85.3-2.
85.4. Hình tứ diện.
Lời giải chia làm hai phần : Chọn mặt N' để trùng với N'
1
. Phần 1 đợc thực hiện theo 4 cách, còn
phần 2 có 3 cách. Sau khi chọn N', chúng ta còn phải tự viết nốt các mặt của N theo một trật tự nào đó
(chẳng hạn ngợc chiều kim đồng hồ ).
Phần thứ hai của lời giải cần viết dới dạng một hàm số ( Xem chơng trình 85.4 ).

86.1. Không có 3 điểm lặp lại.
Dãy cần tìm a
1
, a
2
, , a
i
sẽ đợc xây dựng theo sơ đồ thông thờng của việc duyệt các khả năng.
Chúng ta không diễn giải chi tiết mà chỉ chính xác hoá một số điểm.
Số i sẽ là số bớc đi, các giá trị a
i
=0 và a
i
=1 (hai tình huống của bớc đi này ). Việc kiểm tra là mục
trọng tâm của chơng trình. Ta miêu tả nó.
Sau khi chọn hay thay thế những giá trị a
i
sẽ kiểm tra trong dãy nhận đợc a
1
, a
2
, , a
i
(*), không
một đoạn nào có hạng tử lặp lại 3 lần. Nếu điều kiện này (gọi nó cho ngắn NPT(i) không thoả mãn, thì
không cần xây dựng tiếp dãy (*) mà chuyển qua thay đổi thành phần a
i
( nếu a
i
=1, thì cần thay đổi thành

VIETBOOK
Trang 22

Số lợng trong chúng (đã có sẵn ) duy nhất đặc trng cho tổ hợp. Để tính số cặp bằng nhau, chúng ta làm
bằng 0 bộ ghi S. Chúng ta so sánh mọi phần tử A[i] với tất cả các phần tử tiếp theo A[i] đối với j = i+1,
i+2, và thêm vào S số 1 trong trờng hợp A[i] = A[j].
Điều cần thiết để in câu trả lời p nhận đợc theo giá trị của bộ ghi S trong bảng.

P S S P
4+3+2+1 10 1 1+1 2 5
3+2+1 6 2 1 1 6
2+1+1 4 3 0 0 7
2+1 3 4
Ngoài hai trờng hợp đầu tiên , p = 7 - s
86.3. Cái trống.
Lời giải nh sau là đơn giản nhất. Giả sử k là số thứ tự của véc tơ dự chọn vào phần tử thứ nhất., p là
số thứ tự của véc tơ tiếp theo. Ban đầu k = 1, p=2. Nếu ở thời điểm nào đó xuất hiện :
(1) Xk <= Xp , thì p tăng lên 1
(2) Xk > Xp , thì k đợc thay thế p và p tăng lên 1.
Nếu sau đó p<=12 thì cần chuyển đến việc só sánh các véc tơ Xk và Xp. Nếu p>12, thì số k là lời giải đáp.
Thuật toán này thực hiện ở chơng trình 86.3.
Có thể có lời giải khác. Nó có thể ( ở một vài trờng hợp ) nhanh hơn. Ta đa mảng bổ sung L[1:12]
đối với danh sách các ứng cử ( chính xác hơn danh sách các số thứ tự mà từ đó các ứng cử bắt đầu )
đến véc tơ nhỏ nhất. Ban đầu nạp các số từ 1 đến 12. Sau đó chúng ta lu lại từ chúng những số mà ở đó
phần tử đầu tiên nhỏ nhất, rồi từ chúng những phần tử thứ hai nhỏ nhất, và cứ nh thế cho tới khi không còn
một ứng cử nào hoặc sẽ đợc xem xét cả 12 phần tử ứng cử vào véc tơ nhỏ nhất. Chơng trình 86.3-2
phức tạp hơn nhiều cái trớc đó, để dễ đọc ta qui ớc một số kí hiệu.
i+1 là số hiệu của phần tử các vec tơ ( 0<=i <=11 )
1, j, j
n

=0, nghĩa là lấy vật, còn j = 1 là không lấy vật đó ( xem 2.1 về việc đa ra các thuật ngữ ). Lu ý rằng sẽ
nhận đợc cây nhị phân có tất cả các nhánh đều có độ dài n ( nhng không nhất thiết phải hiểu điều này ).
Ngoài những mảng cho trớc A[1:n] và B[1:n] ta đợc thêm mảng T[1:n] và một số biến nữa :
I : Chỉ số của vật tiếp theo
S : Khối lợng của các vật trong ba lô
Z : Tổng trị giá các vật trong ba lô
Zm : Trị giá lớn nhất trong các phơng án đợc xét
P[k] = 0 hoặc P[k]=1, nếu vật k<=i đợc lấy hay không lấy vào ba lô. Ban đầu ta cho I, S, Z, Zm = 0.
Khi xét các phơng án cần phải biết dừng việc chọn các phơng án ngay khi thấy rằng đó là phơng
án ( và tất cả các bớc tiếp theo của nó ) không đáng quan tâm !.
Trong suốt quá trình, ta luôn cố bổ sung thêm vật vào ba lô (nếu S + A[i] < 30). Trong trờng hợp đó
ta sẽ đi theo nhánh trái
S = S + A[i]: Z = Z + B[i] : P[i] = 0
Nếu nh không thể thêm đợc vật, thì ta sẽ không lấy vật đó ( tức là ta sẽ chuyển dịch theo nhánh
bên phải, bỏ tất cả các nhánh phơng án đi về phía trái ) và lu ý rằng P[i] = 1. Trong cả hai trờng hợp ta
đều tiếp tục chuyển dịch về phía trớc cho đến khi xét đến vật cuối cùng.
Nếu tất cả các vật đợc xét, thì phơng án coi nh đã nhận đợc, ta so sánh với Z
m
:
If Z
m
< Z then Z
m
= Z
Và bắt đầu chuyển dịch về phía sau.
Khi chuyển dịch về phía sau bỏ toàn bộ nhóm các vật đợc lấy liên tiếp ( đối với chúng P[i]=0), bởi
vì các thay đổi trong một nhóm nh vậy chỉ có thể làm giảm tổng trị giá các vật trong ba lô. Nhân tiện bỏ
khỏi ba lô các vật đợc xét
If p[i] = 0 then S = S - A[i] :Z = Z - B[i].
Tiếp sau đó ta bỏ toàn bộ các nhóm vật không đợc lấy trớc đó ( đối với chúng P[i] = 1), bởi sự

là các chỉ số nhỏ nhất của các số có trong (*), mà
A
2
= 2 * A[K
2
] + 1 và A
3
= 3 * A[K
3
] + 1
Còn cha có trong (*)
Ta xét xem điều gì sẽ xảy ra khi thêm vào (*) thêm một hạng tử nữa. Rõ ràng
A[i+1] = MIN ( A
2
A
3
)
Nếu A[i+1] = A
2
, thì K
2
đợc tăng thêm 1
Còn nếu A[i+1] = A
3
thì K
3
đợc tăng thêm 1
( Nếu A[i+1]=A
2
=A

1/3

Để chứng minh sự đúng đắn của thuật toán ta kí hiệu
P[i,j] = {(x,y)} là tập hợp tất cả các cặp số tự nhiên x,y mà
I<=x<=y<=j và x
3
+ y
3
= N
Đặt K = i
3
+ j
3
. Nếu K<N, thì đối với mọi cặp (x,y) từ P(i,j) ta đều có
i
3
+ j
3
< x
3
+ y
3
nhng y<=j, suy ra i < x và nghĩa là nếu K < N, thì P(i,j) = P(i+1,j)
Tơng tự
Nếu K > N, thì P(i,j) = P(i,j-1)
Cuối cùng, khi K = N, sau khi bỏ các cặp (i,j) từ P(i,j) , ta sẽ có nếu K=N, thì P(i,j)\(i,j) = P(i+1,j-1)


CM Soft 70 NCT F2 Q10
CM Soft 70 NCT F2 Q10

này đợc áp dụng cho đoạn A[2:N] và cứ thế mãi .
Nếu để làm phức tạp chơng trình, thì có thể không cần mảng I, nhng vẫn không thay đổi các phần tử
của mảng A. Chỉ cần in và ghi nhớ chỉ số của phần tử nhỏ nhất (MI) tiếp theo. Tất nhiên, trớc hết cần tìm
chỉ số của phần tử đầu tiên đó và chỉ số của phần tử nhỏ nhất đầu tiên ( MA). Điều này đợc làm trong
chơng trình 87.5-2.
olimpic 88.
88.1. Lớn nhất ở bên phải:
Để giải bài này cần sử dụng hai đặc điểm sau. Thứ nhất mảng A[1:n] sẽ đợc xét từ cuối lên ; thứ hai
đa thêm mảng bổ trợ B[1:n] từ các phần tử của mảng A mà có thể có lợi cho việc xét sau này mảng A để
thay các phần tử của nó. Chính xác hơn là vào thời điểm xem xét phần tử A[i] tiếp theo trong mảng B sẽ tìm
các phần tử A[j] (j>1) lớn hơn tất cả các phần tử A[i+1:j-1]. Các phần tử trong mảng B đợc phân bố theo
đúng thứ tự của chúng ở trong A nhng sẽ đợc dịch chuyển sang biên bên phải, chiếm một đoạn B[k:n] nào
đó. Các mảng A và B đợc xử lý đồng thời. Trớc hết đặt
k=n ; B[k]=A[n] ; A[n]=0
Khi xét phần tử A[i] tiếp theo, tất cả các phần tử trên đoạn A[i+1:n] đều đã đợc thay và mảng B[k:n] đã
đợc lấp theo cách cần thiết Trong mảng B[k:n] tìm phần tử đầu tiên B[i] > A[i].


CM Soft 70 NCT F2 Q10
CM Soft 70 NCT F2 Q10

Trích đoạn VIETBOOK Trang

---