Mostrando entradas con la etiqueta multiplicación rusa. Mostrar todas las entradas
Mostrando entradas con la etiqueta multiplicación rusa. Mostrar todas las entradas

jueves, 10 de mayo de 2018

Algoritmo de la multiplicación rusa. Un ejemplo

Realícese la multiplicación $45\cdot 98$ empleando el algoritmo 'ruso'

procedimiento multiplicación_rusa(a,b)
inicio
{
 i:=1;
 a_i:=a;
 b_i:=b;
 p:=0;
 mientras a_i!=1 hacer
  {
   i:=i+1;
   a_i:=entero_por_defecto(a_i/2);
   b_i:=2·b_i
   si resto(a_i div 2 ) != 0, p:=p+b_i
  }
 escribir('a·b=',p);
}
fin

Ejemplo de implementación:

% multiplicación_rusa(45,98)
salida:
->  45·98=4410

Proceso paso a paso:
------------------------------------------------------------------
  i  |  a_i    | ¿ a_i es impar ?   |   b_i   |  si a_i es impar
     |         |                    |         |   acumula suma de
     |         |                    |         |   b_i  
------------------------------------------------------------------
  1  |  45     |      sí            |    98   |       98
------------------------------------------------------------------
  2  |  22     |      no            |   196   |       98
------------------------------------------------------------------
  3  |  11     |      sí            |   392   |   98+392=490
------------------------------------------------------------------
  4  |   5     |      sí            |   784   |  490+784=1274
------------------------------------------------------------------
  5  |   2     |      no            |  1568   |      1274
------------------------------------------------------------------
  6  |   1     |      sí            |  3136   | 1274+3136=4410
------------------------------------------------------------------

$\square$