language-agnostic - 选民最少，分为两半

Question

我的一位以前的学生给我发来了一封有关他在申请初级开发人员时遇到的面试问题的信息。

There are two candidates running for president in a mock classroom election. Given the two percentages of voters, find out the least amount of possible voters in the classroom.

Examples:

Input: 50.00,50.00
Output: 2

Input: 25.00,75.00
Output: 4

Input: 53.23, 46.77
Output: 124 // The first value, 1138 was wrong. Thanks to Loïc for the correct value

Note: The sum of the input percentages are always 100.00%, two decimal places

最后一个例子让我挠头。这是我第一次听说此问题，我对如何解决这个问题感到困惑。
编辑:我调用我的学生关于这个问题，并告诉我他不确定最后的值。他说，我引用“这是一个非常荒谬的数字输出” :(对不起!在将其在线发布之前，我应该做更多的研究〜我猜最后一个示例的输出是9,797。

Answer 1

您可以使用投票者百分比的best rational approximations计算这些值。 Wikipedia描述了如何从continued fraction获得这些值(可以使用euclidean algorithm计算这些值)。期望结果是第一近似值，其在期望值的0.005％以内。

这是一个53.23％的示例:

10000 = 1 * 5323 + 4677
5323  = 1 * 4677 + 646
4677  = 7 * 646  + 155
646   = 4 * 155  + 26
155   = 5 * 26   + 25
26    = 1 * 25   + 1
25    = 25* 1    + 0

Approximations:
1:   1 / 1
 -> 1 = 100%
2:   1 / (1 + 1/1) 
 -> 1/2 = 50%
2.5: 1 / (1 + 1 / (1 + 1/6))
 -> 7/1 = 53.75%
3:   1 / (1 + 1 / (1 + 1/7))
 -> 8/15 = 53.33%
3.5: 1 / (1 + 1 / (1 + 1 / (7 + 1/3)))
 -> 25/47 = 53.19%
4:   1 / (1 + 1 / (1 + 1 / (7 + 1/4)))
 -> 33/62 = 53.23%

我们在第三个和第四个收敛点之前有额外的值的原因是，它们的最后一项(分别为7和4)大于1，因此我们必须在减少最后一项的情况下测试近似值。

所需结果是第一个值的分母，该分母四舍五入为所需值，在此花瓶中为62。

示例Ruby实现可用的 here(使用来自Wikipedia页面 here的公式，因此它与上面的示例略有不同)。