python - 一堆立方体的体积

Question

我正在尝试挑战。思路如下:

"Your task is to construct a building which will be a pile of n cubes. The cube at the bottom will have a volume of n^3, the cube above will have volume of (n-1)^3 and so on until the top which will have a volume of 1^3.

You are given the total volume m of the building. Being given m can you find the number n of cubes you will have to build? If no such n exists return -1"

我显然看到了:

2³ + 1 = 9 = 3² 和 3 - 1 = 2

3³ + 2³ + 1 = 36 = 6² 和 6 - 3 = 3

4³ + 3³ + 2³ + 1 = 100 = 10² 和 10 - 6 = 4

5³ + 4³ + 3³ + 2³ + 1 = 225 = 15² 和 15 - 10 = 5

6³ + 5³ + 4³ + 3³ + 2³ + 1 = 441 = 21² 和 21 - 15 = 6

所以如果我想，如果我检查某个数字是平方根，我就已经可以排除一些了。然后我可以从 1 开始一个变量，从平方根开始取那个值(递增)。这些值最终会匹配，否则之前的平方根将变为负值。

所以我写了这段代码:

def find_nb(m):
    x = m**0.5
    if (x%1==0):
        c = 1
        while (x != c and x > 0):
            x = x - c
            c = c + 1

        if (x == c):
            return c
        else:
            return -1
    return -1

这不应该工作吗？我错过了什么？我失败了样本集的三分之一，例如:10170290665425347857 应该是 -1，在我的程序中它给出 79863。

我是否漏掉了一些明显的东西？

Answer 1

您遇到了浮点精度问题。也就是说，我们有

In [101]: (10170290665425347857)**0.5
Out[101]: 3189089316.0

In [102]: ((10170290665425347857)**0.5) % 1
Out[102]: 0.0

所以内部分支被采用，即使它实际上不是正方形:

In [103]: int((10170290665425347857)**0.5)**2
Out[103]: 10170290665425347856

如果您从 this question 中借用许多整数平方根选项之一并验证 sqrt 平方给出了原始数字，你应该对你的算法没问题，至少如果我没有忽略一些极端情况的话。

(另外:您已经注意到关键模式。数字 1、3、6、10、15.. 非常有名并且有自己的公式，您可以使用它来解决是否存在这样的问题一个直接有效的数字。)