Theo định nghĩa số hạng thứ hai vế phải bằng không, do đó:
Sx = ycF
Hay
Tương tự ta tính được:
Như vậy là từ các công thức trên, ta có thể tính được mômen tĩnh của một hình nếu
biết trọng tâm hoặc ngược lại xác định được trọng tâm nếu biết mômen tĩnh của hình
mà không phải qua phép tính tích phân.
b) Từ đó ta có công thức tính trọng tâm hình ghép nếu biết trọng tâm của các hình
thành phần.
Nhận xét: Từ công thức này ta có thể tính được trọng tâm của một hình đa giác bất
kỳ dựa vào các tam giác thành phần.
Công thức tính trọng tâm G, và diện tích F của hình tam giác biết toạ độ 3 đỉnh A
(XA, YA), B (XB, YB) và C (XC, YC).
Dựa vào nhận xét trên đây tôi xin giới thiệu chương trình tính trọng tâm của một
hình đa giác lồi bất kỳ.
Dữ liệu vào là n (n > 2) điểm (trong mặt phẳng Oxy) – toạ độ n đỉnh liên tiếp nhau
của đa giác lồi. Ta chia đa giác lồi này thành n-2 tam giác với 3 đỉnh của tam giác
lần lượt là đỉnh thứ 1, đỉnh thứ i và đỉnh thứ i + 1 (2 ≤ i ≤ n – 1). Dữ liệu vào là n (n
> 2) điểm (trong mặt phẳng Oxy) – toạ độ n đỉnh liên tiếp nhau của đa giác lồi. Ta
chia đa giác lồi này thành n-2 tam giác với 3 đỉnh của tam giác lần lượt là đỉnh thứ
1, đỉnh thứ i và đỉnh thứ i + 1 (2 ≤ i ≤ n – 1).
Từ đây ta có thể xây dựng chương trình, sau đây là toàn văn chương trình:
{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R-,S+,T-,V+,X+,Y+}
{$M 16384,0,655360}
Program Xac_dinh_trong_tam ;
Const
Maxn = 1000 ;
FileInp = 'TTAM.INP' ;
FileOut = 'TTAM.Out' ;
tp = 2 ; {So chu so thap phan can}
Type
Toado = Record
x, y : Real ;
End ;
Mang = Array [1.. Maxn] of Toado ;
Var
A : Mang ;
XG, YG : Real ;
tongx, tongy, tong : Real ;
N : Integer ;
Procedure Docfile ;
Var
f : Text ;
i : Integer ;
Begin
Assign (f, FileInp) ;
{$I-}
Reset (f) ;
{$I+}
If IOResult <> 0 then Halt ;
Readln (f, N) ;
FillChar (A, Sizeof (A), 0) ;
For i := 1 to N do
Readln (f, A [i].x, A [i].y) ;
Close (f) ;
tongx := 0 ;
tongy := 0 ;
tong := 0 ;
End ;
Function XAG (AA, BB, CC : Toado) : Real ;
Begin
XAG := (AA.x + BB.x + CC.x) / 3 ;
End ;
Function YAG (AA, BB, CC : Toado) : Real ;
Begin
YAG := (AA.y + BB.y + CC.y) / 3 ;
End ;
Function SA (AA, BB, CC : Toado) : Real ;
Var
tam : Real ;
Begin
tam := (AA.x - BB.x) * (AA.y + BB.y) +
(BB.x - CC.x) * (BB.y + CC.y) +
(CC.x - AA.x) * (CC.y + AA.y) ;
SA := Abs (tam) / 2 ;
End ;
Procedure Xuly ;
Var
i : Integer ;
tamx, tamy, tamS : Real ;
Begin
For i := 2 to n - 1 do
Begin
tamx := XAG (A [1], A [i], A [i + 1]) ;
tamy := YAG (A [1], A [i], A [i + 1]) ;
tongx := tongx + tamx * tamS ;
tongy := tongy + tamy * tamS ;
tong := tong + tamS ;
End ;
XG := tongx / tong ;
YG := tongy / tong ;
End ;
Procedure Ghifile ;
Var
f : Text ;
Begin
Assign (f, FileOut) ;
Rewrite (f) ;
Writeln (f, XG : 0 : tp, #32, YG : 0 : tp) ;
Close (f) ;
End ;
Begin
Docfile ;
Xuly ;
Ghifile ;
End.
File vào TTAM.INP
4
00
40
44
04
File ra TTAM.OUT
2.00 2.00
Bạn đọc có thể tìm hiểu thêm để xác định được trọng tâm của một hình bất kỳ (có cả
phần khuyết bên trong) đồng thời có thể xác định thêm các đặc trưng hình học khác
như mô men quán tính Jx, Jy, Jxy, bán kính quán tính ix, iy… Rất mong sự quan
tâm và trao đổi của quý bạn đọc.
Bàn thêm về cặp ghép
Lưu anh tuấn
Bài toán cặp ghép là 1 bài toán rất cơ bản và cũng có rất nhiều ứng dụng trong thực
tế. Trên ISM đã có rất nhiều bài viết viết về những vấn đề liên quan đến bài toán
này. Bài viết của tôi chỉ xin nói thêm về 1 khía cạnh ít được đề cập đến. Đó là đếm
số lượng cặp ghép.
Bài toán phát biểu như sau:
Cho N sinh viên( N<=12 ) và N vấn đề cần nghiên cứu. Mỗi sinh viên sẽ hứng thú
với 1 số vấn đề, và khi sinh viên được giao vấn đề họ thích thì họ sẽ làm việc hiệu
quả hơn rất nhiều. Ngài giáo sư đáng kính của chúng ta muốn biết có bao nhiêu cách
ghép sao cho mỗi sinh viên sẽ giải quyết 1 vấn đề mà họ thích.
Giáo sư sẽ cung cấp cho chúng ta 1 ma trận A kích thước NxN trong file
PROBLEM.TXT với
+ A[i,j]=1 khi sinh viên i thích vấn đề j.
+ A[i,j]=0 khi sinh viên i không thích vấn đề j.
Yêu cầu: Bạn hãy viết 1 chương trình tính số ghép thoả mãn yêu cầu của giáo sư và
gửi file kết quả SOLVE.TXT cho giáo sư.
Ví dụ:
PROBLEM.TXT
3
111
111
110
SOLVE.TXT
4
Giải thích : 4 cặp ghép là
((1,2),(2,3),(3,1))
((1,1),(2,3),(3,2))
((1,3),(2,1),(3,2))
((1,3),(2,2),(3,1))
Bài toán trên ta có thể giải theo cách tầm thường là tìm toàn bộ cách khả năng có thể
ghép bằng cách vét cạn, độ phức tạp là N!. Trong trường hợp ma trận A gồm toàn số
1, số cách chọn sẽ là N!. Dù N<=12 nhưng N! vẫn là 1 giá trị “khủng khiếp”.
Sau đây tôi xin đề xuất cách giải với thuật toán QHĐ trạng thái. Xin nói qua về
QHĐ trạng thái. QHĐ trạng thái là QHĐ trên các trạng thái, các trang thái thường
được biều diễn bằng 1 dãy bít hoặc tính trước.
Ví dụ 1: Bài 1 thi QG năm 2006 bảng B ( tôi không nói lại đề ) : Ta dùng QHĐ
trạng thái với 8 trạng thái cho mỗi dòng : (0,0),(0,1),(0,2),(0,3),(0,4),(1,3),(1,4),(2,4)
với ý nghĩa (i,j) là chọn ô i và ô j, giá trị 0 là không chọn ô nào. Ví dụ 2: Bài viết
“chia sẻ 1 thuật toán hay” của bạn Nguyễn Hiển. Bạn đã dùng 1 dãy bít với ý nghĩa
là bít thứ i bằng 1 nếu công việc đó được chọn, bằng 0 nếu công việc đó không được
chọn.
Trở lại bài toán của chúng ta. Ta biết: 1 cách ghép cặp là cách ghép 1 sinh viên và 1
vấn đề. Giả sử ta có 1 cách ghép cặp (x1,y1),(x2,y2),…,(xn,yn). Bây giờ ta bỏ đi 1
cặp (x1,y1). Cặp ghép còn lại là (x2,y2),(x3,y3),…,(xn,yn) vẫn là 1 cặp ghép, ta có
bài toán với kích thước nhỏ hơn. Như vậy các bạn đã thấy rõ bản chất QHĐ của bài
toán này. Để tìm số cách ghép của N sinh viên, ta phải tìm số cách ghép của N-1
sinh viên.
Ta định nghĩa 1 dãy bít X thay cho các trạng thái của các vấn đề. X[i]=1 nếu vấn đề
i được chọn. X[i]=0 nếu vấn đề i không được chọn. Độ dài dãy bít tối đa là 12 nên ta
thay 1 dãy bít X bằng 1 giá trị TX.
Vì cặp ghép là đầy đủ nên số sinh viên ghép với 1 trạng thái X là số giá trị 1 trong
X. Ta cố định các sinh viên này và duỵêt qua tất cả các trạng thái X. Gọi D[TX] là
số cách ghép cặp 1 trạng thái X với sl sinh viên đầu tiên, sl là số bít 1 của trạng thái
X. Ta có công thức QHĐ: D[TX] := D[TX]+D[TX xor (1 shl i)] với i thoả mãn
X[i]=1 và có sinh viên sl thích vấn đề i. TX xor (1 shl i) có ý nghĩa là thay giá trị bít
thứ i thành 0, ta đã giảm số vấn đề được chọn đi 1. Sau đây là chương trình:
{ Sử dụng Free Pascal }
Const max = 1 shl 12;
fi = 'PROBLEM.TXT';
fo = 'SOLVE.TXT';
Var n : Integer;
f ,g : text;
A : array[0..20,0..20] of Boolean;
D : array[0..max] of longInt; {Mảng D có ý nghĩa như trên }
T : array[0..20] of Integer; { T lưu lại vị trí các bít 1 để dễ dàng QHĐ hơn }
Procedure Tinh( TX : LongInt );
Var gt , j , i , sl : LongInt;
{sl là số lượng bít 1}
Begin
gt := TX;
i := -1;
sl := -1;
While gt> 0 do {vong while de tim cac bit 1 trong phan tich nhi phan so TX}
Begin
Inc( i );
If gt and 1 = 1 then {neu bít i là 1 }
Begin
Inc(sl);
T[pt]:=i; {luu lai vi tri cac bit 1}
End;
gt:= gt shr 1;
End;
D[TX]:=0;
For j :=0 to sl do
If A[ sl , T[j] ] then {Sinh viên sl thích vấn đề T[j]}
Inc( D[TX] , D[ TX xor (1 shl T[j])] );
{TX xor (1 shl T[j] là tắt bit thứ T[j]}
End;
Procedure Xuli;
Var TX:LongInt;
Begin
D[0]:=1;
For TX:=1 to (1 shl n)-1 do
Tinh(TX); {QHD voi so TX
Writeln(g, D[1 shl n-1] );
End;
Procedure Nhap;
Var i ,j,t:Integer;
Begin
Read(f,n);
For i:=0 to n-1 do
For j:=0 to n-1 do
Begin
Read(f,t);
A[i,j]:= t =1;
End;
End;
Begin
assign(f,fi);reset(f);
assign(g,fo);rewrite(g);
fillchar(d,sizeof(d),0);
Nhap;
Xuli;
close(f);close(g);
End.
Thuật toán trên có độ phức tạp khoảng 2^N, hiệu quả hơn rất nhiều so với cách
duyệt bình thường.
Bài toán trên đã giải quyết xong. Bây giờ, ta sẽ thay đổi bài toán trên 1 chút:
Vị giáo sư đáng kính muốn biết có bao nhiêu cách ghép cặp mà trong đó có chứa
cặp sinh viên x và vấn đề y.,/p>
Khi ta đã giải quyết được bài toán trên thì bài toán mở rộng trở nên quá dễ.
Trên đây, tôi xin bàn thêm về bài toán cặp ghép. Để nói hết thì thật là khó. Hi vọng
các bạn sẽ cùng tôi khám phá những điều mới mẻ và lý thú từ những thuật toán hay.
Một vài bài tập về Palindrome
Palindrome hay còn gọi là xâu đối xứng, xâu đối gương là tên gọi của những xâu kí
tự mà khi viết từ phải qua trái hay từ trái qua phải thì xâu đó không thay đổi. VD:
MADAM, IOI,... Nhờ tính chất đặc biệt đó mà có khá nhiều bài tập có liên quan đến
Palindrome, phần lớn trong chúng thường đi kèm với QHĐ. Tôi xin giới thiệu với
các bạn một vài bài tập như vậy.
Bài 1: Xem một xâu có phải là Palindrome hay không?
Đây là một bài cơ bản, nhưng quan trọng vì nó được đề cập đến trong nhiều bài tập
khác. Cách làm tốt nhất là duyệt đơn thuần mất O(N).
function is_palindrome(s: string): boolean;
var i, n : integer;
begin
n := length(s);
for i := 1 to (n div 2) do
if s[i] <> s[n+1-i] then
begin is_palindrome := false; exit; end;
is_palindrome := true;
end;
Một đoạn chương trình khác :
function is_palindrome(s : string) : boolean;
var i, j : integer;
begin
i := 1;
j := length(n);
while i
begin
if s[i] <> s[j] then
begin is_palindrome := false; exit; end;
inc(i);
dec(j);
end;
is_palindrome := true;
end;
Bài 2: Cho một xâu S <= 1000 kí tự; tìm palindrome dài nhất là xâu con của S ( Xâu
con là một dãy các kí tự liên tiếp ).
Đây cũng là một bài cơ bản với nhiều cách làm.
Cách 1: QHĐ
Dùng mảng F[i, j] có ý nghĩa: F[i, j] = true/false nếu đoạn gồm các kí tự từ i đến j
của S có/không là palindrome.
Ta có công thức là:
* F[i, i] = True
* F[i, j] = F[i+1, j-1]; ( nếu s[i] = s[j] )
* F[i, j] = False; ( nếu s[i] <> s[j] )
Đoạn chương trình như sau:
FillChar( F, sizeof(F), false );
for i := 1 to n do F[i, i] := True;
for k := 1 to (n-1) do
for i := 1 to (n-k) do
begin
j := i + k;
F[i, j] := ( F[i+1, j-1] ) and (s[i] = s[j] );
end;
i∀Kết quả là : Max(j-i+1) <=j thỏa F[i,j] = True.
Độ phức tạp thuật toán là 0(N2).
Chú ý : Với N lớn, ta phải thay mảng 2 chiều F bằng 3 mảng 1 chiều và dùng thêm
biến max lưu giá trị tối ưu.
Cách 2: Duyệt có cận.
Ta xét từng vị trí i:
+ xem a[i] có phải là tâm của Palindrome có lẻ kí tự không?
( ví dụ Palindrome MADAM có tâm là kí tự D )
+ xem a[i] và a[i+1] có phải là tâm của Palindrome có chẵn kí tự không?
( ví dụ Palindrome ABBA có tâm là 2 kí tự BB )
với mỗi kí tự ta tìm palindrome dài nhất nhận nó là tâm, cập nhập lại kết quả khi
duyệt. Ta duyệt từ giữa ra để dùng kết quả hiện tại làm cận.
Đoạn chương trình như sau:
procedure Lam;
var i, j : Longint ;
{}
procedure try( first, last : Longint );
var đ : Longint;
begin
if first = last then
begin đ := 1; dec(first); inc(last); end
else đ := 0;
repeat
if (first < 1) or (last > N) then break;
if s[i] = s[j] then
begin
đ := đ + 2;
first := first - 1;
last := last + 1;
end
else break;
until false;
if max < dd then max := dd;
end;
{}
begin
i := n div 2;
j := n div 2 + 1;
max := 1;
while (i > max div 2) and (j <= N-max div 2) do
begin
if i > max div 2 then
begin
try( i, i );
try( i, i+1 );
end;
if j <= N - max div 2 then
begin
try( j, j );
try( j, j+1 );
end;
i := i - 1;
j := j + 1;
end;
end;
Cách làm này có độ phức tạp: max*(N-max). Vì vậy nó chạy nhanh hơn cách QHĐ
trên, thời gian chậm nhất khi max = N/2 cũng chỉ mất N2/4 nhanh gấp 4 lần cách
dùng QHĐ. Nhờ vậy, chúng ta biết là: không phải lúc nào QHĐ cũng chấp nhận
được về mặt thời gian và không phải lúc nào duyệt lúc nào cũng chậm.
|
