Quadraturas do retângulo

Aqui, uma macro que lida com o problema da “quadratura do retângulo”.

Dado um retângulo, digamos de tamanho 11 x 10, como eu decomponho a mesma no menor número de quadrados menores?

A macro utiliza um algoritmo recursivo. Basicamente, esta vai testando todas as combinações possíveis em duas dimensões, até chegar ao final, e compara o número de quadrados gerados. É o chamado método da força-bruta.

Mesmo incluindo alguns truques, como eliminando quem tem mais quadrados que o mínimo até então, o algoritmo continua sendo força bruta – ou seja, demora muito quando aumenta o tamanho do problema.

Outro exemplo, um retângulo 13 x 11.

Uma utilidade possível é encaixar produtos em pallets, ou conjugar cargas em carregamentos, utilizando métodos adaptados.

Há um problema similar, porém com uma restrição muito mais forte: todos os quadrados menores devem ter tamanho diferente.

Esta restrição é tão forte que a maioria dos retângulos não vai ter solução. Porém, algumas que as têm geram resultados muito bonitos, como o seguinte (retângulo 33 x 32).

Houve uma série de matemáticos que estudou este problema, chegando em soluções bem legais (porém, muito mais matemáticas que computacionais).

Uma história desses é mostrada no livro “Mania de matemática”, de Ian Stewart.

Link para download: https://github.com/asgunzi/quadraturaVBA

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair /  Alterar )

Foto do Google

Você está comentando utilizando sua conta Google. Sair /  Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair /  Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair /  Alterar )

Conectando a %s