Как умножить два больших больших числа

В моем первом ответе я обратился к проблеме ОП в «умножении двух больших чисел». Как оказалось, это желание - лишь небольшая часть гораздо более серьезной проблемы, которую я собираюсь решить сейчас:

«Я все еще не добрался до окончательного скелета моего алгоритма. Интересно, не могли бы вы мне помочь? с этим."

(См. Вопрос для описания проблемы)

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

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

1. Вычислить произведение каждого непрерывного подсписка.
2. Вернуть самый большой из всех этих продуктов.

Подсписок можно представить по его индексу start и end . Для start = 0 существует n-1 возможных значения для end , а именно 0..n-1. Это генерирует все подсписки, которые начинаются с индекса 0. На следующей итерации вы увеличиваете start на 1 и повторяете процесс (это время, есть n-2 возможных значения для end ). Таким образом, вы создаете все возможные подсписки.

Теперь для каждого из этих подсписок вы должны вычислить произведение его элементов - то есть подойди с th - метод computeProduct (Список целых списков, int startIndex, int endIndex) . Вы можете либо использовать встроенный класс BigInteger (который должен уметь обрабатывать ввод, предоставленный вашим заданием), чтобы избавить вас от дальнейших проблем, либо попытаться реализовать более эффективный способ умножения, как описано другими. (Я бы начал с более простого подхода, так как легче увидеть, правильно ли работает Ваш алгоритм, и сначала попытаться его оптимизировать.)

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

Если вам все еще сложно установить связь между двумя этапами, дайте нам знать - но, пожалуйста, также предоставьте нам черновик своего кода по мере того, как вы работаете над проблемой, чтобы мы не закончили постепенное построение решение, и вы копируете и вставляете его.

править: Каркас алгоритма

public BigInteger listingSublist(BigInteger[] biArray)
{       
    int start = 0;
    int end = biArray.length-1;
    BigInteger maximum;

    for (int i = start; i <= end; i++)
    {
        for (int j = i; j <= end; j++)
        {
            //insert logic to determine the maximum product.
            computeProduct(biArray, i, j);
        }
    }

    return maximum;                
}

public BigInteger computeProduct(BigInteger[] wholeList, int startIndex, 
                                                         int endIndex)
{
    //insert logic here to return
    //wholeList[startIndex].multiply(wholeList[startIndex+1]).mul...(
    //    wholeList[endIndex]);       
}

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

Конечно, для хранения результата вам может понадобиться BigInteger, если у вас закончились биты. Или, в зависимости от того, как должен выглядеть результат, просто скажите (+/-)2^N, где N - сумма экспонент.

Разбор входных данных может быть вопросом switch-case, поскольку у вас есть только 30 чисел, о которых нужно позаботиться. Плюс отрицательные.

Это скучная часть. Интересная часть заключается в том, как получить подсписок, дающий наибольшее число. Можно использовать тупой подход, проверяя каждый вариант, но это будет алгоритм O(N^2) в худшем случае (IIRC). Что действительно не очень хорошо для длинных входных данных.

Что вы можете сделать? Я бы, вероятно, начал с самого большого неотрицательного числа в списке в качестве подсписка, и увеличил бы подсписок, чтобы получить как можно больше неотрицательных чисел в каждом направлении. Затем, имея все положительные числа в пределах досягаемости, переходите к парам отрицательных чисел с обеих сторон, например, расти только в том случае, если вы можете расти с обеих сторон списка. Если вы не можете расти в обоих направлениях, попробуйте расти в одном направлении с двумя (четырьмя, шестью и т.д., так даже) последовательными отрицательными числами. Если вы не можете расти даже таким образом, остановитесь.

Я не знаю, работает ли эта алогрифма, но если да, то это алгоритм O(N), что означает высокую производительность. Давайте попробуем! :-)

Поскольку k <= 30, любое целое число i = 2 ^k будет соответствовать Java int . Однако произведение таких двух целых чисел не обязательно может соответствовать Java int , поскольку 2 ^k * 2 ^k = 2 ^{2 * k} <= 2 ⁶⁰ , которые заполняют Java long . Это должно ответить на Ваш вопрос относительно «(умножения) двух чисел ...».

В случае, если Вы хотите умножить более двух чисел, что подразумевается в Вашем задании, говорящем «... наибольшее произведение НЕПРЕРЫВНОГО ПОДСПИСКА ...» (длина подсписка может быть> 2), посмотрите в классе Java BigInteger .

РЕДАКТИРОВАТЬ: Я скорректировал схему алгоритма, чтобы она соответствовала фактическому псевдокоду, и поместил анализ сложности непосредственно в ответ:

Схема алгоритма

Последовательно просматривайте последовательность и сохраняйте значение и первый / последний индекс продукта (положительный) с момента последнего 0. Сделайте то же самое для другого продукта (отрицательного), который состоит только из чисел с момента первой смены знака последовательности. Если вы попали в элемент отрицательной последовательности, поменяйте местами два продукта (положительный и отрицательный) вместе со связанными начальными индексами. Всякий раз, когда положительный продукт достигает нового максимума, сохраните его и соответствующие начальные и конечные индексы. После прохождения всей последовательности результат сохраняется в максимальных переменных.

Чтобы избежать переполнения, рассчитайте двоичными логарифмами и дополнительным знаком.

Псевдокод

maxProduct = 0
maxProductStartIndex = -1
maxProductEndIndex = -1
sequence.push_front( 0 ) // reuses variable intitialization of the case n == 0

for every index of sequence
   n = sequence[index]
   if n == 0
       posProduct = 0
       negProduct = 0
       posProductStartIndex = index+1
       negProductStartIndex = -1
   else
       if n < 0
           swap( posProduct, negProduct )
           swap( posProductStartIndex, negProductStartIndex )
           if -1 == posProductStartIndex // start second sequence on sign change
               posProductStartIndex = index
           end if
           n = -n;
       end if
       logN = log2(n) // as indicated all arithmetic is done on the logarithms
       posProduct += logN
       if -1 < negProductStartIndex // start the second product as soon as the sign changes first
          negProduct += logN
       end if
       if maxProduct < posProduct // update current best solution
          maxProduct = posProduct
          maxProductStartIndex = posProductStartIndex
          maxProductEndIndex = index
       end if
   end if
end for

// output solution

print "The maximum product is " 2^maxProduct "."
print "It is reached by multiplying the numbers from sequence index " 
print maxProductStartIndex " to sequence index " maxProductEndIndex

Сложность

Алгоритм использует один цикл над последовательностью, поэтому его сложность в O (n) раз превышает сложность тела цикла. Самая сложная операция тела - log2. Таким образом, его сложность в O (n) раз превышает log2. Log2 числа ограниченного размера составляет O (1), поэтому результирующая сложность O (n), также известная как линейная.

Хммм... поскольку все они равны 2, вы можете просто добавить экспоненту вместо умножения чисел (эквивалентно взятию логарифма произведения). Например, 2^3 * 2^7 - это 2^(7+3)=2^10. Я оставлю работу со знаком как упражнение для читателя.

Что касается проблемы подсписка, то существует менее n^2 пар индексов (begin,end). Вы можете проверить их все или попробовать решение методом динамического программирования.

Смотрите этот код. Здесь я реализую точный факториал огромного большого числа. Я просто использую целочисленный массив для создания больших чисел. Скачайте код с Planet Source Code.