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 x đoạn thẳng màu xanh có chiều dài bằng nhau là dx đơn vị và d đoạn màu đỏ có chiều dài bằng nhau là dd đơn vị. Hãy chọn nx đoạn xanh và nd đoạn đỏ đặt trên chu vi của hình chữ nhật tạo thành một đường viền đan màu (các màu xen kẽ nhau) và diện tích của hình là lớn nhất.
Input: Bốn số x, dx, d  và dd, x ³2, d ³2.
Output: Hiển thị trên màn hình
- nx: Số đoạn xanh được chọn,
- nd: Số đoạn đỏ được chọn,
- s: Diện tích max.

* Thí dụ 1
input: (x, dx, d, dd) = (5, 2, 7, 2)
output: (nx, nd,  s) = (5, 5, 24)
* Thí dụ 2
input: (x, dx, d, dd) = (6, 2, 7, 3)
output: (nx, nd,  s) = (6, 6, 56)
* Thí dụ 3
input: (x, dx, d, dd) = (6, 2, 7, 2)
output: (nx, nd, s) = (6, 6, 36)
* Thí dụ 4
input: (x, dx, d, dd) = (7, 2, 7, 3)
output: (nx, nd, s) = (6, 6, 56)
















Hình chữ nhật
có cạnh đan màu
xanh - đỏ và đạt
diện tích max







































                                                           

















 
x = 11, dx = 1,
  d = 10, dd = 2.
  nx = 10, nd = 10,
s = 7 ´ 8 =  56.





Thuật toán

Dễ thấy là để thu được hình có đường viền đan màu thì cần chọn số đoạn xanh nx và số đoạn đỏ nd như nhau, tức là chọn nx = nd= min(x, d). Khi đó chu vi của hình sẽ gồm t = nx + nd = 2nx = 2nd đoạn, và do đó t là một số chẵn. Do t chẵn nên (t mod 4) sẽ bằng 0 hoặc 2.
Kí hiệu a là số đoạn (tính cả xanh và đỏ) cần đặt trên một chiều rộng, b là số đoạn (tính cả xanh và đỏ) cần đặt  trên một chiều dài của hình. Xét hai trường hợp dx = dddxdd.
1. Trường hợp thứ nhất: dx= dd.  Ta có, a  = b = t div 4. Nếu (tmod 4 = 2). Ta thêm vào chu vi một cặp xanh đỏ nữa. Vậy ta cần chọn:
- nx = min(x,d) đoạn xanh,
- nd = nx đoạn đỏ,
- Diện tích max: s= a * b * dx * dx với
   a = t div 4  là số đoạn đặt trên 1 chiều rộng,
   b = a+ ((t mod 4) div 2) là số đoạn đặt trên 1 chiều dài.
2. Trường hợp thứ hai: dxdd.  Ta thấy, để đảm bảo tính đan màu thì ab phải có cùng tính chẵn lẻ. Từ đó thấy rằng khi (t mod 4 = 2) ta phải bỏ qua số dư, vì nếu thêm cho chiều dài b 1 đoạn nữa thì tính chẵn lẻ của ab sẽ khác nhau. Để ý rằng khi abcùng chẵn thì hình nhận được sẽ vuông và mỗi cạnh chứa đúng z = adiv 2 đoạn xanh và z đoạn đỏ. Khi đó diện tích có thể tính theo công thức: s = sqr(z * (dx+ dd)). Nếu ab cùng lẻ thì số lượng đoạn xanh và số lượng đoạn đỏ trong một cạnh sẽ hơn kém nhau 1 đơn vị. Nếu cạnh này nhiều xanh hơn đỏ thì cạnh kề với cạnh đó sẽ nhiều đỏ hơn xanh. Khi đó diện tích sẽ được tính theo công thức
s = (z * dx + (z+1) *dd) * (z * dd + (z+1) * dx)  = (z* dx + z * dd + dd) * (z * dd + z * dx+ dx)
   = (z * (dx + dd) + dd) * (z * (dx + dd) + dx)  = (k+ dd) * (k + dx)
với z = a div 2,  k = (a div 2)*(dx + dd).
Kết quả là cần chọn:
nx = min(x,d). Chu vi 2*nx phải là bội của 4, tức là nx phải chẵn. Nếu nx  lẻ thì  đặt lại nx:= nx - 1.
nd = nx;
 tổng cộng  t = nx + nd đoạn, trong đó
                   Số đoạn đặt trên 1 chiều rộng: a = t div 4,
                   Số đoạn đặt trên 1 chiều dài: b = a,
-      Diện tích max: (k+dd) * (k+dx), k = (a div 2)*(dx+dd).
   Độ phức tạp: O(1).
(* Pascal *)
  program XanhDo;
  uses crt;
  const bl = #32;
  function Min(a,b: longint): tự viết
  procedure XD(x,dx,d,dd: longint);
   var a,b,nx,nd,k,t,s: longint;
  begin
    if (dx = dd) then
      begin
        nx := Min(x,d); nd := nx; t := nx + nd;
        a := t div 4;
        b := a + ((t mod 4) div 2); s := a * b * dx * dx
      end
     else { dx <> dd }
      begin
        nx := Min(x,d);
        if (nx mod 2 > 0) then nx := nx - 1;
        nd := nx; t := nx + nd; a := t div 4; b := a;
        k := (a div 2) * (dx + dd);
        if (Odd(a)) then s := (k + dx) * (k + dd)
        else s = k*k;
      end;
     writeln(nx,bl,nd,bl,s);
  end;
  BEGIN
   XD(7, 2, 7, 3);
  END.


Nguồn:

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


0 comments:

Post a Comment

domain, domain name, premium domain name for sales

Popular Posts