Rekursion und Multiplikation

Ist das möglich Jungs? Das ist Hausaufgaben, die ich habe, und mein Lehrer, der offensichtlich glaubt, dass es ist, aber es scheint mir, dass es unmöglich ist, nicht zu verwenden, addition oder Multiplikation, die außerhalb des kurz-Multiplikation-Methode.

Schreiben (und bieten einen tester für) einen rekursiven Algorithmus:

int multiplizieren(int x, int y)

multiplizieren von zwei positiven ganzen zahlen zusammen, ohne die Verwendung von *
Betreiber. Nicht nur hinzufügen, dass x sich y mal!!!!!

(Tipp: Schreiben Sie eine rekursive Methode, mit der man multipliziert eine ganze Zahl durch eine
Wert im Bereich von 0 .. 10. Schreiben Sie dann eine zweite rekursive Methode
implementieren Sie den Algorithmus zur Matrixmultiplikation Sie gelernt, sich zu vermehren
mehrstellige zahlen in der Grundschule.)

Mein Problem ist, dass, wenn Sie brechen alle multi-stellige Nummer und starten das hinzufügen dieser zusammen, verwenden Sie die Multiplikation von zahlen größer als 10, ich.e 22 * 6 2 * 6 + 20 * 6 ... so bin ich Total fehlt etwas?

BEARBEITEN
Ich glaube, ich sollte Hinzugefügt haben, ist dies der code, den ich habe,

public int mult(int x, int y){
return x == 0 ? 0 : (mult(x-1, y) + y);
}

perfekt ist, aber soweit verstehe ich die Anleitung, dass das brechen nicht nur hinzufügen, dass x sich y mal. Ich persönlich glaube es nicht, aber mein Lehrer war nicht sehr klar, und ich würde gerne wissen, ob es irgendeine andere Möglichkeit, die ich noch nicht gedacht, sorry für die Verwirrung.

Es ist sehr gut möglich. Was haben Sie versucht?
Bitte aktualisieren Sie dies, wenn der Lehrer hatte eine andere Lösung, dann die gegebene rekursive Funktionen.
Ich werde, es wird ein paar Tage dauern, aber da es nicht wirklich aufgrund der bis zu diesem Abend.
noch havn ' T erhielt Antwort, incase jemand wissen will

InformationsquelleAutor SomeGuyWithFingers | 2013-04-17

Meine interpretation der Zuordnung ist, dass die Lehrerin möchte die Schüler zur Implementierung eines rekursiven Algorithmus ausführen Grid-Methode der Multiplikation (die Art, wie wir lernen in der Grundschule).

Beispielsweise die Multiplikation 34 x 13 erfolgen würde, wie so...

  34
* 13
====
  12
  90
  40
+300
====
 442

Ich nicht haben einfachen Zugang zu einer Java-Entwicklungsumgebung, also schrieb ich den code in C#, aber der Algorithmus sollte einfach genug, um zu konvertieren in Java.

public int Multiply(int x, int y)
{
    if (x < 0) throw new ArgumentException("must be positive integer", "x");
    if (y < 0) throw new ArgumentException("must be positive integer", "y");

    if (x == 0 || y == 0) return 0; //obvious quick-exit condition

    //integer division
    int xDivBy10 = x / 10;
    int yDivBy10 = y / 10;

    bool xIsSingleDigit = xDivBy10 == 0;
    bool yIsSingleDigit = yDivBy10 == 0;

    //base case
    if (xIsSingleDigit && yIsSingleDigit)
    {
        return MultiplySingleDigits(x, y);
    }

    //otherwise, use grid multiplication recursively
    //http://en.wikipedia.org/wiki/Grid_method_multiplication

    if (xIsSingleDigit) //y must not be a single digit
    {
        return (Multiply(x, yDivBy10) * 10) + Multiply(x, y % 10);
    }

    if (yIsSingleDigit) //x must not be a single digit
    {
        return (Multiply(xDivBy10, y) * 10) + Multiply(x % 10, y);
    }

    //else - x and y are both numbers which are not single digits
    return (Multiply(x, yDivBy10) * 10) + Multiply(x, y % 10); //the same code as the "if (xIsSingleDigit)" case
}

//technically, this algorith can multiply any positive integers
//but I have restricted it to only single digits as per the assignment's requirements/hint
private int MultiplySingleDigits(int x, int y)
{
    if (x < 0 || x > 9) throw new ArgumentException("must be in range 0 - 9 (inclusive)", "x");
    if (y < 0 || y > 9) throw new ArgumentException("must be in range 0 - 9 (inclusive)", "y");

    if (x == 0 || y == 0) return 0; //base case
    return x + MultiplySingleDigits(x, y - 1);
}

HINWEISE:

