Решение математических задач с целыми числами, большими, чем у любого доступного целочисленного типа данных - PullRequest
Новая
       29

Решение математических задач с целыми числами, большими, чем у любого доступного целочисленного типа данных

0 голосов
/ 05 февраля 2019

В некоторых соревнованиях по программированию, где числа больше, чем у любого доступного целочисленного типа данных, мы часто вместо этого используем строки.

Вопрос 1: Учитывая эти большие числа, как рассчитать e и f в приведенном ниже выражении?

(a / b) + (c / d) = e / f

примечание: GCD (e, f) = 1 , т.е. они должны быть в минимизированном виде.Например, {e, f} = {1,2} вместо {2,4} .
Кроме того, все a, b, c, d известны нам большие числа.

Вопрос 2: Может ли кто-нибудь также предложить способ найти GCD из двух больших чисел (больше, чем у любого доступного целочисленного типа)?

Ответы [ 2 ]

0 голосов
/ 06 февраля 2019

Я думаю, что способ решить эту проблему состоит в том, чтобы отделить проблему:

  1. Обработать введенные числа как массив символов (т. Е. std::string)

  2. Создайте класс, в котором каждый объект может хранить std::list (или подобное), которое представляет одно из больших чисел, и может выполнять необходимую арифметику с вашими данными

  3. После этого вы можете нормально решать свои проблемы, не беспокоясь о том, что ваши большие входные данные вызывают переполнение.

Вот веб-страница, которая объясняет, как у вас может быть такой арифметический класс (с примером кода на C ++, показывающим добавление).

Если у вас есть такой арифметический класс, вам больше не нужно беспокоиться о том, как хранить данные или о любом переполнении.

У меня сложилось впечатление, что вы уже знаете, как найти GCD, когда у вас нет проблем с переполнением, но на всякий случай вот объяснение поиска GCD (с примером кода C ++).

Что касается конкретногоматематическая задача: 

// given formula: a/b + c/d = e/f
// = ( ( a*d + b*c ) / ( b*d ) )

// Define some variables here to save on copying
// (I assume that your class that holds the
//   large numbers is called "ARITHMETIC")
ARITHMETIC numerator = a*d + b*c;
ARITHMETIC denominator = b*d;
ARITHMETIC gcd = GCD( numerator , denominator );

// because we know that GCD(e,f) is 1, this implies:
ARITHMETIC e = numerator / gcd;
ARITHMETIC f = denominator / gcd;
0 голосов
/ 05 февраля 2019

Я бы предложил использовать полные байты или слова, а не строки.

Относительно легко основываться на 256, а не на 10, и гораздо эффективнее для процессора не делать умножения и деления на 10 все время.В идеале, выбирайте размер слова, который равен половине естественного размера слова процессора, поскольку это облегчает выполнение переноса.Конечно, думать на базе 64K или 4G немного сложнее, но даже лучше, чем на базе 256.

Единственным недостатком является генерация начальных больших чисел из входных данных ascii, которые вы получаете бесплатно в базе 10. Использованиебольший размер слова вы можете сделать это более эффективным, если сначала обработать несколько цифр в одно слово (например, 9 цифр за раз в 4G), а затем выполнить длинное умножение этого одиночного слова до правильного смещения в формате большого целого числа..

Компромисс может состоять в том, чтобы запустить ваш двигатель на базе 1 млрд. Это все равно будет в 9 или 81 раз эффективнее, чем при использовании базы 10!

Самый простой способ решить это уравнение - этоумножьте a / b * d / d и c / d * b / b, чтобы они оба имели общий знаменатель b * d.

Я думаю, что вам нужно будет сначала разложить на множители ваши большие числа e и f, чтобы найти общие факторы.Не забудьте снова искать тот же коэффициент в квадрате.

Конечно, это означает, что вы должны написать простое порождающее сито.Вам нужно только сгенерировать множители с точностью до квадратного корня или половины цифр от минимального значения e и f.

Вы можете использовать простые множители b и d, чтобы получить меньший начальный знаменатель, но вам потребуетсяв любом случае сделайте это снова после добавления.

...