Trở về đầu

foto1 foto2 foto3 foto4 foto5
Giảng viên
Nguyễn Tô Sơn - Thủ khoa Đại học Sư phạm Hà Nội
ĐT: 091.333.2869

HỌC TIN CÙNG THỦ KHOA

Thành công không phải đích đến, mà là cả một hành trình

Tìm kiếm

Đề 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);

}

Giảng viên Nguyễn Tô Sơn, Thủ khoa Đại học Sư phạm Hà Nội. Điện thoại: 091.333.2869