Dieser Ansatz verwendet immer noch die * Betreiber aber nicht für die eigentliche Multiplikation x und y es wird verwendet, um zu erhöhen, andere sub-Produkte mit einem vielfachen von 10
Viele Teile des code vereinfacht werden könnte/umgestaltet werden, aber ich speziell Links, Sie erweitert, um die Schritte deutlicher

das ist, was ich zu denken...
Also das ist, was ich war was bedeutet, aber ich weiß noch nicht wirklich sehen, wie es ist alles anders, denn ich bin noch etwas hinzuzufügen, um sich eine andere Zahl von Zeiten. Wie auch immer, ich wirklich zu schätzen die Hilfe!
Aus Klängen, die die Zuordnung der Lehrer nicht auf der Suche ist für die Effizienz; Sie sind mehr daran interessiert, Sie denken über die algorithmischen Schritte. Ich bin noch nicht überzeugt, dass dies ist, was Sie suchen (weil es verwendet die * Betreiber und theprivate-Methode weiterhin verwendet der Algorithmus, den Sie kam schon mit), aber es scheint am nächsten zu dem, was der Lehrer nach.

InformationsquelleAutor Jesse Webb

5

Ja, es ist möglich. Ja, ich glaube, du bist etwas fehlt. Schreiben Sie hinunter die Schritte, die Sie Folgen würden, um manuell multiplizieren von zwei zahlen, die Art, wie Sie schon in der Grundschule gelernt.

Dann schalten Sie diese Schritte in code.

InformationsquelleAutor CPerkins
1

Natürlich können Sie es tun.

Zuerst von all, denken Sie über den Zustand. Wenn eine Zahl 0 ist, dann ist das Ergebnis? Richtig.. null.

So.. Sie haben if x is zero or y is zero return 0

Nun.. sagen X * Y ist wie gesagt "X -, Y-mal", das ist wie beim schreiben: X + .... + X (Y mal).

Also musst du so etwas wie:
```
x + multiply(x, y - 1);
```
Müssen Sie berücksichtigen den Fall, in dem eine der zahlen negativ ist (Aber wenn Sie verstehen, die grundlegende, ich glaube, Sie können ganz einfach tun es).
- wie ist das nicht "Tun nicht nur x sich y mal"?
- Ich glaube, er sagt ihm, nicht zu verwenden, - Schleifen.
InformationsquelleAutor Maroun
0

Problemlos möglich.
```
int multiply(int x, int y) {
    if(y == 0) {
        return 0;
    }
    return x + multiply(x, y - 1);
}
```
Oben nicht zu berücksichtigen für den Fall, wo y negativ ist, aber Sie würde nicht wollen, mich zu tun, alle Ihre arbeiten für Sie . . .
- wie ist das nicht "Tun nicht nur x sich y mal"?
- Ich gehe davon aus, dass der Unterricht bezieht sich auf for-Schleifen.
- ja, das ist mein Problem ich dachte ursprünglich meinte er einfach nicht Durchlaufen, aber jetzt bin ich mir nicht so sicher
- haben Sie ihn gebeten?
- ja, die ganze Klasse hatte eine Diskussion darüber...meine interpretation war, dass er meinte sogar, dass die rekursive version war nur das hinzufügen x + x y-mal, aber jetzt, wo ich darüber nachdenke, vielleicht war es nur über iteration...class ist ein bisschen laut. Sowieso, es sei denn, jemand hat eine andere Idee, werde ich einfach sagen, dass das die Antwort ist.
InformationsquelleAutor Aurand

Diese Lösung funktioniert für beide, wenn y>=0 und y<0

public int multiply(final int x, final int y) {
    if (y != 0 && x != 0) {
        if (y > 0) {
            return multiply(x, y - 1) + x;
        } else {
            return multiply(x, y + 1) - x;
        }
    }
    return 0;
}

Wie funktioniert dieses erfüllen Do not just add x to itself y times?

InformationsquelleAutor rekinyz

    static int Multiply(int x, int y)
    {
        if (y > 0 && x > 0)
            return (x + Multiply(x, y - 1));
        if (y < 0 && x > 0)
            return -Multiply(x, -y);
        if (x < 0 && y > 0)
            return -Multiply(-x, y);
        if (x < 0 && y < 0)
            return Multiply(-x, -y);

        return 0;
    }

Hallo, herzlich Willkommen auf Stack-Überlauf und vielen Dank für Ihre erste Antwort. Um die Antwort nützlich für andere Menschen, ist es am besten Praxis, um kommentieren Sie Ihre Antwort mit text, der erklärt, warum es geht auf die OP ' s ursprüngliche Frage.
Wie funktioniert dieses erfüllen Do not just add x to itself y times?

InformationsquelleAutor polinens

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.