Details:

Rectangle into Squares

Description:

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).

alternative text

Can you translate this drawing into an algorithm?

You will be given two dimensions

1. a positive integer length (parameter named lng)
2. a positive integer width (parameter named wdth)

You will return an array or a string (depending on the language; Shell bash 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]

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++. In that case the returned structure of C will have its sz component equal to 0. Return the string "nil" with Bash and Fortran.
• You can see more examples in "RUN SAMPLE TESTS".

中文大概含义:

看图就明白了,没必要说明~~

我自己的代码如下:

def sqInRect(lng, wdth):
    num = [lng,wdth]
    Min = min(num)
    if lng==wdth:
        return None
    squre = []
    while Min!=0:
        squre.append(Min)
        num = [num[0]-Min,num[1]] if num[1]==Min else [num[0],num[1]-Min]
        Min = min(num)
    # your code
    return squre

第一名代码:

def sqInRect(lng, wdth):
    if lng == wdth:
        return None
    if lng < wdth:
        wdth, lng = lng, wdth
    res = []
    while lng != wdth:
        res.append(wdth)
        lng = lng - wdth
        if lng < wdth:
            wdth, lng = lng, wdth
    res.append(wdth)
    return res

第二名代码:

# Recursive solution
def sqInRect(lng, wdth, recur = 0):
    if lng == wdth:
        return (None, [lng])[recur]            # If this is original function call, return None for equal sides (per kata requirement);
                                               # if this is recursion call, we reached the smallest square, so get out of recursion.
    lesser = min(lng, wdth)
    return [lesser] + sqInRect(lesser, abs(lng - wdth), recur = 1)

1. 我的方法和第一名思路类似,很容易明白.
2. 第二名代码使用了递归的方式,效率没测试怎么样,但是代码风格值的学习.recur是一个标志位,为了得到第一个None.相当于我的第一个IF判断.

• 这道题难度系数六级
• 天外有天,人外有人~~