я работаю над следующей проблемой SPOJ,с - тип данных для очень длинного числа
http://www.spoj.com/problems/ARITH/
Говорят, что номер должен содержать atmost 500 цифр, что соответствующий тип данных для number with maximun 500 цифр
использовать библиотеку GMP для мульти-точности арифметика, и вы будете отсортированы.
привет Кинджал, спасибо за предложение! – Subbu
Нет встроенного типа данных для хранения целого числа в 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);
Там нет встроенного способа хранения, что много цифр как число в с. Этот вопрос предназначен для того, чтобы вы делали арифметику другими способами (оставляя число в виде строки все время и имея дело с небольшим количеством фактических чисел сразу). Вопрос в том, что проще сделать на Java (например) из-за BigInteger. Но если вы хотите сделать это с помощью c, я бы посмотрел, как работает реализация BigNum в целом. Это может помочь в качестве ссылки:
Для каждого умножения, умножить первое число на каждую цифру второго числа. Поместите частичные результаты один за другим, начиная с произведения последней цифры второго номера. Каждый частичный результат должен быть совмещен с соответствующей цифрой «
Из-за этого ограничения, нет никакой практической заменой к char bignum[MAX_DIGITS+1];
РЕДАКТИРОВАТЬ - это был мой первоначальный ответ;. Она по-прежнему полезно, если не нужно печатать промежуточные результаты.
Поскольку упор делается на , записывая цифры в базе 10, а так как вход в базе 10, я предлагаю использовать базовые десятимерные массивы - Char s являются хорошим кандидатом для изучения длительного умножения, но расширение базы до 100, 1e4, 1e6 или 1e9 будет иметь смысл.
Base 100 будет соответствовать uint8_t или char, base 10000 будет с uint16_t (в то время как 16x16 ==> 32 умножение доступно даже на большинстве встроенных процессоров); Удвои могут содержать точные значения до 2^53 -1, что ограничивало бы каждый мультипликат практически до 1е6.
Работа с, например, base 1e8 позволяет хранить 8 цифр в (uint32_t) и позволяет логически хранить результат умножения в (uint64_t). Он также позволяет легко печатать числа без длинного разделения, необходимого для преобразования базового 2 бигнома в десятичное представление.
struct big_int {
uint32_t digits[MAX_DIGITS/8];
unsigned int length; //
int sign; // or possibly use int length and negative lengths
};
Насколько я знаю, такой встроенной функции/типа для выполнения арифметики с такой точностью не существует. Ни C, ни C++. Ни STL. Не повышается для C++. Поскольку вы собираетесь отправить его на SPOJ, вы не можете связать собственную библиотеку. Насколько я знаю, если вы настаиваете на использовании C и что вы делаете проблему в SPOJ, вы можете написать свою собственную рутину или скопировать &.
В качестве альтернативы попробуйте использовать Java/Python с встроенной поддержкой Big-Integer.
Короче говоря, нет элегантного способа достичь этого, учитывая тот факт, что вы отправляете его на SPOJ.
Возможный дубликат [Как создать тип данных для хранения более 200 цифр в C?] (Http://stackoverflow.com/questions/5436007/how-to-create-a-datatype-to-hold- 200-digit-long-numbers-in-c) – 2013-03-06 06:17:43
Да, я использовал строку размером 500, но для выполнения вычислений, когда мы конвертируем эту строку в число, возникает проблема. – Subbu
Это не может быть эффективным решением. Но почему бы не использовать массивы и выполнить операции с последнего (n-1). Используйте временные переменные (перенос, заимствование и т. Д.) Везде, где это необходимо. Опять же, это не может быть эффективным решением. – Gomu