Quotient durch Subtraktion bestimmen

[hybi]

Moin zusammen,
ich habe vor kurzem das folgende Programm geschrieben, in dem das Produkt zwischen 2 Zahlen durch Addition rekursiv berechnet wird:

public class rekursion
{
public static int mul(int i, int g) {
    if (i == 0 || g == 0)
        return 0;
    if (i == 1)
        return g;
    if (g == 1)
        return i;
    if (i < 0 && g < 0)
        return mul(i * -1, g * -1);
    if (i < 0)
        return -1 * mul(i * -1, g);
    if (g < 0)
        return -1 * mul(i, g * -1);
        
    return i + mul(i, g - 1);
}
	public static void main(String[] args){
		System.out.println("Result: = "+rekursion.mul(5, 6));
	}
}

Nun möchte ich dasselbe Programm umbasteln und der Quotient aus i und g soll durch ständige Subtraktion des g von i errechnet werden (z.B. bei 18/3 soll 18-3-3-3-3 = 6 erreicht werden).
Wie ich es auch gedreht und gewendet hab, komme einfach nicht auf die passende Lösung.
Natürlich ist da noch das Problem, dass man durch die Subtraktion oft nicht auf den dazugehörigen Quotienten stößt (z.B. bei 12/3 kommt man durch Subtraktion nicht auf 4).
Bin ein Java-Neuling und auch mathematisch stoße ich da an meine Grenzen. Jemand eine Idee/Tip/Anregung?

Viele Grüße

 

[stg]

Was du berechnen musst ist nicht 18-3-3-3-3 = 6, sondern du musst ermitteln, wie oft du die 3 von der 18 abziehen musst, um 0 zu erhalten. Also 18-3-3-3-3-3-3 = 0. Du merkst dir die Anzahl der Durchläufe (hier 6) und das ist dein Ergebnis.

 

[hybi]

Ah danke! Bin trotzdem überfragt wie ich das umsetzen soll.
Ich gehe davon aus, dass ich lediglich die letzte return-Zeile abändern muss, nur wie?

 

[blux]

Ah danke! Bin trotzdem überfragt wie ich das umsetzen soll.
Ich gehe davon aus, dass ich lediglich die letzte return-Zeile abändern muss, nur wie?

Vversuch es mal ohne die if-Kaskade. Mit dem ternären Operator wäre das max. ein Dreizeiler in dem die Methode einmal sich selber aufruft.

 

[Tobse]

Sollt ihr da auch nachkommastellen bestimmen?

Wenn nein, kannst du mit dem Modulo-Operator arbeiten (falls ihr das dürft) um ein ganzzahliges ergebnis sicherzustellen. Für die Divison sollten auch deutlich weniger zeilen nötig sein als für die addition.
Als kleiner Tipp:

public static int divide(int divisor, int divident)
{
    if (divisor % divident != 0)
    {
        return divide(divisor - (divisor % divident), divident);
    }
    // prüfungen für negative argumente einfügen
    if (divisor != 0)
    {
        // hier reicht eine Zeile mit kompakter schreibweise, 4 mit ausführlicher
    }
    else
    {
        // hier reicht ebenfalls eine
    }
}

 

[blux]

Eine saubere rekursive Lösung ohne if-else ... könnte z. B. so aussehen

    public static int produkt(int a , int b)
    {
    	return (b > a)
    			? 0
    		    : produkt(a-b, b) + 1;
    }

 

[Tobse]

Eine saubere rekursive Lösung ohne if-else ... könnte z. B. so aussehen

    public static int produkt(int a , int b)
    {
    	return (b > a)
    			? 0
    		    : produkt(a-b, b) + 1;
    }

Du vergisst, dass [c](-8)/4 = -2[/c] und [c]4 > (-8)[/c], nach deiner Methode aber [c](-8)/4 = 0[/code] wäre.

 

[blux]

Du vergisst, dass [c](-8)/4 = -2[/c] und [c]4 > (-8)[/c], nach deiner Methode aber [c](-8)/4 = 0[/code] wäre.

Da hast du recht, mit einem Zweig mehr lässt sich aber auch dieses Problem lösen. Das überlass ich dann dem TE - man muss ja nicht alls vorkauen.

 

[hybi]

Vielen Dank für eure Hilfe!
Hab mein Programm mal mit
produkt(a-b, b) + 1;
von Blux ergänzt (danke!). Die Zeile habe ich gebraucht und bin nicht drauf gekommen.

Eine Lösung zum letztgenannten Problem finde ich leider ebenfalls nicht, bin dafür wohl nicht begabt genug um das auf den ersten Blick zu erkennen. Trotzdem danke für die Hilfe!

 

[Tobse]

Dann hier die Auflösung, damit du das auch durchdringen kannst (wird dir ja in der nächsten Stunde weiterhelfen):

    public static int divide(int divisor, int divident)
    {
        if (divident == 0)
        {
            throw new Exception("Division by zero");
        }
        if (divisor == 0)
        {
            return 0;
        }
        if (divisor % divident != 0)
        {
            return divide(divisor - (divisor % divident), divident);
        }
        // prüfungen für negative argumente
        if (divisor < 0 && divident < 0)
        {
            return divide(-divisor, -divident);
        }
        if (divisor < 0 || divident < 0)
        {
            return -divide(divisor < 0? -divisor : divisor, divident < 0? -divident : divident);
        }
        // ab hier greifft blux' code einwandfrei
        return (divident > divisor)
                ? 0
                : divide(divident-divisor, divisor) + 1;
    }

 

[Lazyyy]

Hallo ich würde diesesn Thread gerne noch einmal kurz aufgreifen ..
Bei diesem Lösungsversuch sollen Sonderfälle mit -1 abgebrochen werden. Ansonsten soll der Rest berechnet werden.
Aktuelles Problem: bekomme beim testen manchmal einen "time out" Fehler.
Ist der Gedanke richtig das result sozusagen den Zähler, wie oft der divisor in den dividenden passt darstellt?

public class Modulo {

   public int calculate(int dividend, int divisor) {
       int result = 0;
       if(divisor <= 0 || dividend < 0)return -1;
       
       while(dividend > divisor){
           result =1+ calculate(dividend-divisor, divisor);
       }
       return dividend - result*divisor;
   }
}

 

[mrBrown]

Hallo ich würde diesesn Thread gerne noch einmal kurz aufgreifen ..

Dazu hättest du auch einen eigenen Thread aufmachen können

Aktuelles Problem: bekomme beim testen manchmal einen "time out" Fehler.

Der Fehler ist erstmal, dass du Schleife und Rekursion mischst.

Die Schleife läuft, so lange dividend > divisor, beide Werte werden aber nie verändert - die Schleife läuft aber endlos.

Ist der Gedanke richtig das result sozusagen den Zähler, wie oft der divisor in den dividenden passt darstellt?

Ja.

 

[Lazyyy]

Lösungsvorschlag: while schleife durch if bedingung zu ersetzen.
10 % 2 sollte 0 ergeben, hier kommt 28 raus. 10 -5*2 = 0 ..
Bei jedem aufruf ändert sich doch der dividend ?

if(divisor < dividend){
           result = calculate(dividend-divisor, divisor) + 1;   
       }
return dividend - result*divisor;