Ghép hình chữ nhật

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 = c²/16 – d²/4 = (c² – 4d²)/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à c²/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

VÀ

LẬP TRÌNH