Fri Aug 31, 2012 9:27 pm
Admin Có một hcn M x N , mỗi lần ta được phép cắt một hcn thành 2 hcn con theo chiều ngang hoặc dọc , và tiếp tục cắt các hcn cho đến khi thành hình vuông thì dừng .
Yêu cầu : tìm cách cắt thành ít ô vuông nhất
HCN.INP
10 2
HCN.OUT
5( Số lượng hình vuông min )
Yêu cầu : tìm cách cắt thành ít ô vuông nhất
HCN.INP
10 2
HCN.OUT
5( Số lượng hình vuông min )
- Code:
Const fi='bai.inp'; fo='bai.out';
Var n,m:Integer;
f:array[1..100,1..100] Of Integer;
f1,g:text;
Procedure doctep;
Begin
Assign(f1,fi);
Reset(f1);
Readln(f1,n,m);
Close(f1);
Assign(g,fo);
Rewrite(g);
End;
Procedure xuly;
Var a,b,i,j,c:Integer;
res:Integer;
Begin
Fillchar(f,sizeof(f),0);
For a:=1 to n do
For b:=1 to m do
Begin
If a=b then
Begin
f[a,b]:=1;
continue;
End;
res:=a*b;
For c:=1 to a-1 do
If res > (f[c,b]+f[a-c,b]) then
res:=f[c,b]+f[a-c,b];
For c:=1 to b-1 do
If res > (f[a,c]+f[a,b-c]) then
res:=f[a,c]+f[a,b-c];
f[a,b]:=res;
End;
End;
Procedure xuat;
Var i,j:Integer;
Begin
For i:=1 to n do
Begin
For j:=1 to m do
Write(g,f[i,j]:3);
Writeln(g);
End;
End;
Begin
doctep;
xuly;
xuat;
Writeln(g,f[n,m]:3);
Close(g);
End.