TÀI LIỆU TẬP HUẤN TẠI QUẢNG BÌNH
Tháng 7 năm 2010
Một số hàm số học
Ucln(x,y): ước chung lớn nhất của 2 số nguyên a, b,
Bcnn(x,y): bội chung nhỏ nhất của 2 số nguyên a, b,
Len(x,b): số chữ số của số nguyên x trong hệ đếm b,
Height(x,b): Độ cao (tổng các chữ số) của số nguyên x trong hệ đếm b,
Lat(x): số lật của số số nguyên x. Lat(1234) = 4321,
LaSoGanh(x): số x đối xứng? Lat(x) = x,
TongUoc(x): tổng các ước thực sự của số nguyên x,
SoUoc(x): số ước thực sự của số nguyên x,
IsPrime(x): x là số nguyên tố, SoUoc(x) = 1,
Can(x) : căn (bậc 2) nguyên của số nguyên x.
(*---------------------------------Mot so ham so hoc
---------------------------------*)
uses crt;
const bl = #32; { Dau cach }
nl = #13#10; { Ve dau dong tiep theo }
type int = longint;
function Ucln(a,b: int): int;
var r: int;
begin
while b 0 do
begin
r := a mod b;
a := b;
b := r;
end;
Ucln := a;
end;
function Bcnn(a,b: int): int;

y := y * 10 + (x mod 10);
x := x div 10;
until x = 0;
Lat := y;
end;
function LaSoGanh(x: int): Boolean;
begin LaSoGanh := ( x = Lat(x)); end;
function Can(x: int): int;
begin Can := trunc(sqrt(x)); end;
function TongUoc(x: int): int;
var c, d, i: int;
begin
TongUoc := 0;
if x = 1 then exit;
c := Can(x); d := 1;
if c*c = x then begin d := d + c; dec(c) end;
for i := 2 to c do
if x mod i = 0 then d := d + i + (x div i);
TongUoc := d;
end;
{ So uoc thuc su }


function SoUoc(x: int): int;
var c, d, i: int;
begin
SoUoc := 0;
if x = 1 then exit;
c := Can(x); d := 1;
if c*c = x then begin inc(d); dec(c) end;

