Russische Bauernmultiplikation

Eine einfache Fingerübung, bei der man wieder schön Unit Tests einsetzen kann, ist die russische Bauernmultiplikation. Die Aufgabe ist auf der Seite der Clean Code Developer School sehr schön und einfach beschrieben.

Der Vollständigkeit halber hier eine Kopie.

Aufgabe

Schreibe eine Funktion, die zwei ganze Zahlen mit dem Algorithmus „russische Bauernmultiplikation“ multipliziert.

Die Signatur der Methode sieht wie folgt aus:

int Multiply(int x, int y);

Der Algorithmus der sogenannten Russischen Bauernmultiplikation verläuft wie folgt: man halbiert die linke der beiden Zahlen so lange, bis die 1 erreicht ist. Nachkommastellen werden abgerundet. Die rechte Zahl wird jeweils daneben geschrieben und verdoppelt. Von den rechten Zahlen werden alle gestrichen, neben denen links eine gerade Zahl steht. Die verbleibenden nicht gestrichenen Zahlen der rechten Seite werden dann addiert und bilden das Ergebnis der Multiplikation.

Beispiel:

47 * 42
-------
47   42
23   84
11  168
 5  336
 2  672
 1 1344
=======
   1974

ennoadm

Verwandte Beiträge

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht.

Read also x