python - 用于分数点的 Google foobar gearing_up_for_destruction

Question

我从谷歌的编码问题中提出了这个问题，并试图解决它，但在某些特定情况下被卡住了。

Challenge

As Commander Lambda's personal assistant, you've been assigned the task of configuring the LAMBCHOP doomsday device's axial orientation gears. It should be pretty simple - just add gears to create the appropriate rotation ratio. But the problem is, due to the layout of the LAMBCHOP and the complicated system of beams and pipes supporting it, the pegs that will support the gears are fixed in place.

The LAMBCHOP's engineers have given you lists identifying the placement of groups of pegs along various support beams. You need to place a gear on each peg (otherwise the gears will collide with unoccupied pegs). The engineers have plenty of gears in all different sizes stocked up, so you can choose gears of any size, from a radius of 1 on up. Your goal is to build a system where the last gear rotates at twice the rate (in revolutions per minute, or rpm) of the first gear, no matter the direction. Each gear (except the last) touches and turns the gear on the next peg to the right.

Given a list of distinct positive integers named pegs representing the location of each peg along the support beam, write a function answer(pegs) which, if there is a solution, returns a list of two positive integers a and b representing the numerator and denominator of the first gear's radius in its simplest form in order to achieve the goal above, such that radius = a/b. The ratio a/b should be greater than or equal to 1. Not all support configurations will necessarily be capable of creating the proper rotation ratio, so if the task is impossible, the function answer(pegs) should return the list [-1, -1].

For example, if the pegs are placed at [4, 30, 50], then the first gear could have a radius of 12, the second gear could have a radius of 14, and the last one a radius of 6. Thus, the last gear would rotate twice as fast as the first one. In this case, pegs would be [4, 30, 50] and answer(pegs) should return [12, 1].

The list pegs will be given sorted in ascending order and will contain at least 2 and no more than 20 distinct positive integers, all between 1 and 10000 inclusive.

这是我的解决方案

def get_last_radius(pegs, radius):
  for i in range(1, len(pegs)):
    pegs_range = pegs[i] - pegs[i - 1]
    radius = pegs_range - radius

  return radius

def get_first_radius(pegs):
  first_range = pegs[1] - pegs[0]
  for first_radius in range(2, first_range, 2):
    last_radius = get_last_radius(pegs, first_radius)
    if first_radius == last_radius * 2:
      return [first_radius, 1]
  return [-1, -1]

我假设不可能有任何浮点数，这就是为什么我返回 1 作为所有情况的分母。但是搜索了一下，我找到了这个帖子

Google foobar gearing_up_for_destruction

哪种告诉有浮点数的情况，但我仍然找不到。

例如，如果第一个半径是*.x，另一个应该是*.ywhere x + y = 1。所以对于第三档，它应该再次被*.x放置在INTEGER位置。有人可以显示一个带有浮动数字的特定测试用例吗？

标签： pythonalgorithm

Answer 1

您的解决方案不符合要求（我一开始也没有）。
以下是您可能遗漏的内容：
1.The engineers have plenty of gears in all different sizes stocked up, so you can choose gears of any size, from a radius of 1 on up.
这意味着，当您找到第一个齿轮半径时，您必须再次循环查看是否有任何齿轮的半径 < 1。
2.return [first_radius, 1] 半径并不总是整数。明确指出returns a list of two positive integers a and b representing the numerator and denominator of the first gear's radius in its simplest form in order to achieve the goal above, such that radius = a/b。这是返回半径不是整数的测试用例：[25,105,145,170]，它返回[130, 3].
为了解决这个问题，你需要数学。尝试找到 n = 2, 3, 4, 5...（输入列表的长度）的最后一个齿轮半径，您将看到模式。祝你好运。