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. 第二名代碼使用了遞歸的方式,效率沒測試怎么樣,但是代碼風(fēng)格值的學(xué)習(xí).recur是一個標志位,為了得到第一個None.相當(dāng)于我的第一個IF判斷.

• 這道題難度系數(shù)六級
• 天外有天,人外有人~~