java - 获取适合矩形的所有正方形的大小？‽？

Question

我正在做以下编程练习:Rectangle into Squares 。声明如下:

The drawing below gives an idea of how to cut a given "true" rectangle into squares ("true" rectangle meaning that the two dimensions are different).

Can you translate this drawing into an algorithm?

You will be given two dimensions

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

You will return an array or a string (depending on the language; Shell bash, PowerShell and Fortran return a string) with the size of each of the squares.

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.

Notes:

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

(See kata, Square into Squares. Protect trees! http://www.codewars.com/kata/54eb33e5bc1a25440d000891 for this problem).

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

kata so, in that case, return 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".

我认为我们可以通过计算最接近的 2 次幂来解决这个练习，即 lngth * wdth(给定正方形的总尺寸)。因此，我们只需将每个最接近的 2 的幂添加到尺寸列表中即可。

我编写了以下代码:

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

我使用以下方法尝试了该问题。基本思想是从矩形中切出正方形，只要长和宽相同即可。

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;
}