Я должен написать функцию, которая умножает два больших числа, которые находятся в двух связанных списках. Мне нужна помощь в разработке алгоритма, который делает это так же, как вы решали бы это на ручке и бумаге. вот о чем я думаю:
Я бы использовал вложенный цикл for для перебора обоих списков при умножении каждого из элементов, но я не уверен, как справиться с ситуацией переноса. Я уже реализовал функцию, которая добавляет два связанных списка целых чисел. любой вклад будет оценен.
Я бы выбрал рекурсию (если вы не слышали о рекурсии, вы, вероятно, можете проигнорировать этот ответ; рано или поздно вы его изучите).
Я беру умножение 152 * 463 в качестве примера. Мой калькулятор говорит мне, что ожидаемый результат равен 70376. Моя идея состоит в том, чтобы отделить 2 от 152, чтобы получить 15 и 2, а затем умножить 15 * 463 и 2 * 463:
15 * 463 = 6945. Needs to be multiplied by 10 because the 15 were in the 10s’ position. 6945 * 10? Just add a zero: 69450.
2 * 463 = 926.
Product is 69450 + 926 = 70376.
В вашем коде 15*463 получается через рекурсивный вызов метода умножения, который вы пишете. Умножить на 10 просто, достаточно добавить ноль. 2 * 463 проще, потому что мы умножаем на однозначное число. Напишите новый рекурсивный метод для этой подзадачи. Функция, которая у вас уже есть, которая добавляет два связанных списка, завершит работу.
O(n^2), либо Карацубу. Но имейте в виду, что Карацубе нужно больше переносных бит... - person Spektre schedule 06.07.2020