问立方体堆体积
EN

Stack Overflow用户

提问于 2018-09-08 10:34:27

回答 3查看 3.5K关注 0票数 2

我在尝试挑战。其想法如下：

“你的任务是建造一个由n个立方体组成的建筑，底部的立方体的体积为n^3，上面的立方体的体积为(n-1)^3等等，直到顶部的体积为1^3。你得到的是这栋建筑的总体积m。如果给m，你能找到你要建的立方体数n吗？如果不存在这样的n，则返回-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。

我漏掉了什么明显的东西吗？

python

optimization

电商安全场景方案

帮助电商行业客户一站式解决Web安全、黑产羊毛党对抗、高危漏洞、BOT工具、恶意入侵门户服务器等安全问题

回答 3

Stack Overflow用户

发布于 2018-09-08 10:54:54

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

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

如果您从这个问题借用了许多整数平方根选项中的一个，并验证sqrt平方给出了原始数字，那么您应该对算法没有意见，至少如果我没有忽略某个角落的情况。

(旁白:你已经注意到了关键的模式。数字1，3，6，10，15。是非常有名的，并且有自己的公式，您可以用它来求解是否存在这样一个直接工作的数字。)

票数 3

Stack Overflow用户

发布于 2018-09-08 10:45:58

我不知道你的答案是否正确，但我对这个问题有另一个更容易解决的办法

def max_level(remain_volume, currLevel):
    if remain_volume < currLevel ** 3:
        return -1
    if remain_volume == currLevel ** 3:
        return currLevel
    return max_level(remain_volume - currLevel**3, currLevel + 1)

你可以用max_level(m, 0)找到答案。它需要O(n)时间和O(1)内存。

票数 1

Stack Overflow用户

发布于 2018-09-08 11:03:57

DSM的答案是一个，但是加上我的两分钱来改进解决方案.

Brilliant.org中的这个表达式用于对立方体数进行求和：

sum of k**3 from k=1 to n:
    n**2 * (n+1)**2 / 4

这个问题当然可以在所涉及的总量中得到解决。这里是四种解决方案之一(要求n和v都是正的)：

from math import sqrt

def n(v):
    return 1/2*(sqrt(8*sqrt(v) + 1) - 1)

但是这个函数也返回79863.0。现在，如果我们把所有的立方体数从1加到n，由于精度错误，我们得到了一个稍微不同的结果：

v = 10170290665425347857
cubes = n(v)    # 79863
x = sum([i**3 for i in range(cubes+1)])

# x = 10170290665425347857, original
x  -> 10170290665425347856