Умножение «столбиком»

Умножение «столбиком» чисел и производится по формуле . Запишем эту формулу в виде и реализуем ее в виде программы Mult.

Procedure Mult(Prod,M1,M2)

Begin

SetEmpty(Prod)

if (M1 nil)and(M2 nil) then {

revers(S,M1);t:=S.last;

Repeat

AddToBegin(Prod,0);

t:=t^.next;MultCnst(S1,M2,t^.info);Add(S2,Prod,S1);{Prod, S1можно удалить}

Prod.last:=S2.last

until t=S.last;

norm(Prod)} {Sможно удалить}

End

Трудоемкость умножения «столбиком» чисел длины n и m пропорциональна произведению mn.