Trở về đầu
Đề bài: Nhập từ bàn phím 2 số tự nhiên m, n (với 5 < m, n <1000) là hai kích thước của hình chữ nhật. Đưa ra màn hình phương án cắt hình chữ nhật trên thành các hình vuông sao cho số hình vuông là ít nhất.
Mời các bạn download tại: Click here
#include <iostream>
using namespace std;
const int MAXN = 1000;
const int oo = INT_MAX;
int m, n;
int F[MAXN][MAXN];
int H[MAXN][MAXN];
void Nhap() {
cout << "Nhap so hang: "; cin >> m;
cout << "Nhap so cot: "; cin >> n;
}
void QHD() {
int i, j, c, h;
for (i=1; i<=m; i++) {
for (j=1; j<=n; j++) {
if (i == j) F[i][j] = 1;
else if (i > j) F[i][j] = F[j][i];
else if (j%i == 0) F[i][j] = j/i;
else { // j > i va j khong chia het cho i
F[i][j] = +oo;
for (c=1; c<=j/2; c++)
if (F[i][j] > F[i][c] + F[i][j-c]) {
F[i][j] = F[i][c] + F[i][j-c];
H[i][j] = +c;
}
for (h=1; h<=i/2; h++)
if (F[i][j] > F[h][j] + F[i-h][j]) {
F[i][j] = F[h][j] + F[i-h][j];
H[i][j] = -h;
}
}
}
}
}
void TruyVet(int i, int j) {
if (i == j) {
cout << i << " ";
return;
}
if (i > j) {
TruyVet(j, i);
return;
}
// i < j
int k;
if (j%i == 0) {
for (k=1; k<=j/i; k++) cout << i << " ";
return;
}
int c, h;
if (H[i][j] > 0) {
c = H[i][j];
TruyVet(i, c);
TruyVet(i, j-c);
return;
}
// H[i][j] < 0
h = -H[i][j];
TruyVet(h, j);
TruyVet(i-h, j);
return;
}
void KQ() {
cout << "So it nhat cac hinh vuong la: " << F[m][n] << endl;
}
int main(){
Nhap();
QHD();
KQ();
cout << "Cach chia la: " << endl;
TruyVet(m, n);
}