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 N đoạn thẳng cùng chiều dài d đơn vị. Hãy chọn K đoạn để ghép thành cạnh của hình chữ nhật có diện tích lớn nhất.
Input: Hai số N và d, n ³ 4.
Output: Hiển thị trên màn hình
   -  t: Tổng số đoạn cần chọn t,
  -  a: Số đoạn đặt trên 1 chiều rộng
  -  b: Số đoạn đặt trên 1 chiều dài,
  -  s: Diện tích max.
Thí dụ,
Input: N = 23, d = 2.
Output:   22   5   6   120.

Thuật toán

Định lý Trong các hình chữ nhật cùng chu vi thì hình vuông có diện tích lớn nhất.
Chứng minh
Gọi c là chu vi của hình chữ nhật, a  là chiều rộng, b là chiều dài, b ³ a, d là độ lệch giữa chiều dài b và chiều rộng a. Ta có, b = a + d và c = 2(a+a+d) = 4a + 2d, diện tích s = a(a+d). Thay giá trị a = (c-2d)/4 vào biểu thức tính diện tích và rút gọn ta thu được s = c2/16 – d2/4 = (c2 – 4d2)/16. Giá trị s đạt max khi và chỉ khi d = 0, tức là khi a = b. Vậy hình chữ nhật có diện tích lớn nhất là c2/16 chính là hình vuông.
Từ định lý trên ta rút ra heuristics sau đây: muốn xây dựng một hình chữ nhật có diện tích lớn nhất từ một chu vi c cố định với các cạnh nguyên cho trước ta phải chọn độ lệch giữa chiều dài và chiều rộng nhỏ nhất có thể được.
Khởi trị: a = b = N div 4.
Xét các trường hợp số đoạn còn thừa r = N mod 4.
r = 0: bỏ qua
r = 1: bỏ qua
r = 2: thêm chiều dài 1 đoạn, b := b + 1;
r = 3: thêm chiều dài 1 đoạn, b := b + 1;
Tổng quát: a = N div 4; b = a + (N mod 4) div 2;
Khi đó diện tích sẽ là: s = a*b*d*d.
Thí dụ, N = 23, d = 2: a = 23 div 4 = 5; b = a + (N mod 4) div 2 = 5 + (3 div 2) = 5 + 1 = 6;
            t = 2*(a+b) = 2*(5+6) = 22; s = a*b*d*d = 5*6*2*2 = 120.
Độ phức tạp: O(1).
(* Pascal *)
(*========================================
   Chon t trong n doan de ghep duoc HCN
   dien tich max
   =======================================*)
program GhepChuNhat;
uses crt;
const bl = #32;
procedure ChuNhatMax(n,d: longint);
var a,b,t,s: longint;
begin
   a := n div 4; b := a + ((n mod 4) div 2);
   t := 2 * (a + b); { tong so doan }
   s := a * b * d * d;
   writeln(t,bl,a,bl,b,bl,s);
end;
BEGIN
  ChuNhatMax(23,2);
END.
Kết quả dự kiến:
22 5 6 120


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