Выполнение умножения на изолированных элементах arraylist

Я ищу четкое объяснение своего вопроса (НЕ ищу код), но если немного кода поможет вам объяснить себя, пожалуйста, сделайте это. Спасибо :)

Вопрос:

-использование Java

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

Например, с моим кодом прямо сейчас это выглядит примерно так:

"Пожалуйста, введите целое число:"

688

"Пожалуйста, введите другое целое число:"

34

На данный момент внутри я сохранил ввод как 2 массива, которые выглядят так:

СписокСписка1: [6, 8, 8]

СписокМассива2: [3, 4]

Теперь предположим, что я хочу выполнить умножение, например, ArrayList1 * ArrayList2.

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

Но та часть, с которой у меня возникли проблемы, заключается в том, чтобы придумать систематический и четкий способ умножения массивов вместе. Имейте в виду, что в этом примере используется список массивов, который представляет целое число длины 3 и 2 соответственно, но это может быть что угодно. Я мог бы, например, иметь массив с 50 элементами, такими как [2, 4, 4, 3, 7, 3, 6, 3,............], который мог бы представлять огромное число в триллионы и т.д.


java arraylist algorithm math multiplication
person John Smith    schedule 04.02.2012    source источник
comment
BigInteger может быть более эффективным способом сделать это, если это разрешено/доступно/уместно.   -  person Louis Wasserman    schedule 04.02.2012
comment
Справедливо. Судя по контексту, не был уверен, было ли это упражнением.   -  person Louis Wasserman    schedule 04.02.2012
comment
Вам было бы значительно проще, если бы ваши списки были [8,8,6] и [4,3] такими, что представленное значение представляет собой сумму элемента, умноженного на десять в степени его индекса - в противном случае вам нужно вычислить заранее количество цифр в результате, или придется все сдвинуть, если нужно другое.   -  person Pete Kirkham    schedule 04.02.2012

Ответы (3)


arrow_upward
0
arrow_downward

псевдокод:

subtotal=0
iterate AL1 on index i (where i goes from zero to AL1.length()-1)
{
  iterate AL2 on index j (where j goes from zero to AL2.length()-1))
  {
    increment subtotal by AL2[AL2.length-j]*10^j * AL1[AL1.length-i]*10^i
    increment j
  }
  increment i
}
person kmote    schedule 04.02.2012

arrow_upward
2
arrow_downward

Если вы не используете быстрый алгоритм, такой как умножение Карацубы, описанный вами алгоритм умножения двух чисел будет простой алгоритм O(n^2), который вы выучили в начальной школе, - умножить каждую цифру второго списка на каждую цифру первого списка, перенося по мере необходимости. Итак, для вашего первого примера этот алгоритм дает вам 688 x 34 = [6*4, 8*4, 8*4] + [6*3, 8*3, 8*3, 0] = [24, 32, 32] + [18, 24, 24, 0], что после переноса становится [2, 7, 5, 2] + [2, 0, 6, 4, 0] = [2, 3, 3, 9, 2] .

person Adam Mihalcin    schedule 04.02.2012

arrow_upward
1
arrow_downward

Похоже, вы хотите в конечном итоге умножить, в вашем примере: 688 * 34. Чтобы сделать это со структурой, которую вы используете, ArrayList это будет сделано с использованием 2 циклов for, по одному для каждого списка (улучшенный цикл for, поскольку его итерируемый объект). Взятие каждого элемента из первого массива будет умножено на 10 ^ i, что даст вам (8 * 10 ^ 0) + (8 * 10 ^ 1) + (6 * 10 ^ 2) = 688. Каждый будет умножен на каждый целое число во втором списке и умножается на 10^j, как это было сделано в первом цикле. Держите текущий счетчик каждой итерации в цикле, чтобы суммировать каждое умножение по мере их возникновения.

person wcawley    schedule 04.02.2012