. La so nguyen to: ');
if IsPrime(x) then writeln(' Yes') else writeln('
No');
readln;
end;
end;
BEGIN
Run;
readln;
END.


Bài toán vẽ 2 nét
Cho đồ thị G liên thông vô hướng, n đỉnh, m cạnh.
Hãy vẽ G bằng 1 nét bút: xuất phát từ 1 đỉnh và qua mỗi cạnh đúng 1 lần.
Thuật toán
1. Đọc dữ liệu gồm n – số đỉnh; m – số cạnh và đọc đủ m cạnh (x,y) ghi vào mảng 2
chiều c gọi là mảng kề, c[x,y] = c[y,x] = 1.
2. Đếm số đỉnh lẻ ghi vào biến s và ghi đỉnh lẻ đầu tiên vào biến DinhLe để dùng sau
này.
3. Kiểm tra s: Nếu s > 2 thông báo vô nghiệm.
Nếu s = 0: Gọi thủ tục Ve(1) bắt đầu từ đỉnh 1;
Nếu s = 2: Gọi thủ tục Ve(DinhLe) bắt đầu từ đỉnh DinhLe.
Thủ tục Ve(z)
Trước tiên ta nạp đỉnh đầu
Tiếp theo lặp đến khi nào trống không,
Từ ngọn ngăn xếp ta trông
Còn đường : xếp tiếp, nếu không xuất liền.
Ý nghĩa :
Ve(z)

for i := 1 to m do
begin
read(f,x,y);
c[x,y] := 1;
c[y,x] := 1;
end;
close(f);
end;
procedure Xem;
var i,j: int;
begin
write(nl,nl,'n = ',n,nl);
for i := 1 to n do
for j := i+1 to n do
if c[i,j] = 1 then writeln(i,' -> ',j);
end;
{ Tim toi da 2 dinh le }
procedure TimDinhLe;
var i,j,b: int;
begin
s := 0;
for i:=1 to n do
begin
b := 0;
for j := 1 to n do b := b + c[j,i];
if Odd(b) then
begin
inc(s);
if s = 1 then DinhLe := i;
end;

InitSt;
Push(z); { nap dinh z vao stack st }
writeln;
repeat
x := GetTop; { xem ngon x cua stack st }
y := TimDinhKe(x); { x -> y }
if y = 0 then
begin { het duong: dua ngon stack vao ket qua }
inc(k); kq[k] := Pop;
end else { co dinh ke, x -> y }
begin
c[x,y] := 2; c[y,x] := 2; { Danh dau duong da duyet }
{ Nap y vao st } Push(y);
end;
until p = 0;
writeln;
for i:=1 to k do write(kq[i],' ');
end;
procedure Run;
var i,j,net: int;
begin
Doc;
Xem;


TimDinhLe;
writeln(nl, s , ' Dinh le ');
if s > 2 then
begin writeln(nl,' Vo nghiem '); exit end;
write(nl, ' Ve 1 net: ');

tử tạo thành một tập con riêng biệt có nhóm trưởng là chính nó.
Với mỗi cạnh (x,y) ta thực hiện thủ tục Union như sau:
- Xác định nhóm trưởng tx của nhóm chứa x, tx := Find(x) ;
- Xác định nhóm trưởng ty của nhóm chứa y, ty := Find(y) ;
- So sánh : nếu tx = ty kết luận x và y cùng nhóm do đó không cần hợp nhất, gán
Union = 0 và dừng.
- Nếu tx < ty : cho ty bám theo tx : d[ty] := tx, Union := 1 (có sự hợp nhất).
- Nếu tx > ty : cho tx bám theo ty : d[tx] := ty (có sự hợp nhất).
Lúc đầu có n mảnh liên thông, sau mỗi lần hợp nhất số mảnh liên thông giảm 1.


Hàm Find (x) xác định nhóm trưởng của nhóm chứa x.
Nhận xét : x là nhóm trưởng khi và chỉ khi d[x] = x.
Sau đó duyệt lại d để xác định các nhóm trưởng và liệt kê các phần tử (đỉnh) trong mỗi
mảnh liên thông : j nằm trong nhóm i khi và chỉ khi Find(j) = i.
Nhận xét : đỉnh 1 luôn luôn là nhóm trưởng của một mảnh liên thông.
Thuật toán Liên thông hóa
Nếu đồ thị G có k mảnh liên thông thì coa thể thêm cho G k-1 cạnh để thu được đồ thị
liên thông. Các cạnh cần thêm là (1,m2), (1,m3),...,(1,mk), trong đó mi là nhóm trưởng, mi
≠ 1.
Thuật toán Kruskal
Init ;
Đọc dần từng cạnh (x,y). Xét
- Nếu Union(x,y) = 0 thì bỏ qua vì x và y cùng mảnh do đó sẽ tạo thành chu trình.
- Nếu Union(x,y) = 1 : Đưa cạnh (x,y) vào cây khung.
(*-----------------------------------Find Union va ung dung:
- Tinh so manh lien thong
- Tim Cay khung theo Kruskal
------------------------------------*)
uses crt;

{ Tinh so manh lien thong }
function SoManh(fn: string): int;
var f: text;
i, m: int;
x,y: int;
s: int;
begin
assign(f,fn); reset(f);
read(f,n,m);
writeln(' So dinh: ',n, ' So canh: ',m);
Init;
s := n; { Luc dau co n manh }
for i := 1 to m do
begin
read(f,x,y); writeln(' Canh: ', x, ' -> ',y);
s := s - Union(x,y);
end;
close(f);
SoManh := s;
end;
{ Liet ke cac manh lien thong }
procedure ManhLienThong(fn: string);
var i,j,k: int;
begin
k := SoManh(fn);
{ Liet ke }
for i := 1 to n do
if (d[i] = i) then
begin
write(nl,' Manh ',i,': ');

close(f);
{ Hien thi cay khung }
writeln(nl,' Cay khung gom ',k, ' canh: ');
for i := 1 to n-1 do writeln(i,'. ',khung[i].a,' ->
',khung[i].b);
end;
function LienThongHoa(fn: string): int;
var i,k: int;
begin
k := SoManh(fn);
for i := 2 to n do
if d[i] = i then { gap nhom truong }
writeln(' Noi dinh 1 voi dinh ', i);
writeln(nl,' So canh can then cho do thi ',fn,':
k-1);
LienThongHoa := k-1;
end;
procedure Run;
var i,k: int;
begin
writeln(nl,'* * * * * D E M O
writeln(' So Manh lien thong: ');
k := SoManh('graph.inp');
write(nl,' Dap so: ',k);

* * * * * ',nl);

',



Dữ liệu cho thuật toán tìm các mảnh liên thông
graph.inp
10 9
1 2
1 10
2 3
3 10
5 6
6 7
7 8
8 5
4 9
Luồng
Phát biểu bài toán:


Cho đồ thị hữu hạn, có hướng G gồm n đỉnh, m cung. Mỗi cung (x,y) có nhãn c(x,y) là
một số nguyên dương gọi là thông lượng của cung. Gọi s là đỉnh phát, t là đỉnh thu của
G. Hãy gán trên mỗi cung (x,y) của G một giá trị nguyên không âm z(x,y) thỏa các ddiều
kiện sau:
a) z(x,y) ≤ c(x,y),
b) Tại mỗi đỉnh x, ta kí hiệu
w+(x) là lượng đến đỉnh x: w+(x) = Σ{ z(u,x) | cung (u,x) thuộc G };
w-(x) là lượng đi từ đỉnh x: w-(x) = Σ{ z(x,y) | cung (x,y) thuộc G },
Với mỗi đỉnh x, trừ đỉnh phát s và đỉnh thu t hệ thức sau được thỏa:
w+(x) = w-(x)
+
c) w (s) = w (t) và đạt max.
Thuật toán
Thuật toán sau đây đơn giản, dễ cài.

