最小的正方形切割数

无标题

任务是找到最小数量的正方形矩形。我编写了一个递归函数来执行此操作，但是重点是使用动态编程编写它。我在纸上写了矩阵，但是仍然很难写代码。这里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的两个正方形所需的最小割数。

这是我认为（如果我使用动态编程）解决子问题（较小的矩形）时矩阵的外观。不需要带有零的列和行。

阿纳斯塔丘

您使用欧几里得算法遍历矩形，这是您要尝试的方法，并计算切割次数，递归函数有一些可能实现此目的，这是一个可能的实现，它将计数器指针作为参数传递内部递归中要更改的功能：

现场演示

#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

这是一个不错的图形演示，您可以在其中检查结果。

请注意，表中有一些不确定性，例如，边数为3和4的矩形仅需要切割3个。

本文收集自互联网，转载请注明来源。

如有侵权，请联系 [email protected] 删除。