给定十进制数,找到给出整数结果的最小整数乘数

Question

最好用一个例子来描述问题.假设我的小数值为100.227273.

100.227273*X = Y.

我需要找到给出整数Y的最小正整数X.

Answer 1

如果100.227273只是一个近似值并且您想获得最佳有理逼近,请使用连续分数.

以100.227273为例.

1. 取整数部分(100).现在你得到100.227273 = 100 + 0.227273.
2. 反转0.227273得到4.39999(4.4？).
3. 重复步骤1,直到您对错误感到满意为止.

所以你得到了

                       1
100.227273 = 100 + —————————
                         1
                   4 + —————
                           1
                       2 + —
                           2

简化此表达式以获得2205/22.

Answer 2

1000000/gcd(1000000,227273).也称为lcm(1000000,227273)/227273.在这种情况下,100万.

您想要做的是将0.227273变成最简单形式的分数.您正在寻找的数字是该分数的分母.由于227273/1000000已经是最简单的形式,你已经完成了.但如果你的输入是100.075,那么75/1000不是最简单的形式.最简单的形式是3/40,因此X的解决方案是40.

作为优化,你可以简化计算,因为你知道起始分母是10的幂,所以它的唯一素因子是2和5.所以你需要在分子中寻找的是2和5的可分性,比欧几里德的算法更容易.当然,如果你已经有gcd和/或lcm的实现,那么这是你的努力,而不是更少.

在得到结果时要记住,浮点数通常不能精确地表示小数部分.因此,一旦得到数学上正确的答案,当您进行浮点乘法时,它不一定会给出整数答案.另一方面,当然这个问题仅适用于您感兴趣的数字的有限十进制表达式.

如果您首先将数字作为商,那么您需要直接找到其最简单形式的分母,而不是将其转换为十进制并截断它.例如,要解决数字"6和三分之一"的问题,答案是3,而不是10的任何幂.如果输入是"2的平方根",那么X没有解.

嗯,实际上,具有您需要的属性的最小整数X是0,但我认为您不是那个意思;-)