algorithm - 如果数字是小数，如何检查某个数字是否可以表示为 x^y？

Question

我在编码面试中被问到这个问题。

如果一个数字是整数，如 16、25、100，我们可以使用对数或质因数或其他方式推导该数字是否可以用 x^y 表示。但是，如果数字是 0.4 或 0.002 或任何其他十进制数，该如何处理这种情况。

请帮我找到一个方法。谢谢:)

Answer 1

如果x是一个整数并且y是一个非负整数，x^y是一个整数(如果我们忽略不明确的情况 0^0 )。如果我们允许 y为负整数，则x^y也表示为 1/ (x^(-y))这是一个非负整数的倒数(如果我们忽略 0^-1 等未定义的情况)。

因此，如果您给定值 x^y不是整数，检查它的倒数。那必须是一个整数并且可以分解成 x^y积分x和 y .

我在这里假设 x和 y必须是整数。如果没有，您可以使用 a^1其中 a是期望的结果。例如，如果给定 0.4 , 你可以使用 0.4^1 .但是如果我们对 x 有整数限制和 y ，你看0.4不是整数，2.5 也不是，它的倒数。所以这个不能分解。给0.002我们试试它的倒数500然后看它唯一的分解就是500^1 , 所以只能分解0.002是500^-1 .

---

如果我在编码面试中被问到这个问题，我会再提出一点。一些数字，例如 0.002 , 不能在标准浮点变量中准确表示。因此，即使在预期的情况下，取其倒数也可能不会得到整数。例如，x=1/49 就是这样。 : 在 Python 3.6.4 中取其倒数不给出 49 .一个更好的例子是 x=0.00016 .它的倒数应该是6250但它实际上是 6249.999999999999 .所以分解这些数字是比较困难的。这会影响数字输入例程的方式。例如，在 Python 中，当“十进制数”不是作为浮点值输入，而是作为字符串或 decimal 中的 Decimal 值输入时，可以获得最佳结果。模块或来自 fractions 的分数值模块。这使十进制数的值保持准确，并且例程可以正确检查倒数是否为整数。