Получить все размеры квадратов, которые помещаются внутри прямоугольника?

Question

Я выполняю следующее упражнение по программированию: Прямоугольник в квадраты . Утверждение таково:

Рисунок ниже дает представление о том, как разрезать данный «истинный» прямоугольник на квадраты («истинный» прямоугольник, означающий, что два измерения различны).

Можете ли вы перевести этот рисунок в алгоритм?

Вам дадут два измерения

a positive integer length (parameter named lng)
a positive integer width (parameter named wdth)

Вы вернете массив или строка (в зависимости от языка; Shell bash, PowerShell и Fortran возвращают строку) с размером каждого из квадратов.

sqInRect(5, 3) should return [3, 2, 1, 1]
  sqInRect(3, 5) should return [3, 2, 1, 1]
  or (Haskell)
  squaresInRect  5  3 `shouldBe` Just [3,2,1,1]
  squaresInRect  3  5 `shouldBe` Just [3,2,1,1]
  or (Fsharp)
  squaresInRect  5  3 should return Some [3,2,1,1]
  squaresInRect  3  5 should return Some [3,2,1,1]
  or (Swift)
  squaresInRect  5  3 should return [3,2,1,1] as optional
  squaresInRect  3  5 should return [3,2,1,1] as optional
  or (Cpp)
  sqInRect(5, 3) should return {3, 2, 1, 1}
  sqInRect(3, 5) should return {3, 2, 1, 1}
  (C)
  C returns a structure, see the "Solution" and "Examples" tabs.
  Your result and the reference test solution are compared by strings.

Примечания:

    lng == wdth as a starting case would be an entirely different problem and the drawing is planned to be interpreted with lng != wdth.

