在SPOJ`CUBERT`中错误的回答 [英] Wrong answer in SPOJ `CUBERT`

问题描述

我的解决方案出现错误答案，导致此问题 a>在SPOJ上。

这个问题要求计算一个整数的立方根（可以长达150个数字），并输出截尾为10个小数位的答案。 b $ b它还要求计算答案模10中所有数字的总和作为校验和值。

下面是确切的问题陈述：

lockquote

你的任务是计算给定正整数的立方根。
我们不记得为什么我们需要这个，但是它有一个与公主，一个年轻的农民，亲吻和一个王国的一半相同的东西
（一个巨大的，我们可以保证你）。

编写一个程序来解决这个关键的任务。输入

输入以包含单个整数的行开始t< / p> ; = 20，
个测试用例。 t测试用例如下。

接下来的行由大正整数150个十进制
数字组成。每个数字都在输入文件的独立行上。
输入文件可能包含空行。数字可以在前面，
之后是空格，但是不要超过255个字符。

输出

对于输入文件中的每个数字，你的程序应该输出一行
，由两个由单个空格分隔的值组成。第二个值
是给定数字的立方根，在
第十个小数位之后被截断（不是四舍五入！）。第一个值是立方体根的所有打印的
数字的校验和，计算为打印的数字
模10的总和。

示例

输入：

5

1

8 b
$ b $ 1000

2 33076161 $ / $>

输出：

1 1.0000000000

2 2.0000000000

1 10.0000000000

0 1.2599210498

6 321.0000000000

这是我的解决方案：


$ b $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ 3）
＃第一轮到11位小数
num_cube_root =％.11f％（num_cube_root）
＃然后删除最后一个十进制数字
＃以实现截断10小数位
num_cube_root = str（num_cube_root）[0：-1]

num_cube_root_sum = 0
for num_cube_root：
如果数字！='。'：
num_cube_root_sum + = int（数字）
num_cube_root_sum％= 10

返回（num_cube_root_sum，num_cube_root）

$ b def main（）：
＃测试用例的数量
t = int（input（））
while t：
t - = 1
num = input（）。strip（）
＃如果一行为空，则忽略
如果不是的话：
t + = 1
continue

$ num = int（num）
ans = foo（num）
print（str（ans [0]）++ ans [1]）$ ​​b

$ b if __name__ =='__main__'：
main（）

示例：现场演示。

任何人都可以告诉这个解决方案有什么问题吗？

解决方案

您的解决方案有两个问题，都与使用浮点运算有关。第一个问题是，Python float s只包含大约16位重要的精度十进制数字，所以只要您的答案需要超过16位有效数字（所以超过6在点之前的数字和10个数字之后），你很少希望得到正确的结尾数字。第二个问题更为微妙，甚至会影响 n 的小值。这就是说，由于双舍入，您将舍入到十一位十进制数字，然后删除最后一位数字的方法遭受潜在的错误。 。举一个例子，取 n = 33 。 n 的立方体根到20个小数位左右是：

  3.20753432999582648755 ... 
  

当点数后四舍五入到11位时， / p>

  3.20753433000 
  

现在放弃最后一位数字给出 3.2075343300 ，这不是你想要的。问题是这个小数点后11位可能会影响第11位数字左边的位数。

那么你能做些什么来解决这个问题呢？那么，你可以完全避免浮点，并将其减少到一个纯整数的问题。我们需要一些整数的立方体根（ n ）到10个小数位（舍去最后一个位置）。这相当于将 10 ** 30 * n 的立方根再次舍入，然后将结果除以 10 ** 10 。所以这里最重要的任务是计算任何给定整数的立方根的底部 n 。我无法找到关于计算整数立方体根目前的任何现有堆栈溢出的答案（在Python中仍然较少），所以我认为值得展示如何做到这一点。

计算整数的立方体根源变得相当简单（借助一点点数学）。有各种可能的方法，但是一种既高效又容易实现的方法是使用纯整数版本的牛顿 - Raphson 方法。在实数上，牛顿用于求解方程的方法 x ** 3 = n 取近似值 x 给立方体根 n ，迭代返回一个改进的近似值。所需的迭代是：

$ $ $ $ code $ 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 =无）：

给定一个正整数n ，找到n的立方体根的底部
 
 Args：
n：正整数
 initial_guess：正整数，可选如果给出，这是
初始值猜测是立方根的底面，它必须大于
大于或等于floor（cube_root（n））
 
返回：
 n，作为一个整数

a = initial_guess如果initial_guess不是None其他n 
而真：
d = n // a ** 2 
如果a <= d：
返回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 至少是地板（CBRT（n））的。此外，每次迭代都会产生一个小于原来值的 a ，所以我们的迭代保证最终收敛到 floor（cbrt（n） ）。为了证明这些事实，请注意，当我们输入 while 循环时，有两种可能：

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 ，这又来自应用于 a的 AM-GM不等式。 code> a 和 n / a ** 2 ：这三个量的几何平均值正好 n 的立方根，因此算术平均值必须至少<$ em $ c $ n的立方根。所以我们的循环不变被保留下来进行迭代。

