python - 套路问题 : square-into-squares-protect-trees

Question

我自己无法解决以下问题，所以我搜索并找到了一个可行的算法。有人可以向我解释该算法背后的思维过程、数学或其他内容吗？

类型:https://www.codewars.com/kata/square-into-squares-protect-trees/train/python

算法(https://github.com/Peter-Liang/CodeWars-Python/blob/master/solutions/Square_into_Squares_Protect_trees.py):

def decompose(n):
    goal = 0
    result = [n]
    while result:
        current = result.pop()
        goal += current ** 2
        for i in range(current - 1, 0, -1):
            if goal - (i ** 2) >= 0:
                goal -= i ** 2
                result.append(i)
                if goal == 0:
                    result.sort()
                    return result
    return None

edit: I'm new to Python and had some trouble understanding the code. It's clear to me now.

Answer 1

让我们让程序自己解释:

def decompose(n):
    goal = 0
    print "Adding n, %s, to sequence.\n" % (n)
    result = [n]
    while result:
        current = result.pop()
        print "The last number, %s, wasn't helpful. Removing it from sequence and adding it back to `goal`" % (current)
        print "Trying lower numbers now.\n" if current - 1 > 0 else "\n"

        goal += current ** 2
        for i in range(current - 1, 0, -1):
            print "Trying %s" % (i)
            if goal - (i ** 2) >= 0:
                goal -= i ** 2
                result.append(i)
                "This number, %s, might work. Goal is not below zero. Adding it to sequence and subtracting from `goal`." % (i)
                if goal == 0:
                    result.sort()
                    print "\nFound result, %s." % (result)
                    return result
            else:
              print "This number, %s, is too big here. Continuing." % (i)
    return None

产生:

> decompose(10)

Adding n, 10, to sequence.

The last number, 10, wasn't helpful. Removing it from sequence and adding it back to `goal`
Trying lower numbers now.

Trying 9
Trying 8
This number, 8, is too big here. Continuing.
Trying 7
This number, 7, is too big here. Continuing.
Trying 6
This number, 6, is too big here. Continuing.
Trying 5
This number, 5, is too big here. Continuing.
Trying 4
Trying 3
This number, 3, is too big here. Continuing.
Trying 2
This number, 2, is too big here. Continuing.
Trying 1
The last number, 1, wasn't helpful. Removing it from sequence and adding it back to `goal`


The last number, 4, wasn't helpful. Removing it from sequence and adding it back to `goal`
Trying lower numbers now.

Trying 3
Trying 2
Trying 1
The last number, 1, wasn't helpful. Removing it from sequence and adding it back to `goal`


The last number, 2, wasn't helpful. Removing it from sequence and adding it back to `goal`
Trying lower numbers now.

Trying 1
The last number, 1, wasn't helpful. Removing it from sequence and adding it back to `goal`


The last number, 3, wasn't helpful. Removing it from sequence and adding it back to `goal`
Trying lower numbers now.

Trying 2
Trying 1
The last number, 1, wasn't helpful. Removing it from sequence and adding it back to `goal`


The last number, 2, wasn't helpful. Removing it from sequence and adding it back to `goal`
Trying lower numbers now.

Trying 1
The last number, 1, wasn't helpful. Removing it from sequence and adding it back to `goal`


The last number, 9, wasn't helpful. Removing it from sequence and adding it back to `goal`
Trying lower numbers now.

Trying 8
Trying 7
This number, 7, is too big here. Continuing.
Trying 6

Found result, [6, 8].
=> [6, 8]