将正方形分割成小正方形

Question

将正方形分割成小正方形

algorithmmath

4

我有一个大正方形，我想把它分成小正方形。我需要所有可能的组合。我知道有无限多的组合，但是我有一个限制：最小正方形的大小是固定的。

我可以使用暴力方法实现，但这太耗时了。

有没有更好的算法来完成这个任务？

谢谢！

- aritomo

1

请进一步解释您试图解决的问题。这听起来像某种作业问题？ - akent

小方块是什么意思？请举个例子。 - Mork0075

这是来自欧拉计划吗？ - Emil H

你所说的“square”，是指“x * x = x的平方”还是“四条边长度相等的四边形”？我们需要更多的信息。 - Binary Worrier

1

@Binary Worrier... 它们不是同一件事吗... x * x == x ^ 2 == x的“平方” == 表示边长为x的四边形的数学表示。 - Eoin Campbell

我可以使用网格。该网格的单元格将是最小的正方形。但我不仅需要可能正方形的数量，还需要包含所有信息的正方形，例如对于大小为4且最小大小为2的大正方形，以下是可能组合之一：square1= x=0, y=0, size=2 square2= x=2, y=0, size=2 square3= x=0, y=2, size=2 square4= x=2, y=2, size=2如何在不使用蛮力的情况下获取所有组合？ - aritomo

4个回答

0

我提出以下Python代码，用于将一个大正方形（512x512）随机分成较小的正方形（最小32x32）。

import random 
import numpy as np

n = 16
cellSize = 32
smallSizes = [1,2,4,8]

def is_cell_available(grid, indexRow, indexCol):
    return not bool(grid[indexRow, indexCol])

def try_square_size(grid, indexRow, indexCol):
    smSizes = smallSizes.copy()
    while True:
        potentialSize = random.choice(smSizes)
        if indexRow + potentialSize <= n and indexCol + potentialSize <= n:
            if np.count_nonzero(grid[indexRow:indexRow+potentialSize, indexCol:indexCol+potentialSize])==0:
                return potentialSize
        else:
            smSizes.remove(potentialSize)

grid = np.zeros((n,n), np.uint8)
bigMat = np.zeros((n*cellSize,n*cellSize), np.uint8)

for indexRow in range(n):
    for indexCol in range(n):
        if is_cell_available(grid, indexRow, indexCol):
            blockSize = try_square_size(grid, indexRow, indexCol)
            val = random.randint(1,255)
            grid[indexRow:indexRow+blockSize, indexCol:indexCol+blockSize] = val
            bigMat[indexRow*cellSize:(indexRow+blockSize)*cellSize, indexCol*cellSize:(indexCol+blockSize)*cellSize] = val
        else:
            pass

- Emilien Valat

0

我的数学有点模糊，但如果你有一个正方形（n²），那么你就有一个边长（n）。

从n，你可以计算出该数字的所有因子，并将它们用作小正方形的边...

例如：

n^2 = 44100
n = 210

Factors of n = x=2,x=3,x=5,x=7, x= ... and so on.

所以每个因子的小正方形是

x=2 : x^2 = 4 : 44100 / 4 = 11025 small squares
x=3 : x^2 = 9 : 44100 / 9 = 4900 small squares
x=5 : x^2 = 25 : 44100 / 25 = 1764 small squares
x=7 : x^2 = 49 : 44100 / 49 = 900 small squares

等等

- Eoin Campbell

+1，但它们不必是质因数，我想，所以210的因数是1、2、3、5、6、7、10，啊，为什么你要选一个有这么多因数的数字？ - Patrick McDonald

1

他也可能是指平方和，例如 5^2 = 3^2 + 4^2。 - Patrick McDonald

@Patrick，是的，我故意这样做了，把前几个质数相乘；-)为了完整起见...“1,2,3,5,6,7,10,14,15,21,30,35,42,70,105,210”。关于平方和...那将是一个非常重要的条件被省略了，肯定会限制他的“无限”分解。想必他必须将整数因子除以分数大小的平方。 - Eoin Campbell

当n为质数时，你的方法完全失败。 - mueslo

0

并不存在“无限”组合。实际上，数量可能很大，但是有界的。此外，如果您需要严格的正方形（宽度=高度，而不仅仅是矩形），则数量更少，因为您必须在两侧使用相同的整数来分割原始正方形（边长为L），否则您也会得到矩形。如果您正在使用整数，则建议仅将L除以2、3、... M（L/M = 最小内部正方形长度）。

- Dan

1

@丹，如果他没有实现一个固定的最小尺寸，那么它可能有无限多种可能性。他没有说明他的分解需要整数大小，所以如果没有这个限制，他可以继续分解0.5^2、0.25^2、0.125^2等平方。 - Eoin Campbell

这让我想起了《小天才》中的一幕，老师在黑板上写下1-10的数字，然后问班上有多少个数可以被2整除。没有人回答，于是她转向她的优等生：“弗雷德，我知道你知道哪些数字可以被2整除。”无聊的弗雷德抬起头，看到了列表，然后说：“嗯，全部都可以。”那个开头的“嗯”是最好的部分，好像在问：“这真的算一个问题吗？” - PaulMcG

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- RMAAlmeida · Accepted Answer

这个问题只有在我们做出两个假设的情况下才有解决方案（否则会有无限组合）

1）最小的正方形具有固定的大小
2）切割大正方形的方式也是固定的，就好像将正方形放入由小正方形大小分隔的网格中的线条一样。

还有一个第三个假设可以使问题变得更容易

3）大正方形的边长是小正方形的K倍。其中K是整数。

如果两个假设都成立，我们可以继续：

找到N（N为整数）个最小正方形的数量：大小为N * small-size的正方形

 if ((big-size % N*small-size)==0)
    Number += (big-size / N*small-size)^2
 else
    Number += ((big-size / N*small-size)^2) * (big-size % N*small-size)

else 条件中的 * (big-size % N) 是因为如果大正方形不能被 N 整除，当使用 N 个小步长进行网格化时，会有一个“分数部分”剩余。这样我们就可以再次开始划分（重新网格化），但是偏移量为 1、2 或 N 个小步长。步数为 (big-size % N)。

同样，这些步骤只在满足 3 个假设的情况下才成立。