4

存储大型 B 基数的最佳方法是什么，以便可以有效地完成右移和检查最低有效位等操作？

实际上，我遇到了一个面试问题，上面写着

Given two numbers N and K such that 0<=N<=1000 and 0<=K<=1000^1000. I need 
to check that whether N^N = K or not. For example:

if N=2 and K=4 , 2^2 = 4 so return true;
if N=3 and K=26 , 3^3 != 26 so return false

我在想的是，如果我考虑base N number system, thenN^N将相当于1 followed by N zeroin it。例如 - 对于 N = 2，2^2 = 100（以 2 为底），对于 N=3，3^3 = 1000（以 3 为底）。然后我可以轻松地编写一个函数来判断是否K = N^N。

int check(unsigned long int N, unsigned long int K) 
{
    unsigned long int i;
    for (i=0; i<N; i++) 
    {
        if (K%N != 0) //checking whether LSB is 0 or not in base N number system 
           return 0;
        K = K/N; //right shift K by one. 
    }
    return (K==1);
}

现在这个函数有两个主要问题：

1) An unsigned long int is not sufficient to store large numbers of range 0 
to 1000^1000.
2) The modulus and the division operations makes it every less efficient.

为了提高效率，我正在寻找某种方法来表示大的基数 N 数字，以便我可以有效地执行右移和检查最低有效位操作。有没有人遇到过这样的事情？或者有人知道有效解决这个问题的任何其他方法吗？

4

5 回答 5

2

要检查相等性，您实际上不必进行高精度算术 - 您可以使用http://en.wikipedia.org/wiki/Chinese_remainder_theorem。找到足够的素数以确保它们的乘积大于 N^N，然后依次检查 N^N 与 K 模数每个素数。

在实践中，我可能会使用 Java BigInteger 包来进行简单的计算。

于 2012-06-13T18:16:17.893 回答
2

根据面试官的不同，有一些答案可能会被接受。如果其中任何一个不被接受，那么希望面试官会迅速让你提出其他建议。

  • 使用, 并用代替 进行gmp除法和模数，或者只计算并与 比较。这是最简单的工作。mpz_tunsigned longN^NK
  • 编写您自己的大数库，可能使用以 10 为基数而不是以 2 为基数的内部表示，如果输入以 10 为基数，并且认为坚持使用它可能比首先转换为二进制更快。当然它不需要是一个完整的算术库，你真正需要的只是除法与余数。
  • 发明一些可以在开始之前进行的快速测试，以避免在某些方面K遥不可及时进行大量工作。N^N例如，测试是否log(K) / N近似等于log(N)，以最方便输入的任何基数取对数。或者测试多少次K并且N可以被方便的数字整除，例如2or 10：如果K不能被整除的N倍数是 的倍数N，那么它显然是错误的。或者测试它们是否等于模一些小的数字，比如ULONG_MAX或1000000. 不幸的是，这种事情只会加速它们不相等的某些情况，它会减慢其他一切，包括它们的情况。因此，这可能会适得其反，具体取决于您期望的输入。

我不知道，麦克多维拉的回答可能是最好的，也可能不是最好的。特别有希望的是，您只需要生成一次素数（当您编写程序时），并且从 1009 开始的 1000 个素数已经足够给定了N <= 1000。更大的素数意味着更少的需要，因此更少的工作，特别是如果它们没有大于 的平方根ULONG_MAX。通过平方或等价的取幂来获得N^N模每个素数，并K在输入的任何基础上一次做几个数字。

为了真正的闪光，对于每个预先选择的素数p，您可以编写（或让编译器为您编写）一个模 p 运算，它比适用于任何除数的一般整数模运算更快。也就是说，使用一个体面的编译器i % 1009可能比编译时未知i % j的值要快j，但在运行时结果为 1009。但请注意，速度上的差异可能无法证明（比如说）调用它的成本通过函数指针。因此，利用它可能需要一些难看的重复代码。

于 2012-06-13T18:30:47.697 回答
0

给定两个数字 N 和 K，使得 0<=N<=1000 和 0<=K<=1000^1000。我需要检查 N^N = K 是否。

很大程度上取决于这些数字在提供给您的代码时是如何存储的。假设它们是文本格式，我会保持这种方式，并创建一个包含 1001 个字符串的数组来存储 N^N 值。您可以使用任意精度的算术命令行程序，例如bc一次性创建这些字符串，在循环中调用它。

于 2012-06-14T08:55:33.610 回答
0

由于 1000^1000 中只有 1000 个“好”值（而且它们之间的距离会很远），因此您可以先使用一些对数近似来猜测N。之后，您最多需要进行一次精确检查（例如，使用一些 bignum 库）。

这个对数不一定要精确，甚至strlen()也可以是足够接近的近似值。

于 2012-06-14T10:39:22.620 回答
0

为什么要将数字转换为基数 N？

您可以继续除以 N。如果您在 N 个这样的除法之后得到 1，那么它就是 N^N。否则不是。

您必须将 K 存储为字符串并实现除法运算。

divide(k,n):
  c = ''
  a = ''
  for i in k:
    c = c+i
    a = a+ str(int(c)/ int(n))
    c = str(int(c) % int(n))
 return a

这是在 python 中，你可以在 C 中实现类似的东西

于 2012-06-13T18:11:33.153 回答