간단한 제곱 된 사각형에 대한 알고리즘

Question

불평등 한 사각형으로 사각형을 분할하고 싶습니다. 웹에서 일부 검색 후 this Link을 찾았습니다. 이 출력은 내가 필요로한다 :

는 사람이에 대한 생각이 있습니까?

Answer 1

Yves Daoust가 말했듯이이를 해결하는 알고리즘은 느려질 것입니다. 첫 번째 과제는 큰 사각형에 맞추기 위해 어떤 사각형을 결합해야할지 결정하는 것입니다. 그런 다음 그들이 거기에 들어갈 지 파악하십시오.

먼저 영역별로 필터링합니다.

첫 번째 부분에 답하려면 큰 사각형에 들어갈 수있는 사각형 조합을 찾아야합니다. 5x5 정사각형이 4x4 정사각형을 가진 3x3과 동일한 영역을 차지하므로 여러 조합이있을 수 있습니다. 이것은 O (2^n) 문제입니다.

그런 다음 정렬을 시도하십시오.

큰 사각형 크기의 매트릭스를 만들 것입니다. 그런 다음 맨 위부터 시작하여 가장 오른쪽 색인에서 시작하여 정사각형이 차지하는 행렬 위치를 표시하여 정사각형에 추가합니다. 그런 다음 사용되지 않은 사각형을 추가하는 이전 규칙에 따라 다음 비어있는 공간으로 이동합니다. 사각형이 맞지 않으면 이전 사각형을 제거하고 다음 사각형으로 계속 진행합니다. 이것은 재귀를 요구하는 메소드입니다.

내가 처음에 말했듯이 이것은 느린 방법이지만 그렇게되면 해결 방법이 제공됩니다.

Answer 2

이 문제를 해결하기 위해 동적 프로그래밍 방식을 사용했습니다. $ g ++ -O3 -std = C++ 11 squares.cpp -o 사각형 :

당신이 직접 코드를 컴파일 할 수 있습니다 : N ~ 50 내가 효율을위한 비트 세트와 같은 솔루션을 저장 할 때까지 만 작동

#include <bitset> 
#include <iostream> 
#include <list> 
#include <vector> 

using namespace std; 

constexpr auto N = 116; 

class FastSquareList { 
public: 
    FastSquareList() = default; 

    FastSquareList(int i) { mask_.set(i); } 

    FastSquareList operator+(int i) const { 
    FastSquareList result = *this; 
    result.mask_.set(i); 

    return result; 
    } 

    bool has(int i) const { return mask_.test(i); } 

    void display() const { 
    for (auto i = 1; i <= N; ++i) { 
     if (has(i)) { 
     cout << i * i << " "; 
     } 
    } 
    cout << endl; 
    } 

private: 
    bitset<N + 1> mask_; 
}; 

int main() { 
    int n; 
    cin >> n; 
    vector<list<FastSquareList> > v(n * n + 1); 
    for (int i = 1; i <= n; ++i) { 
    v[i * i].push_back(i); 
    for (int a = i * i + 1; a <= n * n; ++a) { 
     int p = a - i * i; 
     for (const auto& l : v[p]) { 
     if (l.has(i)) { 
      continue; 
     } 

     v[a].emplace_back(l + i); 
     } 
    } 
    } 

    for (const auto& l : v[n * n]) { 
    l.display(); 
    } 

    cout << "solutions count = " << v[n*n].size() << endl; 

    return 0; 
} 

예 :

이

$ ./Squares 
15 
9 16 36 64 100 
25 36 64 100 
1 4 9 16 25 49 121 
4 36 64 121 
4 100 121 
4 16 25 36 144 
1 16 64 144 
81 144 
4 16 36 169 
4 9 16 196 
4 25 196 
225 
solutions count = 12