栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

SPOJ`CUBERT`中的错误答案

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

SPOJ`CUBERT`中的错误答案

您的解决方案有两个问题,都与浮点运算的使用有关。第一个问题是Python

float
的精度只包含大约16位有效十进制数字,因此,一旦您的答案需要超过16位有效数字左右(即该点之前超过6位数字,之后则超过10位数字),您已经获得正确的尾随数字的希望很小。第二个问题更加微妙,甚至影响的很小的值
n
。那就是您舍入到十进制小数点后再舍去最后一位数字的方法会由于双舍入而遭受潜在的错误。例如,以
n= 33
。的立方根,大约
n
为20个小数位:

3.20753432999582648755...

在该点之后四舍五入到11位时,您最终得到

3.20753433000

现在删除最后一位数字会得到

3.2075343300
,这不是您想要的。问题在于,舍入到小数点后11位会影响第11位左侧的数字。

那么,您该如何解决呢?好吧,您可以完全避免浮点并将其简化为纯整数问题。我们需要一些整数的立方根

n
到小数点后10位(将最后一位向下取整)。这等效于计算的立方根
10**30*n
为最接近的整数,再次四舍五入,然后将结果除以
10**10
。因此,这里的基本任务是计算任何给定整数的立方根底数
n
。我无法找到有关计算整数立方根的任何现有Stack
Overflow答案(在Python中还更少),所以我认为值得详细说明如何这样做。

事实证明,计算整数的立方根非常容易(借助于一点点数学)。有多种可能的方法,但是有效且易于实现的一种方法是使用Newton-
Raphson方法的纯整数版本。在实数上,用于求解方程的牛顿方法对的立方根

x**3= n
进行近似
x
处理
n
,然后迭代以返回改进的近似值。所需的迭代是:

x_next = (2*x + n/x**2)/3

在实际情况下,您将重复迭代,直到达到所需的公差为止。事实证明,在整数,本质上是相同的迭代工作,并与合适的退出条件,它会给我们 正好
正确的答案(无需公差)。整数情况下的迭代为:

a_next = (2*a + n//a**2)//3

(请注意,使用底数除法运算符

//
代替
/
上面通常的真除法运算符。)数学上,
a_next
正好是的底数
(2*a + n/a**2)/3

这是基于此迭代的一些代码:

def icbrt_v1(n, initial_guess=None):    """    Given a positive integer n, find the floor of the cube root of n.    Args:        n : positive integer        initial_guess : positive integer, optional. If given, this is an initial guess for the floor of the cube root. It must be greater than or equal to floor(cube_root(n)).    Returns:        The floor of the cube root of n, as an integer.    """    a = initial_guess if initial_guess is not None else n    while True:        d = n//a**2        if a <= d: return a        a = (2*a + d)//3

和一些示例使用:

>>> icbrt_v1(100)4>>> icbrt_v1(1000000000)1000>>> large_int = 31415926535897932384626433>>> icbrt_v1(large_int**3)31415926535897932384626433>>> icbrt_v1(large_int**3-1)31415926535897932384626432

icbrt_v1
我们很快会解决一些烦恼和效率低下的问题。但首先,简要解释一下以上代码为何起作用。请注意,我们从一个初始猜测开始,假设该猜测大于或等于多维数据集根的底数。我们将证明此属性是循环不变的:
每次
我们到达while循环的顶部时,
a
至少是
floor(cbrt(n))
。此外,每次迭代产生的值都
a
严格小于旧值,因此可以保证我们的迭代最终收敛到
floor(cbrt(n))
。为了证明这些事实,请注意,当我们进入
while
循环时,有两种可能性:

情况1.

a
严格大于的立方根
n
。然后
a > n//a**2
,代码继续进行下一个迭代。写
a_next = (2*a +n//a**2)//3
,那么我们有:

  • a_next >= floor(cbrt(n))
    。这是由于以下事实:
    (2*a + n/a**2)/3
    至少是的立方根
    n
    ,而这又又来自应用于的AM-GM不等式
    a
    a
    并且
    n/a**2
    :这三个量的几何平均值恰好是的立方根
    n
    ,因此算术平均值必须 为至少 是的立方根
    n
    。因此,我们的循环不变式将保留用于下一次迭代。

  • a_next < a
    :因为我们假定
    a
    比立方根较大,
    n/a**2 < a
    以及接下去
    (2a + n/a**2) / 3
    a
    ,从而获得一种
    floor((2a + n/a**2) / 3) < a
    。这保证了我们在每次迭代时都朝着解决方案前进。

情况2.

a
小于或等于的立方根
n
。然后
a <= floor(cbrt(n))
,但是从上面建立的循环不变性我们也知道
a >=floor(cbrt(n))
。我们完成了:
a
是我们追求的价值。从此时开始,while循环退出
a <= n // a**2

上面的代码有两个问题。首先,与初始猜测开始

n
是低效的:该代码将花费其最初的几个迭代(粗略地)分割的当前值
a
3
每一次,直到它进入溶液的附近。对于初始猜测(在Python中很容易计算),一个更好的选择是使用大于2的立方根的2的第一个乘方
n

initial_guess = 1 << -(-n.bit_length() // 3)

更好的是,如果

n
它足够小以避免溢出,则可以使用浮点算法来提供初始猜测,例如:

initial_guess = int(round(n ** (1/3.)))

但这将我们带入了第二个问题:算法的正确性要求初始猜测不小于实际的整数立方根,并且随着算法的增大,我们

n
不能保证
initial_guess
上述基于浮点数的算法(尽管足够小)
n

我们可以)。幸运的是,有一个非常简单的解决方法:对于 任何
正整数
a
,如果我们执行一次迭代,我们总是最终得到的值至少为
floor(cbrt(a))
(使用与上面使用的相同的AM-
GM参数)。因此,我们要做的就是在开始测试收敛之前至少执行一次迭代。

考虑到这一点,下面是上述代码的更有效版本:

def icbrt(n):    """    Given a positive integer n, find the floor of the cube root of n.    Args:        n : positive integer    Returns:        The floor of the cube root of n, as an integer.    """    if n.bit_length() < 1024:  # float(n) safe from overflow        a = int(round(n**(1/3.)))        a = (2*a + n//a**2)//3  # Ensure a >= floor(cbrt(n)).    else:        a = 1 << -(-n.bit_length()//3)    while True:        d = n//a**2        if a <= d: return a        a = (2*a + d)//3

而且,借助这些工具

icbrt
,很容易将所有内容放在一起以将多维数据集的根计算到小数点后十位。在这里,为简单起见,我将结果输出为字符串,但您可以轻松构造一个
Decimal
实例。

def cbrt_to_ten_places(n):    """    Compute the cube root of `n`, truncated to ten decimal places.    Returns the answer as a string.    """    a = icbrt(n * 10**30)    q, r = divmod(a, 10**10)    return "{}.{:010d}".format(q, r)

输出示例:

>>> cbrt_to_ten_places(2)'1.2599210498'>>> cbrt_to_ten_places(8)'2.0000000000'>>> cbrt_to_ten_places(31415926535897932384626433)'315536756.9301821867'>>> cbrt_to_ten_places(31415926535897932384626433**3)'31415926535897932384626433.0000000000'


转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/419885.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号