问将小数转换为“漂亮”小数的优化算法

EN

查找“连分式近似”。维基百科在它的“连续分数”文章中有一个基本的介绍，但是有一些优化的算法可以在生成分数的同时生成近似值。

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

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

在下面，我将假设我们的小数落在0到1之间，这应该很简单，以适应更大的数字和负数。

也许最简单的做法是选择您认为可以接受的最大分母，然后创建一个介于0和1之间的分母小于或等于它们的分数列表。一定要避免任何可以简化的分数。显然，一旦你列出了1/2，你就不需要2/4了。你可以避免分数，可以通过使用欧几里德算法检查分子和分母的GCD是1来简化分数。一旦你有了你的清单。将这些值计算为浮点数(可能是双倍数，但数据类型显然取决于您选择的编程语言)。然后将它们插入到存储原始分数和分数的浮点计算的平衡二进制搜索树中。您只需执行一次此操作即可进行初始设置，因此n*log(n)时间(其中n是分数的数量)不是很多。

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