使用机器人开采 n 克矿物 - JPMC 面试问题

Question

使用机器人开采 n 克矿物，该机器人可以通过每天开采 1 克或每天创建另一个机器人来度过一天 - JPMC 面试问题

新创建的机器人需要一天后才能开始工作
开采 n 克矿物需要多少天/多少台机器人？

例如：输入 1 输出 1 输入 4 输出 3

Answer 1

机器人的最佳产出完全取决于它还能工作多少天。我们可以很容易地给出最佳循环：

def optimal_output(days):
    if days == 0: return 0
    if days == 1: return 1
    return max(optimal_output(days - 1) + 1,  # Mine.
               optimal_output(days - 1) + optimal_output(days - 2)) # Create robot.

我们可以看一下前几项：

>>> [optimal_output(n) for n in range(10)]
[0, 1, 2, 3, 5, 8, 13, 21, 34, 55]

嘿，这就是斐波那契数列。这是有道理的，因为在第 3 天之后，我们发现 optimal_output(days - 1) + 1 永远不会高于 optimal_output(days - 1) + optimal_output(days - 2)，我们只剩下斐波那契的复发。

以上是假设第 1 天组装的机器人只能在第 3 天开始工作。如果它能在第 2 天开始工作，我们有以下循环：

def optimal_output(days):
    if days == 0: return 0
    if days == 1: return 1
    return max(optimal_output(days - 1) + 1,  # Mine.
               optimal_output(days - 1) + optimal_output(days - 1)) # Create robot.

这简化为 f(1) =、f(n) = 2f(n-1) 或者换句话说，2 的幂。

Answer 2

int findMinDaysUsingMath(int grain) {
    return (int) Math.ceil(Math.log(grain) / Math.log(2)) + 1;
}

使用机器人开采 n 克矿物 - JPMC 面试问题

Mine n grams of mineral using robot - JPMC Interview question

algorithm

data-structures

puzzle