-2

我正在研究 SPOJ 的以下问题，

http://www.spoj.com/problems/ARITH/

据说这个数字最多应该包含500位数字，对于最多500位数字的数字，什么是合适的数据类型？

4

5 回答 5

2

没有内置数据类型来保存 500 位的整数。因此，您必须想出一种将它们存储在字节数组中的方法。

从http://gmplib.org/的作用中获得灵感。简而言之，您必须首先将数字存储在某处：

struct Digit {
    size_t len;
    char   sign;
    char*  digits;
};

然后你必须实现你需要使用的所有功能Digit：

void digit_init(struct Digit* d);
void digit_set(struct Digit* d, const char* digits);
void digit_add(struct Digit* a, struct Digit* b, struct Digit* result);
void digit_mult(struct Digit* a, struct Digit* b, struct Digit* result);
于 2013-03-06T06:19:06.317 回答
1

使用 GMP 库进行多精度算术，您将被排序。

http://gmplib.org/

于 2013-03-06T06:25:37.997 回答
0

据我所知，没有这样的内置函数/类型可以如此精确地执行算术运算。既不是 C 也不是 C++。也不是 STL。C ++也没有提升。因为您要将其提交到 SPOJ，所以无法链接自定义库。据我所知，如果你坚持使用C，并且你在SPOJ上做问题，你只能自己编写例程或复制粘贴。

或者，尝试具有内置 Big-Integer 支持的 Java/Python。

长话短说，没有优雅的方式来实现这一点，因为您将在 SPOJ 上提交它。

于 2013-03-06T08:44:40.510 回答
0

没有内置的方法可以将这么多数字存储为 c 中的数字。该问题旨在让您通过其他方式进行算术运算（始终将数字保留为字符串并一次处理少量实际数字）。由于 BigInteger，这个问题在 Java（例如）中更容易实现。但是如果你想用 c 来做，我会看看 BigNum 实现是如何工作的。这可能有助于作为参考：

http://www.algorithmist.com/index.php/BigNum

于 2013-03-06T06:26:07.130 回答
0

对于每个乘法，将第一个数字乘以第二个数字的每个数字。将部分结果放在另一个下方，从第二个数字的最后一位数字的乘积开始。每个部分结果都应与相应的数字对齐。”

由于这个限制，没有实际的替代品 char bignum[MAX_DIGITS+1];

编辑 ——这是我最初的回应；如果不需要打印中间结果，它仍然很有用。

由于重点是以10 为基数写下数字，并且输入以 10 为基数，我建议使用以 10 为基数的导数数组——字符是研究长乘法的一个很好的候选者，但将基数扩展到 100、1e4、 1e6 或 1e9 会有意义。

以 100 为底适合 uint8_t 或 char，以 10000 为底适合 uint16_t（即使在大多数嵌入式处理器上也可以使用 16x16 ==> 32 乘法）；双精度数最多可以保存 2^53 -1 的精确值，这会将每个被乘数实际上限制为 1e6。

使用例如 base 1e8 允许在 (uint32_t) 中存储 8 位数字，并且它允许在 (uint64_t) 中逻辑地存储乘法结果。它还允许轻松打印数字，而无需将基数为 2 的 bignum 转换为十进制表示所需的长除法。

 struct big_int {
     uint32_t digits[MAX_DIGITS/8];
     unsigned int length;  //
     int sign;             // or possibly use int length and negative lengths
 };
于 2013-03-06T06:37:28.930 回答