begin
writeln;


for i:=1 to n do write(a[i],bl);
end;
{ Hien thi mang 2 chieu }
procedure Print2(var a: mi2);
var i: int;
begin
for i:=1 to n do Print1(a[i]);
end;
procedure Doc;
var i,j, m, x, y, v: int;
begin
assign(f,fn); reset(f);
read(f,n,m);
writeln(' so dinh: ', n, '
so cung: ', m);
read(f,s,t);
writeln(' Dinh phat: ', s, '
Dinh thu: ', t);
fillchar(c,sizeof(c),0);
for i := 1 to m do
begin
read(f,x,y, v); writeln(' Cung ',x, ' -> ',y, '
thong luong: ', v);
c[x,y] := v;
end;
close(f);

var x,y: int;
begin
fillchar(tr, sizeof(tr),0);
InitSt;
w[s] := maxint;
Push(s, s); { nap dinh phat s vao st, tro truoc den
chinh s }
repeat
x := Pop;
if x = t { Gap dinh cuoi (dinh thu) } then
begin
Update(x);
TangLuong := true;
exit;
end;
{ Duyet cac cung x->y }
for y := 1 to n do
if (c[x,y] > z[x,y]) and (tr[y] = 0) then
begin
w[y] := Min(w[x],c[x,y]-z[x,y]); { Tinh trong
so }
Push(x,y); { Nap y vao st, tro truoc toi x }
end;
until IsEmpty;
TangLuong := false;
end;
{ Giai trinh ket qua }
function Ket: int;
var vmax,i: int;
begin

2 3 5
3 7 10
4 2 2
4 7 3
5 6 9
5 8 2
6 4 2
6 8 10
7 2 8
7 5 4
7 6 1