algorithm - 从数字中减去数字的数字，直到达到 0

Question

有人可以帮我解决这个问题吗？

我们有一个大数字(19 位数字)，在一个循环中，我们从数字本身中减去该数字的一位数字。

我们会继续这样做，直到数字达到零。我们要计算使给定数字达到零的最小减法次数。

算法必须在两秒内快速响应 19 位数字 (10^19)。例如，提供 36 的输入将得到 7:

1. 36 - 6 = 30
2. 30 - 3 = 27
3. 27 - 7 = 20
4. 20 - 2 = 18
5. 18 - 8 = 10
6. 10 - 1 =  9
7.  9 - 9 =  0

谢谢。

Answer 1

达到零的最小减法次数使这个，我怀疑，一个非常棘手的问题，一个需要大量回溯潜在解决方案的问题，使得它对于您的时间限制来说可能太昂贵了.

但是您应该做的第一事情是健全性检查。因为最大的数字是 9 , 一个 19 位数字大约需要 10<sup>18</sup>减法达到零。编写一个简单的程序，从 10<sup>19</sup> 中连续减去 9直到小于十。如果您不能在两秒内完成，那您就有麻烦了。

例如，下面的程序^(a):

#include <stdio.h>

int main (int argc, char *argv[]) {
    unsigned long long x = strtoull(argv[1], NULL, 10);
    x /= 1000000000;
    while (x > 9)
        x -= 9;
    return x;
}

当使用参数 10000000000000000000 运行时( 10<sup>19</sup> )，即使在 gcc 也需要一个半时钟时间(和 CPU 时间，因为它都是计算)疯狂的优化级别 -O3 :

real    0m1.531s
user    0m1.528s
sys     0m0.000s

那是在 while 之前的十亿除数。循环，这意味着全部迭代次数大约需要 48 年。

因此，强力方法在这里无济于事，您需要的是一些严肃的数学分析，这可能意味着您应该在 https://math.stackexchange.com/ 上发布类似的问题。让数学天才有机会。

---

^(a) 如果您想知道为什么我从用户那里获取值而不是使用常量 10000000000000000000ULL ，这是为了防止gcc从在编译时计算它并将其变成类似的东西:

mov  $1, %eax

同上 return x这将阻止它注意到我没有使用 x 的最终值从而完全优化循环。