拆分数字所采取的步骤数

Question

我无法理解这个：

假设我有一个数字 9。我想知道拆分它所需的最小步骤，以便没有数字大于 3。

我一直认为最有效的方法是每次循环减半。所以，9 -> 4,5 -> 2,2,5 -> 2,2,2,3 所以总共 3 个步骤。但是，我刚刚意识到一个更聪明的方法：9 -> 3,6 -> 3,3,3 这只是 2 个步骤...

经过一番研究，步数实际上是(n-1)/target，在我的例子中target=3。

有人可以向我解释一下这种行为吗？

Answer 1

每个 n 都可以被认为是一个优先级队列，由 \lfloor n/target \rfloor 目标元素放在队列中的第一个元素和一个值为 n%target 的元素组成。每次从队列中删除一个元素时，都会将其放回队列中。删除除最后一个元素之外的所有元素：您已经清楚地删除了 \lfloor (n-1)/target \rfloor 元素。如果最后一个元素小于或等于目标，我们就完成了。如果它大于目标，我们就有矛盾了。因此，在 \lfloor (n-1)/target \rfloor 步骤之后，我们有一个仅由小于或等于 target 的元素组成的队列。

Answer 2

如果我们想将一根长度 L 的木棍切成不大于 S 的块，我们需要 ceiling(L/S) 块。每次我们进行新的切割时，我们都会将块数增加 1。切割的顺序无关紧要，重要的是切割的位置。例如，如果我们想把一根长度为 10 的棍子折断成大小为 2 或更小的碎片：

 -------------------
0 1 2 3 4 5 6 7 8 9 10

我们应该在以下地方进行切割：

 ---|---|---|---|---
0 1 2 3 4 5 6 7 8 9 10

并且任何切割顺序都可以，只要这些是切割的内容即可。另一方面，如果我们先把它分成两半：

 ---------|---------
0 1 2 3 4 5 6 7 8 9 10

我们做了一个不属于最佳解决方案的削减，我们浪费了时间。

Answer 3

我真的很喜欢@user2357112 对为什么减半不是正确的第一步的解释，但我也喜欢代数，你可以用归纳法证明 ceil(n / target) - 1 是最优的。

让我们先证明一下，您总是可以在 ceil(n / target) - 1 步内完成。

如果n <= target，显然不需要任何步骤，所以公式有效。假设n > target。将 n 拆分为 target 和 n - target（1 步）。通过归纳，n - target 可以分成 ceil((n - target)/target) - 1 步。因此总步数为

  1 + ceil((n - target) / target) - 1

= 1 + ceil(n / target) - target/target - 1

= ceil(n / target) - 1.

现在让我们证明您不能在少于 ceil(n / target) - 1 步的情况下完成。如果 n <= target，这是显而易见的。假设n > target，第一步是n -> a + b。通过归纳，a 至少需要 ceil(a / target) - 1 步，b 至少需要 ceil(b / target) - 1 步。因此所需的最少步数至少为

   1 + ceil(a / target) - 1 + ceil(b / target) - 1

>= ceil((a + b) / target) - 1                using ceil(x) + ceil(y) >= ceil(x + y)

 = ceil(n / target) - 1                      using a + b = n

拆分数字所采取的步骤数

Number of steps taken to split a number

algorithm

numbers