a ：因为我们假设 a 大于立方根， n / a ** 2 <一个，而且（2a + n / a ** 2）/ 3 比<$小 （（2a + n / a ** 2）/ 3） c 一个。这保证了我们在每次迭代中都能够取得进步。 小于或等于 n 的立方根。然后根据上面建立的循环不变量，我们也知道 a> = floor（cbrt（n）） （n））的。所以我们完成了： a 是我们之后的值。而while循环在这个时候退出，因为 a< = n // a ** 2 。




上面的代码有几个问题。首先，从最初的 n 猜测开始是低效的：代码将花费其前几次迭代（粗略地）将当前值分成 a by 3 ，直到它进入解决方案的邻域。初始猜测（以及Python中可以轻松计算的）的更好选择是使用超过 n 的立方根的两个第一次方。 b
$ b

  initial_guess = 1<< - （ -  n.bit_length（）// 3）
  

更好的是，如果 n 足够小，以避免溢出，是使用浮点算法来提供初始猜测，如：



  initial_guess = int（round（n **（1/3。）））
  



但是这带来了我们的第二个问题：我们的算法的正确性要求初始猜测不小于实际的整数立方体根，并且当 n 变大我们不能保证上面的基于浮点数的 initial_guess （尽管对于足够小的 n ，我们可以）。幸运的是，对于任何正整数 a 都有一个非常简单的解决方法，如果我们执行一次迭代，我们总是会得到一个至少为（code> floor（cbrt（a）））（使用上面我们使用的相同的AM-GM参数）。因此，我们所要做的就是在开始测试收敛之前至少执行一次迭代。





考虑到这一点，下面是上述代码的更高效的版本： / p>



  def icbrt（n）：

给定一个正整数n， n的立方根
 
参数：
n：正整数
 $ b返回：
 n的立方根的底面，整数。 

如果n.bit_length（）< 1024：＃float（n）safe from overflow 
a = int（round（n **（1/3。）））
a =（2 * a + n // a ** 2）// 3＃确保> = floor（cbrt（n））。 
 else：
 a = 1<< - （ -  n.bit_length（）// 3）
 
而真：
d = n // a ** 2 
如果a <= d：
返回
a =（2 * a + d）// 3 
  

c $ c> icbrt ，很容易将所有东西都放在一起来计算立方体根到十个小数位。在这里，为了简单起见，我将结果输出为一个字符串，但是您可以轻松地构造一个 Decimal 实例。

  def cbrt_to_ten_places（n）：

计算`n`的立方根，截断到十位小数
 
 

a = icbrt（n * 10 ** 30）
q，r = divmod（a，10 ** 10）
 return格式（q，r）
  

输出示例：

 >>> cbrt_to_ten_places（2）
'1.2599210498'
>>> cbrt_to_ten_places（8）
'2.0000000000'
>>> cbrt_to_ten_places（31415926535897932384626433）
'315536​​756.9301821867'
>>> cbrt_to_ten_places（31415926535897932384626433 ** 3）
'31415926535897932384626433.0000000000'
  




I am getting a Wrong Answer for my solution to this problem on SPOJ.

The problem asks to calculate the cube root of an integer(which can be upto 150 digits long), and output the answer truncated upto 10 decimal places.
It also asks to calculate the sum of all the digits in the answer modulo 10 as a 'checksum' value.

Here is the exact problem statement:

Your task is to calculate the cube root of a given positive integer. We can not remember why exactly we need this, but it has something in common with a princess, a young peasant, kissing and half of a kingdom (a huge one, we can assure you).

Write a program to solve this crucial task.

Input

The input starts with a line containing a single integer t <= 20, the number of test cases. t test cases follow.

The next lines consist of large positive integers of up to 150 decimal digits. Each number is on its own separate line of the input file. The input file may contain empty lines. Numbers can be preceded or followed by whitespaces but no line exceeds 255 characters.

Output

For each number in the input file your program should output a line consisting of two values separated by single space. The second value is the cube root of the given number, truncated (not rounded!) after the 10th decimal place. First value is a checksum of all printed digits of the cube root, calculated as the sum of the printed digits modulo 10.

Example

Input:
5
1

8

1000

2 33076161

Output:
1 1.0000000000
2 2.0000000000
1 10.0000000000
0 1.2599210498
6 321.0000000000

Here is my solution:

from math import pow


def foo(num):
    num_cube_root = pow(num, 1.0 / 3)
    # First round upto 11 decimal places
    num_cube_root = "%.11f" % (num_cube_root)
    # Then remove the last decimal digit
    # to achieve a truncation of 10 decimal places
    num_cube_root = str(num_cube_root)[0:-1]

    num_cube_root_sum = 0
    for digit in num_cube_root:
        if digit != '.':
            num_cube_root_sum += int(digit)
    num_cube_root_sum %= 10

    return (num_cube_root_sum, num_cube_root)


def main():
    # Number of test cases
    t = int(input())
    while t:
        t -= 1
        num = input().strip()
        # If line empty, ignore
        if not num:
            t += 1
            continue

        num = int(num)
        ans = foo(num)
        print(str(ans[0]) + " " + ans[1])


