Studientagsübung Bauernmultiplikation

Dr Franke Ghostwriter
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...

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);
        }
    }    
}
 
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 🙂

Dann werfe ich mal noch nen Handschuh hinterher und sage: "Halbieren geht noch viel viel einfacher 🙂" Die dafür notwendigen Operatoren werden aber im Kurs definitiv gar nicht thematisiert. Noch ein kleiner Hinweis: Wie sieht halbieren im Binärformat aus?

Viele Grüße und ein schönes Restwochenende
Silvia
 
Dann werfe ich mal noch nen Handschuh hinterher und sage: "Halbieren geht noch viel viel einfacher 🙂" Die dafür notwendigen Operatoren werden aber im Kurs definitiv gar nicht thematisiert. Noch ein kleiner Hinweis: Wie sieht halbieren im Binärformat aus?

Hast du nicht gesagt, du hättest Urlaub?
Also, _DEN_ Handschuh hast du nun aber richtich weit aus dem Ring rausgeworfen; und dann noch nach hinten...

Unabhängig von der Signatur die ich hier manchmal verwende, habe ich BitOperationen zuletzt glaube ich auf dem C64 benötigt.
Wie ging das noch... alle Bits eins nach rechts aufrutschen, wobei das äusserst rechte leider dran glauben muss und links eine 0 nachgeschoben wird?

Das mache ich jetzt aber nicht in Java - soweit geht mein Ehrgeiz nicht 🙂
Man müsste ja dann auch entweder einen speziellen BitShift Operator verwenden... in C# geht das z.B. mit nHalberWert = nGanzerWert >> 1.
Wie geht denn der Operator in Java, wahrscheinlich genauso, oder?
Aber das entstellt ja auch irgendwie den Sinn der Aufgabe.

Wenn schon, denn schon, müsste man ja ein entsprechendes Array aus booleans machen, dessen Grösse man entweder auf 32 festlegt, oder auch erst noch ermitteln muss.
Dann den zu halbierenden Wert binär zerlegen und ins Array schreiben... neee, lass mal
 
hab mal eben mit bitoperationen gelöst, ich hab jetzt nur keine rekursion drin, weiß nicht ob es gefordert war:

import java.util.Scanner;

public class Bauernmultiplikation {

long faktor1, faktor2; // Zu multiplizierende natürlich Zahlen
long ergebnis = 0;

// Konstuktor
public Bauernmultiplikation() {
einlesen();
berechnen();
System.out.println(ergebnis);
}

/**
* Liest 2 Longwerte ein.
* Zur vereinfachung, gehe ich von korrekten werten aus...
*/
private void einlesen() {
System.out.println("ersten Faktor eingeben: ");
Scanner sc = new Scanner(System.in); // Scanner zum einlesen der werte.
if(sc.hasNext()) // Prüfen ob elemete vorhanden sind.
faktor1 = sc.nextLong(); // faktor1 einlesen.

System.out.println("zweiten Faktor eingeben: ");
if(sc.hasNext()) // Prüfen ob elemete vorhanden sind.
faktor2 = sc.nextLong(); // faktor2 einlesen.

}

/**
* Führt die Bauernmultiplikation aus.
*/
private void berechnen() {
while(faktor1 > 0) { // Abbruch bedingung, wenn faktor1 auf 0
if(isUngerade(faktor1)) { // Prüft, ob faktor1 ungerade ist,
ergebnis += faktor2; // wenn ja zwischenergebnis + neuer faktor.
}
faktor1 = faktor1 >> 1; // halbieren des faktor1.
faktor2 = faktor2 << 1; // verdoppeln faktor2.
}
}

/**
* Prüft, ob eine Long zahl ungerade ist.
* @param zahl
* @return
*/
private boolean isUngerade(long zahl) {
if(zahl != ((zahl >> 1) + (zahl >> 1))) // Wenn die zahl ungleich ihrer 2
return true; // abgerundeten hälften ist ist sie ungerade.

return false; // sonst ist sie gerade.
}

/**
* Main methode damit es in eclipse gestartet werden kann.
* @param args
*/
public static void main(String args[]) {
new Bauernmultiplikation();
}
}
 
Kollege!

Ich habe Fragen zu den Übungen vom Studientag und zwar:

Wie wird das folgende ausgeklammert?:
Klammern Sie den folgenden Ausdruck vollständig:

11 + 3 * 4 - 4 / 6 % 3 + 2 * 7 – 3

ich habe die folgende Lösung:
11+(3*4)-((4/6)%3)+(2*7)-3

Stimmt es?

Ich verstehe die nächste Aufgabe nicht und bezüglich den Ausdrücken:
true && false || true

3 > 4 ^ 7 >= 3 + 4

true && (3 < 4 || 4 > 5)

false || 4 == 2 * 2 ^ 2 == 1 + 1

Was denkt ihr dran?

ich bedanke mich im Voraus.

Mit einem freundlchen Grüß

bulgari
 
Oben