6

我没有将任意小数转换为精确分数（例如 323527/4362363），而是尝试转换为常见的易于识别（就人类可读性而言）的数量，例如 1/2、1/4、1/8等等

除了使用一系列 if-then、小于/等于等比较之外，是否有更优化的技术来做到这一点？

编辑：在我的特殊情况下，近似值是可以接受的。这个想法是 0.251243 ~ 0.25 = 1/4 - 在我的用例中，这“足够好”，就快速指标而言，后者更适合人类可读性（不用于计算，仅用作显示数字）。

4

5 回答 5

7

查找“连续分数逼近”。维基百科在其“连分数”一文中有基本介绍，但有优化算法在生成分数的同时生成近似值。

然后选择一些停止启发式，分母大小和近似值的组合，当你“足够接近”时。

于 2011-01-13T03:32:16.113 回答
3

您可以使用欧几里得算法来获得枚举数和分母之间的最大公约数并将它们除以它。

于 2011-01-13T03:25:49.883 回答
0

在下文中，我将假设我们的小数介于 0 和 1 之间。将其应用于更大的数字和负数应该很简单。

可能最简单的做法是选择您认为可接受的最大分母，然后创建一个介于 0 和 1 之间的分数列表，这些分数的分母小于或等于它们。一定要避免任何可以简化的分数。显然，一旦你列出了 1/2，你就不需要 2/4。您可以通过检查分子和分母的 GCD 是否为 1 来使用 Euclid 算法来避免可以简化的分数。一旦你有了你的清单。将它们评估为浮点数（可能是双精度数，但数据类型显然取决于您选择的编程语言）。然后将它们插入到平衡二叉搜索树中，该树存储原始分数和分数的浮点评估。

然后，每当你得到一个数字时，只需搜索树以找到最接近它的数字，它在搜索树中。请注意，这比搜索精确匹配稍微复杂一些，因为您要查找的节点可能不是叶节点。因此，当您遍历树时，请记录您访问过的最近的值节点。一旦到达叶节点并将其与您访问过的最接近的值节点进行比较，您就完成了。无论您最接近哪个，它的分数就是您的答案。

于 2011-01-13T03:34:58.270 回答
0

这是一个建议：假设您的起始分数是 p/q

  1. 计算 r = p/q 作为有理（浮点）值（例如 r = float(p)/float(q)）

  2. 计算四舍五入的小数 x = int(10000*r)

  3. 计算 x 和 10000 的 GCD（最大公分母）： s = GCD(x, 10000)

  4. 将结果表示为 m / n，其中 m = x/s 和 n = y/s（您的示例计算为 371 / 5000）

通常，1000 的所有分母都是人类可读的。

当值更接近更简单的情况（例如 1/3）时，这可能不会提供最佳结果。但是，我个人发现 379/1000 比 47/62（这是最短的小数表示）更具人类可读性。不过，您可以添加一些例外来微调此类过程（例如，计算 p/GCD(p,q) 、 q/GCD(p,q) 并在其中一个是单个数字值时接受它，然后再继续此方法）

于 2011-01-13T04:21:06.153 回答
0

非常愚蠢的解决方案，仅用于“预览”分数：

因子 = 1/小数
结果 = 1/轮（因子）
乘数 = 1

而（结果= 1）{
  乘数 = 乘数 * 10
  结果 = (1 * mult)/(Round(mult * factor))
}

结果 = 简化_with_GCD（结果）

祝你好运！

于 2011-01-14T12:34:44.753 回答