Vua Tên Miền chuyên cung cấp tên miền đẹp, giá rẻ! Hãy liên hệ kỹ thuật: 0914205579 - Kinh doanh: 0912191357 để được tư vấn, hướng dẫn miễn phí, Cảm ơn quý khách đã ủng hộ trong thời gian qua!
kinh doanh, bán hàng, tư vấn, bảo hiểm Những cá nhân, tổ chức, đại lý,muốn bán, hợp đồng bảo hiểm
Monday, December 16, 2013



Cho tam giác đều ABC, đỉnh A, cạnh dài N đơn vị. Tại các điểm chia nguyên trên các cạnh ta kẻ các đường thẳng song song chia tam giác thành N2tam giác đơn vị (TGĐV). Mã số cho các TGĐV theo trật tự từ trên xuống và từ trái qua phải là 1, 2, …, N2. Ba bạn A, B và C được cấp mỗi bạn một TGĐV khác nhau làm nơi xuất phát trên các cạnh AB cho bạn A, BC cho bạn B và AC cho bạn C.  Lần lượt theo thứ tự quay


vòng A, B, C viết chữ cái tên mình vào các TGĐV kề cạnh với các tam giác mà mình đã viết ở lần trước. Biết các giá trị N, và các điểm xuất phát NA, NB và NC, tính số chữ cái mỗi loại mỗi bạn đã viết.

Tổ chức dữ liệu

Các biến dùng chung:
var n: longint; { Do dai canh tam giac }
f,g: text; { input, output file }
AN, BN, CN: longint; { O xuat phat }
Ad, Av, Bd, Bv, Cd, Cv: longint; { Toa do xuat phat }
Ak,Bk,Ck: longint;
A,B,C: longint; { con dem }
Kq: array [‘A’..’C’] of longint;
trong đó n là chiều dài một cạnh của tam giác đều; AN, BN và CN là số hiệu của các ô xuất phát tương ứng cho A, B và C.

Thuật toán

Xét các tam giác đơn vị từ đỉnh xuống đến cạnh đáy của bàn cờ. Ta thấy, trên dòng 1 có 1 TGĐV, dòng 2 có 3, dòng 3 có 5 TGĐV... Tổng quát, trên dòng i tính từ đỉnh xuống đến đáy sẽ có 2*i -1 TGĐV. Trên mỗi dòng i ta gán số hiệu cho các TGĐV là 1, 2, ... , 2i-1.    Ta định nghĩa tọa độ của một tam giác đơn vị có số hiệu (tuyệt đối theo đầu bài) cell là cặp số (d,v) trong đó d là số hiệu dòng chứa TGĐV đó và v là số hiệu  của tam giác đó trên dòng d. Thủ tục ToaDodưới đây tính tọa độ cho một TGĐV theo cell - số hiệu (tuyệt đối) của TGĐV như cách mã số của đề bài. Thủ tục cho ra hai giá trị,  dong - dòng chứa TGĐV cell và viTri -  số hiệu của TGĐV trên dòng đó mà ta gọi là số hiệu tương đối. Thí dụ, ToaDo(15,d,v) cho ta d = 4, v = 6.
procedure ToaDo(cell: longint;var dong, viTri:longint);
begin
  dong := 0;
  while cell > 0 do
    begin
      dong := dong + 1;
      cell := cell - (2*dong-1);
    end;
    viTri := cell + (2*dong-1);
end;
Hàm KhoangCach dưới đây tính khoảng cách giữa hai TGĐV theo tọa độ (d1,v1) và (d2,v2), trong đó d1, d2 là số hiệu dòng, v1 và v2 là số hiệu  tương đối của chúng (trên dòng). Giống như bài trước, khoảng cách trong bài này chính là số TGĐV ít nhất, kề cạnh nhau trên đường đi từ TGĐV (d1,v1) đến TGĐV (d2,v2).  Trước hết ta đổi chỗ hai tọa độ, nếu cần, sao cho tam giác thứ nhất luôn luôn nằm ở dòng trên so với tam giác thứ hai, tức là  d1 £ d2. Sau đó ta nhận xét như sau:
Nếu một TGĐV có đỉnh quay lên trên thì
* Số hiệu tương đối của nó là số lẻ, và
* Nó sẽ là đỉnh của một tam giác đều chứa nó và có các cạnh song song với các cạnh của bàn cờ.
Nếu một TGĐV có đỉnh quay xuống dưới thì
* Số hiệu tương đối của nó là số chẵn, và
* TGĐV kề cạnh với nó trên cùng dòng sẽ có đỉnh quay lên trên.
Ta gọi các TGĐV có đỉnh quay lên trên là tam giác lẻ để phân biệt với các TGĐV chẵn - có đỉnh quay xuống dưới.
Nếu TGĐV thứ nhất (d1,v1) là tam giác lẻ ta xét tam giác lớn hơn tạo bởi các TGĐV nhận tam giác lẻ này làm đỉnh và có cạnh đáy trên dòng d2. Ta tính hai đỉnh trên đáy của tam giác này trên dòng d2 là C1 và C2 theo công thức
  d := 2*(d2 - d1);
  c1 := v1;
  c2 := v1 + d;
Tiếp đến ta xét vị trí v2 trên cạnh đáy có thể nằm giữa C1 và C2 hoặc nằm ngoài đoan [C1, C2] đồng thời xét v2 là tam giác chẵn hay lẻ.
function KCLe(d1,v1,d2,v2: longint):longint;
var c1,c2,d: longint;
begin
  { v1 <= v2 }
  d := 2*(d2 - d1);
  c1 := v1;
  c2 := v1 + d;
  if (c1 <= v2) and (v2 <= c2) then
    begin
      if odd(v2) then KCLe := d
      else KCLe := d - 1;
     exit;
    end;
   KCLe := d + Min(abs(v2-c1),abs(v2-c2));
end;
Nếu TGĐV thứ nhất (d1,v1) là tam giác chẵn thì ta lùi lại một dòng dể xét TGĐV lẻ có chung đáy với TGDV thứ nhất rồi tính toán như trên và giảm kết quả 1 đơn vị.
function KhoangCach(d1,v1,d2,v2: longint):longint;
var t: longint;
begin
  if d1 > d2 then
  begin
    t := v1; v1 := v2; v2 := t;
    t := d1; d1 := d2; d2 := t;
  end;
  { v1 <= v2 }
  if odd(v1) then KhoangCach := KCLe(d1,v1,d2,v2)
  else KhoangCach := KCLe(d1-1,v1-1,d2,v2) - 1;
end;
procedure XuLi;
 var d,v,j: longint;
     Ad, Av, Bd, Bv, Cd, Cv: longint;
begin
   fillchar(kq,sizeof(kq),0);
   ToaDo(NA, Ad, Av);
   ToaDo(NB, Bd, Bv);
   ToaDo(NC, Cd, Cv);
   for d := 1 to N do
     for v := 1 to 2*d - 1 do
        inc(kq[Min3(KhoangCach(Ad,Av,d,v),
                    KhoangCach(Bd,Bv,d,v),
                    KhoangCach(Cd,Cv,d,v))]);
end;

Độ phức tạp

Ta phải duyệt mọi TGĐV trên bàn cờ, vậy độ phức tạp tính toán cỡ N2.
 

Nguồn:

SÁNG TẠO
TRONG THUẬT TOÁN
LẬP TRÌNH


tcaviet@gmail.com

0 comments:

Post a Comment

domain, domain name, premium domain name for sales

Popular Posts