(См. Ката, квадрат в квадраты. Защитите деревья! http://www.codewars.com/kata/54eb33e5bc1a25440d000891 для этой проблемы).

    When the initial parameters are so that lng == wdth, the solution [lng] would be the most obvious but not in the spirit of this

ката, поэтому, в этом случае, верните None / nil / null / Nothing

    return {} with C++, Array() with Scala.

    In that case the returned structure of C will have its sz component equal to 0.

    Return the string "nil" with Bash, PowerShell and Fortran.

    You can see more examples in "RUN SAMPLE TESTS".

Я думал, что мы могли бы решить это упражнение, рассчитав ближайшую степень от двух, до длины * wdth (общий размер данного квадрата). Тогда мы просто добавим каждую ближайшую степень двойки к списку размеров.

Я написал следующий код:

import java.util.*;
public class SqInRect {
    public static List<Integer> sqInRect/*?✅*/(int lng, int wdth) {
    System.out.println("\nlng: "+lng);
    System.out.println("wdth: "+wdth);
    if(lng == wdth) return null;
    List<Integer> sizes = new ArrayList<Integer>();
    int totalSquares = lng * wdth;
    double pow = 0;
    for(int i = 1; totalSquares > 0; i++){
      pow = Math.pow(2,i);
      if(pow >= totalSquares){
        System.out.println("pow: "+pow);
        System.out.println("i: "+i);
        System.out.println("totalSquares: "+totalSquares);
        double prevPow = Math.pow(2,--i);
        System.out.println("prevPow: "+prevPow);
        totalSquares -= prevPow;
        sizes.add(i == 0 ? 1 : i);
        System.out.println("\nnew sizes: "+Arrays.toString(sizes.toArray()));
        i = 0;
      }        
    } 
    System.out.println("\nsizes: "+Arrays.toString(sizes.toArray()));
    return sizes;
    }
}

Однако мы видим, что некоторые тесты не проходят. Например, с учетом следующих тестов:

import static org.junit.Assert.*;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import org.junit.Test;
import java.util.Random;

public class SqInRectTest {

    @Test
    public void test1() {
        List<Integer> res = new ArrayList<Integer>(Arrays.asList(3, 2, 1, 1));
        for (int r : res)
            assertEquals(res, SqInRect.sqInRect(5, 3));
    }
    @Test
    public void test2() {
        assertEquals(null, SqInRect.sqInRect(5, 5));
    }
  @Test
    public void test3() {
    List<Integer> res = new ArrayList<Integer>(Arrays.asList(120, 120, 120, 120, 120, 76,
                                                            44,32,12,12,8,4,4));
        assertEquals(res, SqInRect.sqInRect(676, 120));
    }
}

test3 завершится неудачей. Кроме того, мы можем увидеть след, чтобы узнать, как ведет себя код:

lng: 676
wdth: 120
pow: 131072.0
i: 17
totalSquares: 81120
prevPow: 65536.0

new sizes: [16]
pow: 16384.0
i: 14
totalSquares: 15584
prevPow: 8192.0

new sizes: [16, 13]
pow: 8192.0
i: 13
totalSquares: 7392
prevPow: 4096.0

new sizes: [16, 13, 12]
pow: 4096.0
i: 12
totalSquares: 3296
prevPow: 2048.0

new sizes: [16, 13, 12, 11]
pow: 2048.0
i: 11
totalSquares: 1248
prevPow: 1024.0

new sizes: [16, 13, 12, 11, 10]
pow: 256.0
i: 8
totalSquares: 224
prevPow: 128.0

new sizes: [16, 13, 12, 11, 10, 7]
pow: 128.0
i: 7
totalSquares: 96
prevPow: 64.0

new sizes: [16, 13, 12, 11, 10, 7, 6]
pow: 32.0
i: 5
totalSquares: 32
prevPow: 16.0

new sizes: [16, 13, 12, 11, 10, 7, 6, 4]
pow: 16.0
i: 4
totalSquares: 16
prevPow: 8.0

new sizes: [16, 13, 12, 11, 10, 7, 6, 4, 3]
pow: 8.0
i: 3
totalSquares: 8
prevPow: 4.0

new sizes: [16, 13, 12, 11, 10, 7, 6, 4, 3, 2]
pow: 4.0
i: 2
totalSquares: 4
prevPow: 2.0

new sizes: [16, 13, 12, 11, 10, 7, 6, 4, 3, 2, 1]
pow: 2.0
i: 1
totalSquares: 2
prevPow: 1.0

new sizes: [16, 13, 12, 11, 10, 7, 6, 4, 3, 2, 1, 1]
pow: 2.0
i: 1
totalSquares: 1
prevPow: 1.0

new sizes: [16, 13, 12, 11, 10, 7, 6, 4, 3, 2, 1, 1, 1]

sizes: [16, 13, 12, 11, 10, 7, 6, 4, 3, 2, 1, 1, 1]
expected:<[120, 120, 120, 120, 120, 76, 44, 32, 12, 12, 8, 4, 4]> but was:<[16, 13, 12, 11, 10, 7, 6, 4, 3, 2, 1, 1, 1]>

Не могли бы вы помочь мне понять, почему этот код не подходит для этого упражнения? Какой алгоритм вы бы использовали для решения этого вопроса? Как мы могли бы написать ответ с псевдокодом и Java его версию?

Answer 1

Ваш алгоритм не может начинаться с самого маленького квадрата и идти до самого большого. Вы хотите заполнить оставшуюся часть доступного пространства наименьшим количеством квадратов. Однако вы не знаете, с какого размера квадрата можно начать, чтобы идеально заполнить прямоугольник наименьшим числом квадратов. Вы также не знаете, какой размер квадрата лучше всего подходит после этого размера, и так далее. Вот почему вы хотели бы выбрать подход от самого большого к наименьшему.

Вы хотите разместить наименьшее число квадратов в прямоугольнике, заполнив самый большой квадрат, который вы можете заполнить, а затем попытаться заполнить самый большой квадрат. квадрат в оставшемся пространстве и так далее ...

---

Лично я бы go за рекурсивный подход. Получите прямоугольник, квадрат будет маленькой стороной, затем уменьшите прямоугольник.

fun sqInRect(length: Int, width: Int, squares: ArrayList<Int> = arrayListOf()): ArrayList<Int>? {
    if (length == width && squares.size == 0) return null

    if (length <= 0 || width <= 0) return squares

    return if (width > length) {
        squares.add(length)

        sqInRect(length, width - length, squares)
    } else {
        squares.add(width)

        sqInRect(length - width, width, squares)
    }
}

Результат вашего третьего теста был [120, 120, 120, 120, 120, 76, 44, 32, 12, 12, 8, 4, 4]

---

Вы можете проверить код на KotlinPlayground. Просто нажмите здесь .

Answer 2

Я попытался решить проблему, используя следующий подход. Основная идея c состоит в том, чтобы вырезать квадраты из прямоугольника, если длина и ширина одинаковы.

public static List<Integer> sqInRec (int length, int width) {
    List<Integer> list = new ArrayList<>();
    while(length!=width){
          if(length>width){
             length = length-width;
             list.add(width);
          }else{
              width = width- length;
              list.add(length);
          }
    }
    if(list.size()>0){
          list.add(length);
          return list;
    }

    return null;
}