Минимальное количество разрезов прямоугольника на квадраты - PullRequest
Новая
       38

Минимальное количество разрезов прямоугольника на квадраты

1 голос
/ 29 мая 2020

Задача - найти минимальное количество разрезов прямоугольника на квадраты. Для этого я написал рекурсивную функцию, но дело в том, чтобы написать ее, используя динамическое c программирование. Я написал матрицу на бумаге, но мне все еще сложно написать код .. Здесь a и b - размеры прямоугольника: 

int minimalNumOfCuts(int a, int b)
{
    if (a==b) return 0;
    int result;
    if (a<b)
        result = 1+minimalNumOfCuts(b-a,a);//found a square with side a, so I add 1 and recurs on 
    else result = 1+minimalNumOfCuts(a-b,b);//found a square with side b
    return result;
}

Например, для прямоугольника 3x5 функция должна вернуть 3, что является количество минимальных разрезов, необходимых для получения одного квадрата со стороной 3, одного со стороной 2 и двух квадратов со стороной 1.

Вот как я думаю (если я использую динамическое c программирование) матрицу должен смотреть, когда решаю подзадачи (меньшие прямоугольники). Столбец и строка с нулями не нужны.

enter image description here

1 Ответ

1 голос
/ 29 мая 2020

Вы go через прямоугольник с помощью алгоритма Евклида, который является своего рода тем, что вы пытаетесь там, и подсчитываете разрезы, есть некоторые возможности для рекурсивной функции, которая могла бы этого достичь, вот возможная реализация, передающая указатель счетчика в качестве аргумента функции, которая будет изменена во внутренних рекурсиях:

Live demo 

#include <stdio.h>
#include <stdlib.h>

void minimalNumOfCuts(int side1, int side2, int *count);

int main() {
    int side1 = 3, side2 = 5, count = 0;

    minimalNumOfCuts(side1, side2, &count);
    printf("Height %d Length %d - %d cuts\n", side1, side2, count);

    return EXIT_SUCCESS;
}

void minimalNumOfCuts(int side1, int side2, int *count) {

    if (side1 == side2) {
        return;
    }

    if (side1 > side2) {
        side1 -= side2;
    }
    else {
        side2 -= side1;
    }
    (*count)++;
    minimalNumOfCuts(side1, side2, count); //recursive call
}

Вывод: 

Height 3 Length 5 - 3 cuts

РЕДАКТИРОВАТЬ:

Для вашей таблицы просто прокрутите значения:

В этом примере подсчитываются вырезы из прямоугольника с высотой от 1 до 5 и длиной от 1 до 4 используя ту же рекурсивную функцию.

Живая демонстрация 

#define MAX_HEIGHT 5
#define MAX_LENGHT 4

int main() {

    int count = 0;

    for (int i = 1; i < MAX_HEIGHT + 1; i++) {
        for (int j = 1; j < MAX_LENGHT + 1; j++) {   
            minimalNumOfCuts(i, j, &count);
            printf("Height %d Length %d - %d cuts\n", i, j, count);
            count = 0;
        }
    }
    return EXIT_SUCCESS;
}

Вывод: 

Height 1 Length 1 - 0 cuts
Height 1 Length 2 - 1 cuts
Height 1 Length 3 - 2 cuts
Height 1 Length 4 - 3 cuts
Height 2 Length 1 - 1 cuts
Height 2 Length 2 - 0 cuts
Height 2 Length 3 - 2 cuts
Height 2 Length 4 - 1 cuts
Height 3 Length 1 - 2 cuts
Height 3 Length 2 - 2 cuts
Height 3 Length 3 - 0 cuts
Height 3 Length 4 - 3 cuts
Height 4 Length 1 - 3 cuts
Height 4 Length 2 - 1 cuts
Height 4 Length 3 - 3 cuts
Height 4 Length 4 - 0 cuts
Height 5 Length 1 - 4 cuts
Height 5 Length 2 - 3 cuts
Height 5 Length 3 - 3 cuts
Height 5 Length 4 - 4 cuts

Вот красивый график c демонстрация , где вы можете проверить результаты.

Обратите внимание, что в вашей таблице есть некоторые неточности, например, прямоугольник со сторонами 3 и 4 потребует всего 3 разрезов.

...