使用机器人开采n克矿物质-JPMC采访问题

问题描述 投票:0回答:1

使用机器人可以开采一天的矿物,每天可以开采1gm或每天创建另一个机器人来度过一天-JPMC采访问题

  • 新创建的机器人只能在一天后开始工作。
  • 需要多少天/多少机器人才能开采n克矿物质?

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

algorithm data-structures puzzle
1个回答
0
投票

机器人的最佳输出量完全取决于它可以工作多少天。我们可以很容易地得到最佳的复发率:

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),而我们只剩下斐波那契的重复出现。

© www.soinside.com 2019 - 2024. All rights reserved.