引用符号的加法算法
我正在努力理解Quote Notation，并试图用Python语言构建一个简单的报价计算器。我有浮点数和浮点数的转换，现在正在尝试理解一些算法。在尝试编写一个可以将两个引号加在一起的函数时，我发现自己迷路了。维基百科的链接条目写着“在引用符号中添加，只是添加”，这是令人沮丧的无用之处。即使在他们给出的例子中，我也找不到一种将引号加在一起而不将它们转换回浮点数的方法，这就违背了目的。
什么算法可以将两个报价数字相加，而不转换为浮点数？谢谢!
回答 1
Stack Overflow用户
发布于 2018-06-11 09:22:16
“要添加，只需添加”是一个正确的描述，但遗漏了一个非常重要的终止条件。(它也没有明确指出数字必须首先在基点对齐的事实，可能是因为原始论文的作者认为这个过程隐含在“只加”中。)
回想一下，引号前面的数字应该被认为是向左无限重复。要将两个数字相加，我们只需按正常方式从右向左操作。
如果我们天真地这样做，算法将永远不会结束，因为隐式表示是无限的。但它的输出最终必须开始循环，因为它实际上是一个有限状态机。也就是说，一旦我们在引号的左侧，sum算法的状态完全由以下因素决定：
- 第一个加数中的索引；
- 第二个加数中的索引；
- 和进位(0或1)。
可能状态的数量至多是两个周期长度的乘积的两倍(更准确地说，它是周期长度的最小公倍数的两倍)。由于存在有限数量的状态，因此某些状态必须重复，这意味着序列的其余部分是循环的。
您可以使用类似于tortoise and hare算法的方法来查找重复状态，所需的额外内存为O(1)。然而，这并没有找到最短的表示。一旦你找到一个循环前缀，然后你必须通过尽可能右移该循环来归一化这个数字。(如果第一个数字与引号后的数字相同，则可以将循环向右移动；如果是这样，请删除第一个数字，将引号向右移动一个位置，然后重复操作，直到数字不同为止。)
https://stackoverflow.com/questions/50789040
复制相似问题