给定一个整数以及它在某个任意进制下的表示，目标是找到这个进制的基数。例如，如果数字是10，表示为000010，则进制应该是10。另一个例子：数字21的表示为0010101，那么进制就是2。再举一个例子：如果数字是6，表示为10100，则进制为sqrt(2)。有没有人知道如何解决这样的问题？
8个回答
12
___
\
number = /__ ( digit[i] * base ^ i )
number，你知道所有的数字 digit[i]，你只需要找出 base。解决这个方程是简单还是复杂留作练习。
- mouviciel
1
你正在忽略求和项中的基本属性。对于任意
I，都有 base^I > ∑(i = 0; i < I; ++i)(digit[i] * base^i)。 - Matthieu M.8
我不认为每个情况都有一个答案。而事实上我有理由这么想！=)
给定一个数字 x，在基数 b 中表示为
给定一个数字 x，在基数 b 中表示为
a_6 a_5 a_4 a_3 a_2 a_1，找到该基数意味着解决：a_6 b^5 + a_5 b^4 + a_4 b^3 + a_3 b^2 + a_2 b^1 + a_1 = x.
如Abel和Ruffini所示，这通常是不可能完成的。如果数字很短，你可能会更幸运，但如果涉及超过四位数，则公式变得越来越丑陋。
然而，有相当多的良好的近似算法。请参见此处。
- Jens
4
1然而，由于浮点类型具有有限的精度，因此可以通过数值方法解决这个问题。 - slacker
只有当你知道基数可以表示为浮点数时才能这样做。大多数基数都不能。 - Jens
+1 我非常确定在问题的第二个例子中，底数实际上是 -sqrt(2)。我不知道提问者是怎么丢失负号的，但是... - Ben Voigt
在这种情况下，目标是找到最接近正确答案的浮点数...懒人是对的。 - Ben Voigt
6
仅限整数，这并不难（我们可以列举出来）。
让我们看看 21 及其表示为 10101。
1 * base^4 <= 21 < (1+1) * base^4
让我们为一些进制生成数字：
base low high
2 16 32
3 81 162
更普遍地，我们将 N 表示为 ∑ ai * basei。考虑 I 是最大的幂次，使得 aI 非零，则有:
a[I] * base^I <= N < (a[I] + 1) * base^I # does not matter if not representable
# Isolate base term
N / (a[I] + 1) < base^I <= N / a[I]
# Ith root
Ithroot( N / (a[I] + 1) ) < base <= Ithroot( N / a[I] )
# Or as a range
base in ] Ithroot(N / (a[I] + 1)), Ithroot( N / a[I] ) ]
在整数基或如果您有已知可能的基础列表的情况下，可能性不会太多，因此我们可以尝试它们。
请注意，实际上获取
N / (a[I] + 1) 的 Ithroot 并从这里开始迭代可能更快，而不是计算第二个（这应该足够接近）...... 但是我需要对这种感觉进行数学审查。如果您真的没有任何想法（尝试找到浮点基）...... 好吧，我想这可能有点困难，但您始终可以根据相同的属性调整（包括一个或两个以上的术语）的不等式。
- Matthieu M.
4
1提问者的一个例子中，底数可以被表示为sqrt(2)。 - AakashM
由于所有数字都是严格非负的，若假设进制也是非负的，则它是一个具有唯一解的凸优化问题。您已经描述了一些好的、易于找到的边界，二分查找（可能使用插值而不是平均二分）可以继续求解。 - Ben Voigt
@Matthieu：去掉floor和ceil，你就可以使用非整数了，正如AakashM指出的那样。 - Ben Voigt
我没有意识到这点......已经有一段时间没有做过这个级别的数学了 oO - Matthieu M.
4
如果底数是整数，那么此算法应该能够找到基数，并且至少可以缩小非整数底数的选择范围：
- 设
- 您知道您的基数至少为
- 对于
这是一种蛮力方法，但它应该有效。您还可以通过在
还有一些其他的东西可能会帮助加速，特别是对于非整数基数的情况：请记住，正如一些人所提到的，任意基数下的数字可以扩展为一个多项式。
评估潜在基数时，您不需要转换整个数字。首先只需要转换最大项
另外，还有另一种快速消除潜在基数的方法。注意，您可以重新排列上述多项式表达式并得到：
你知道
- 设
N 为您的整数，R 为其在神秘基数下的表示。
- 找到 R 中最大的数字并将其称为 r。- 您知道您的基数至少为
r+1。- 对于
base == (r+1, r+2, ...)，让 I 表示在基数 base 下解释的 R
- 如果 I 等于 N，那么 base 就是您要找的神秘基数。
- 如果 I 小于 N，尝试下一个基数。
- 如果 I 大于 N，那么您的基数就在 base-1 和 base 之间。这是一种蛮力方法，但它应该有效。您还可以通过在
I 明显小于 N 时将 base 增加超过一来加快速度。还有一些其他的东西可能会帮助加速，特别是对于非整数基数的情况：请记住，正如一些人所提到的，任意基数下的数字可以扩展为一个多项式。
x = a[n]*base^n + a[n-1]*base^(n-1) + ... + a[2]*base^2 + a[1]*base + a[0]
评估潜在基数时，您不需要转换整个数字。首先只需要转换最大项
a[n]*base^n。如果这比x还要大，则您已经知道您的基数太大了。否则，逐个添加一个项（从最高有效位到最低有效位）。这样，您就不会在知道基数错误后浪费时间计算术语。另外，还有另一种快速消除潜在基数的方法。注意，您可以重新排列上述多项式表达式并得到：
(x - a[0]) = a[n]*base^n + a[n-1]*base^(n-1) + ... + a[2]*base^2 + a[1]*base
或者
(x - a[0]) = (a[n]*base^(n-1) + a[n-1]*base^(n-2) + ... + a[2]*base + a[1])*base
你知道
x和a[0]的值（即“个位数”，无论进制如何，你都可以解释它）。这使你得到了额外的条件，即(x - a[0])必须能够被base整除（因为所有的a[]值都是整数）。如果你计算(x - a[0]) % base并得到一个非零结果，则base不能是正确的进制。- bta
3
谢谢，我正在使用类似的方法，但是以不同的方式，明天我会发帖展示。 - evil.coder
你假设
base 是一个整数（在这种情况下问题是微不足道的）...我也犯了同样的错误，但是 @evil.coder 给出了一个例子，其中 base 是 sqrt(2)。 - Matthieu M.@Matthieu M.- 对于非整数基数，该算法将缩小搜索空间到两个相邻整数之间的区间。一旦您知道这些边界，您可以在该范围内进行二分查找以进一步缩小基数。然而，如果您的基数是一个无理数，这个过程将永远不会收敛。 - bta
1
我不确定这个问题能否有效地解决。我会尝试选择一个随机的基数，看看给定该基数时结果是小于、大于还是等于该数字。如果结果比该数字小，那就选择一个更大的基数，如果结果比该数字大，则选择一个更小的基数，否则你就得到了正确的基数。
- Henri
1
这应该会给你一个起点：
从数字和表示中创建一个方程，数字42和表示“0010203”变为：
从数字和表示中创建一个方程，数字42和表示“0010203”变为：
1 * base ^ 4 + 2 * base ^ 2 + 3 = 42
现在你可以解方程来获取base的值。
- Guffa
1
我认为你需要尝试并检查不同的进制。为了高效，你的起始进制可以是max(digit) + 1，因为你知道它不会小于这个值。如果这个值太小，就加倍直到超过，然后使用二分搜索来缩小范围。这样，你的算法在正常情况下应该以O(log n)的速度运行。
- Big Endian
1
其他一些帖子建议通过找到表示数字的多项式的根来找到解决方案。当然，这通常是有效的，尽管它们往往会产生负数和复数基数以及正整数。
另一种方法是将其作为整数规划问题进行转换，并使用分支定界法进行求解。
但我怀疑猜测和测试的建议比任何聪明的提议都要快。
- High Performance Mark
1
该问题展示了一个非整数基的例子。因此，整数规划不适用。 - Ben Voigt
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
I，base^I > ∑(i in [0, I[)(digit[i] * base^i)。这个属性使得问题变得更容易，我在答案中进行了说明，因为我没有足够的空间来放置方程，但它确实大大简化了手头的问题。 - Matthieu M.