Integer Division mit Rekursion - und ein paar andere interessante Einschränkungen

Question

Ich versuche ein Puzzle in Java für meine eigene Erbauung zu lösen. Mir wurde gesagt, ist eine Lösung von dem Mann, der das Puzzle entworfen, aber ich bin nicht in der Lage, es selbst zu finden.

Hier ist das Rätsel:

Implementieren Sie die folgende Methode in Java

/** 
* Divides a natural number by two. 
* 
* @param n 
*   The number to be divided 
* @updates n 
* @ensures n = floor(n/2) 
*/ 
private static void split(NaturalNumber n) {...} 

Die natürliche Zahl Klasse einfach eine Klasse, die eine natürliche Zahl speichert eine Zeichenfolge verwendet wird. (Das heißt, es kann Nummern speichert viel größer als Integer.MAX_VALUE.)

Die Klasse diesen und inherited methods sowie die NaturalNumber.isZero() Methode bietet, die gibt true zurück, wenn die internen String-Wert der Instanz "0" ist, falsche sonst .

Es ist erwähnenswert, dass die NaturalNumber.divideBy10() Methode im Wesentlichen die rechte Ziffer aus der Zahl erscheint, gibt es als int und aktualisiert die internen Wert der Instanz.

Verwenden Sie keine statischen Eigenschaften für die Hauptklasse, um Werte zu speichern. Schreiben Sie keine statischen Hilfsmethoden.

Konvertieren Sie n nicht in einen anderen Datentyp und arbeiten Sie damit. Verwenden Sie keine externen Bibliotheken.

Außerdem muss split() durch Rekursion implementiert werden.

Ich habe folgende in der Nähe von Lösung ausgearbeitet:

private static void split(NaturalNumber n) { 
    // Initialize local variables. 
    String stringBuffer = ""; 
    int numerator = 0; 
    int quotient = 0; 
    int remainder = 0; 

    int thisDigit = n.divideBy10(); 

    if (n.isZero()) { 
    quotient = thisDigit/2; 
    remainder = thisDigit % 2; 
    n.transferFrom(new NaturalNumber2(quotient * 10 + remainder)); 
    } else { 
    split(n); 
    numerator = n.divideBy10() * 10 + thisDigit; 
    quotient = numerator/2; 
    remainder = numerator % 2; 
    if (!n.isZero()) { 
     stringBuffer += n.toString(); 
    } 
    stringBuffer += Integer.toString(quotient * 10 + remainder); 
    n.transferFrom(new NaturalNumber2(stringBuffer)); 
    } 
} 

Die obigen einfach lange Teilung führt. Aber der letzte Frame in dem Aufruf-Stack fügt unnötigerweise den Rest seiner Operation an das Ende der Lösung an.

Ich habe Lösungen zu ähnlichen Problemen gesehen, die rekursiv zwei von n subtrahieren und zählen, wie oft zwei für n abgezogen werden müssen, um Null zu werden. Diese Lösungen beruhen jedoch darauf, dass das Verfahren einen Rückgabewert aufweist; Dieses Puzzle erfordert, dass es keinen Rückgabewert gibt.

Ich kann auch sehen, wie das Rätsel mit einem Funktionsaufruf zu split() und interne Schleifen lösen. Aber mir wurde gesagt, dass die Lösung sich nicht auf Schleifen verlassen muss, um auf n zu arbeiten.

Hat jemand da draußen einen Einblick in eine Lösung?

Answer 1

Angenommen, die Ziffern von n sind a...yz. Wenn y gerade ist, dann sind die Ziffern von n/2 die Verkettung von a...y/2 und z/2. Wenn y ungerade ist, lassen Sie Y = y - 1. Dann sind die Ziffern n/2 die Verkettung von a...Y/2 und 1z/2.

Wir können dies wie folgt implementieren:

private static void split(NaturalNumber n) { 
    int z = n.divideBy10(); 
    int y = n.divideBy10(); 

    if (n.isZero()) { 
     // Base case. 
     int result = (y * 10 + z)/2; 
     n.multiplyBy10(result/10); 
     n.multiplyBy10(result % 10); 
    } else if (y % 2 == 0) { 
     n.multiplyBy10(y); 
     split(n); 
     n.multiplyBy10(z/2); 
    } else { 
     n.multiplyBy10(y - 1); 
     split(n); 
     n.multiplyBy10((10 + z)/2); 
    } 
} 

übrigens diese Methodennamen sind schrecklich, und machen NaturalNumber s wandelbar ist eine seltsame Design-Wahl.