Enrere Mòdul 3
Fonaments de Programació. Llenguatge C/C++---
Pràctica  Resum teòric Exercicis
Pràctica d'ampliació

 
Algorisme rus de la multiplicació

En aquesta pràctica farem ús de la sentència do...while per tal de fer la multiplicació de dos nombres enters d'una forma molt especial.

 
Desenvolupament de la pràctica

Definiu un projecte nou anomenat m3p05 i afegiu-li un arxiu de font C/C++ anomenat m3p05.cpp. Escriviu el següent codi:

//m3p05.cpp: algorisme rus de la multiplicació

#include <stdio.h>

int mrus(int a,int b);

void main(){

    int a,b;

    printf("introduïu a,b>0 ");
    scanf("%d %d",&a, &b);
    printf ("\n\n%d x %d = %d\n",a,b,mrus(a,b));

}

// funció multiplicació rusa

int mrus(int a,int b ){

    int suma=0;

    do{

        if (a%2) suma=suma+b;

        a=a/2;b=b*2;

    }while(a>0);

    return suma;

}

 

Explicació del programa

S'escriuen els dos nombres, un al costat de l'altre i es formen dues columnes aplicant repetidament la següent regla: el primer nombre es divideix per dos i es col·loca  el quocient enter a sota. El segon nombre es multiplica per dos i es col·loca a sota. Aquest procediment es segueix fins que s'obtingui un 1 a la primera columna. 

Per exemple, per multiplicar 46 i 43 fem:

46 43
23 86
11 172
5 344
2 688
1 1376

A continuació es ratllen les files en què el primer dels nombres sigui parell:

46 43
23 86
11 172
5 344
2 688
1 1376

La suma dels nombres no ratllats que en queden de la segona columna és el resultat.

86+172+344+1376=1978

Pot ser que aquest algorisme sembli una mica estrany però s'ha de tenir en compte que es pot realitzar sense saber les taules de multiplicar, tan sols és necessari saber sumar, duplicar i dividir per dos.

Aquest algorisme s'implementa en el programa a través de la funció mrus(int a, int b):

// funció multiplicació rusa

int mrus(int a,int b ){

    int suma=0;

    do{

        if (a%2) suma=suma+b;

        a=a/2;b=b*2;

    }while(a>0);

    return suma;

}

Inicialment, a i b són els nombres que volem multiplicar, després, els successius valors d'a corresponen als valors de la columna de l'esquerra i els successius valors de b als valors de la columna de la dreta. En el cos del bucle hi ha una sentència if que fa que s'acumuli en la variable suma els valors de b que corresponen a valors d'a senars (a%2 diferent de 0).