至少有两半的选民

Question

我的一位前学生给我发了一条关于他在申请初级开发人员工作时遇到的面试问题的消息.

在模拟教室选举中,有两名候选人竞选总统.考虑到选民的两个百分比,找出课堂上可能选民的数量最少.

例子:

输入:50.00,50.00
输出:2

输入:25.00,75.00
输出:4

输入:53.23,46.77
输出:124 //第一个值,1138错了.感谢Loïc的正确价值

注意:输入百分比的总和始终为100.00%,小数点后两位

最后一个例子让我挠头.这是我第一次听说这个问题,我对如何解决这个问题感到很难过.

编辑:我打电话给我的学生解决了这个问题,并告诉我他不确定最后一个值.他说,我引用,"这是一个荒谬的大数字输出":(对不起!我应该在网上发布之前研究更多〜我猜测9,797是最后一个例子的输出虽然..

Answer 1

您可以使用选民百分比的最佳有理近似值来计算这些值.维基百科描述了如何从连续分数中获得这些值(可以使用欧几里德算法计算这些值).期望的结果是第一近似值,其在预期值的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%

我们在第3和第4个收敛点之前有额外值的原因是它们的最后一个项(分别为7和4)大于1,所以我们必须测试最后一个项递减的近似值.

期望的结果是第一个值的分母,它绕到所需的值,在这个花瓶中是62.

样品Ruby实现可在这里(使用该公式从维基百科页面在这里,所以它看起来上面的例子略有不同).