if __name__ == '__main__':
    main()

It is working perfectly for the sample cases: Live demo.

Can anyone tell what is the problem with this solution?

解决方案

Your solution has two problems, both related to the use of floating-point arithmetic. The first issue is that Python floats only carry roughly 16 significant decimal digits of precision, so as soon as your answer requires more than 16 significant digits or so (so more than 6 digits before the point, and 10 digits after), you've very little hope of getting the correct trailing digits. The second issue is more subtle, and affects even small values of n. That's that your approach of rounding to 11 decimal digits and then dropping the last digit suffers from potential errors due to double rounding. For an example, take n = 33. The cube root of n, to 20 decimal places or so, is:

3.20753432999582648755...

When that's rounded to 11 places after the point, you end up with

3.20753433000

and now dropping the last digit gives 3.2075343300, which isn't what you wanted. The problem is that that round to 11 decimal places can end up affecting digits to the left of the 11th place digit.

So what can you do to fix this? Well, you can avoid floating-point altogether and reduce this to a pure integer problem. We need the cube root of some integer n to 10 decimal places (rounding the last place down). That's equivalent to computing the cube root of 10**30 * n to the nearest integer, again rounding down, then dividing the result by 10**10. So the essential task here is to compute the floor of the cube root of any given integer n. I was unable to find any existing Stack Overflow answers about computing integer cube roots (still less in Python), so I thought it worth showing how to do so in detail.

Computing cube roots of integers turns out to be quite easy (with the help of a tiny bit of mathematics). There are various possible approaches, but one approach that's both efficient and easy to implement is to use a pure-integer version of the Newton-Raphson method. Over the real numbers, Newton's method for solving the equation x**3 = n takes an approximation x to the cube root of n, and iterates to return an improved approximation. The required iteration is:

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

In the real case, you'd repeat the iteration until you reached some desired tolerance. It turns out that over the integers, essentially the same iteration works, and with the right exit condition it will give us exactly the correct answer (no tolerance required). The iteration in the integer case is:

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

(Note the uses of the floor division operator // in place of the usual true division operator / above.) Mathematically, a_next is exactly the floor of (2*a + n/a**2)/3.

Here's some code based on this iteration:

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

And some example uses:

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

There are a couple of annoyances and inefficiencies in icbrt_v1 that we'll fix shortly. But first, a brief explanation of why the above code works. Note that we start with an initial guess that's assumed to be greater than or equal to the floor of the cube root. We'll show that this property is a loop invariant: every time we reach the top of the while loop, a is at least floor(cbrt(n)). Furthermore, each iteration produces a value of a strictly smaller than the old one, so our iteration is guaranteed to eventually converge to floor(cbrt(n)). To prove these facts, note that as we enter the while loop, there are two possibilities:

Case 1. a is strictly greater than the cube root of n. Then a > n//a**2, and the code proceeds to the next iteration. Write a_next = (2*a + n//a**2)//3, then we have:

• a_next >= floor(cbrt(n)). This follows from the fact that (2*a + n/a**2)/3 is at least the cube root of n, which in turn follows from the AM-GM inequality applied to a, a and n/a**2: the geometric mean of these three quantities is exactly the cube root of n, so the arithmetic mean must be at least the cube root of n. So our loop invariant is preserved for the next iteration.

• a_next < a: since we're assuming that a is larger than the cube root, n/a**2 < a, and it follows that (2a + n/a**2) / 3 is smaller than a, and hence that floor((2a + n/a**2) / 3) < a. This guarantees that we make progress towards the solution at each iteration.

Case 2. a is less than or equal to the cube root of n. Then a <= floor(cbrt(n)), but from the loop invariant established above we also know that a >= floor(cbrt(n)). So we're done: a is the value we're after. And the while loop exits at this point, since a <= n // a**2.

There are a couple of issues with the code above. First, starting with an initial guess of n is inefficient: the code will spend its first few iterations (roughly) dividing the current value of a by 3 each time until it gets into the neighborhood of the solution. A better choice for the initial guess (and one that's easily computable in Python) is to use the first power of two that exceeds the cube root of n.

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

Even better, if n is small enough to avoid overflow, is to use floating-point arithmetic to provide the initial guess, with something like:

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

But this brings us to our second issue: the correctness of our algorithm requires that the initial guess is no smaller than the actual integer cube root, and as n gets large we can't guarantee that for the float-based initial_guess above (though for small enough n, we can). Luckily, there's a very simple fix: for any positive integer a, if we perform a single iteration we always end up with a value that's at least floor(cbrt(a)) (using the same AM-GM argument that we used above). So all we have to do is perform at least one iteration before we start testing for convergence.

With that in mind, here's a more efficient version of the above code:

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

And with icbrt in hand, it's easy to put everything together to compute cube roots to ten decimal places. Here, for simplicity, I output the result as a string, but you could just as easily construct a Decimal instance.

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)

Example outputs:

>>> 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'

这篇关于在SPOJ`CUBERT`中错误的回答的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！