Trở về đầu

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

HỌC TIN CÙNG THỦ KHOA

Thành tích hôm nay, Thành công ngày mai !

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

}

Bản quyền thuộc về Nguyễn Tô Sơn, Đại học Sư phạm Hà Nội. Điện thoại: 091.333.2869