Studientagsübung: Bauernmultiplikation
Da Sylvia ja nun mal den Handschuh geworfen hat ("Auf die Division braucht ihr nicht wirklich zu verzichten... wer mehr mit Programmierung zu tun hat, kann das lösen, aber hier geht das zu weit..") mussten wir uns der Sache doch mal annehmen 🙂
Hier ein Vorschlach, danke auch an Jörch für's Mitdenken bezüglich gerade/ungerade...
Da Sylvia ja nun mal den Handschuh geworfen hat ("Auf die Division braucht ihr nicht wirklich zu verzichten... wer mehr mit Programmierung zu tun hat, kann das lösen, aber hier geht das zu weit..") mussten wir uns der Sache doch mal annehmen 🙂
Hier ein Vorschlach, danke auch an Jörch für's Mitdenken bezüglich gerade/ungerade...
Code:
/**
* Übung zur Kurseinheit 4; Bauernmultiplikation
* Es soll eine Multiplikation von zwei natürlichen Zahlen
* durchgeführt werden, ohne explizit eine Division oder eine
* Multiplikation anzuwenden
*
* @author ich
* @version 1.0.0.0
*/
public class Multiplikation
{
// Die beiden Multiplikatoren werden hier als Exemplarvariablen implementiert
// da man ansonsten der rekursiven Methode "halbiere(long e)" immer wieder
// denselben Wert übergeben müsste... oder nich?
long m1; // Multiplikator 1
long m2; // Multiplikator 2
public Multiplikation()
{
}
public long multipliziere_m1_mit_m2(long a, long b)
{
// folgendes Q&D, weil ich nicht weiss, wie ReadLn funzt...
m1 = a;
m2 = b;
long ergebnis = 0; // Zwischenspeicher für den Rückgabewert
long m1_halb; // Hälfte des ersten Multiplikators
// Bauernrechnung anwenden, solange der erste Multiplikator
// grösser als 0 ist
while (m1 > 0)
{
// halben Wert von m1 ermitteln, als Startwert nehmen wir
// den ersten Multiplikator minus 1
m1_halb = halbiere(m1 - 1);
// following concept courtesy of Jörch... :)
// Wenn 2 Hälften nicht wieder exakt das Ganze ergeben, dann ist es
// eine abgerundete Hälfte, und somit ist die ganze Zahl ungerade...
if ((m1_halb + m1_halb) != m1)
{
// erster Multiplikator ist ungerade...
ergebnis += m2;
}
// Ersetze ersten Multiplikator mit der Hälfte, ggfs. abgerundet
m1 = m1_halb;
// Ersetze zweiten Multiplikator mit dem Doppelten
m2 += m2;
}
return ergebnis;
}
// rekursive Methode, um die ggfs. abgerundete Hälfte einer natürlichen Zahl
// zu ermitteln, ohne explizite Division oder Multiplikation zu verwenden
// Die Zahl, von der die Hälfte ermittelt werden soll, ist hier als Variable
// des Exemplars vorgegeben (m1, siehe oben), um unnötige Werteübergabe zu
// vermeiden.
// Ausgehend von einem Startwert "e" wird dieser rekursiv solange um den Wert 1
// verringert, bis sein Zweifaches kleiner oder gleich dem zu halbierenden Wert
// ist
private long halbiere(long e)
{
if ((e + e) <= m1)
{
return e;
}
else
{
return halbiere(e - 1);
}
}
}