Rekursives Problem....

[Soltan]

Hallo... habe heute leider bei meinem Test versagt und bin im Endeffekt an folgendem Beispiel gescheitert....

gegeben ist die Methode

private static boolean x (int a){
}

Wir sollen diese Methode ( mit exakt dieser Signatur ) so erweitern dass sie wenn eine Zahl eine ungerade Anzahl an NULLEN hat true ausgibt.... und bei einer geraden Anzahl an nullen false..... leider hab ich keine Ahnugn wie ich das lösen sollte... Kann mir bitte jemand erklären was die Lösung gewesen wäre ?

Also zB wenn die Zahl "52402401" übergeben wird (beinhaltet 2 nullen) dann wird false ausgegeben. Bei bsp. "50100" wird true ausgegeben. Die Methode ist vom typ boolean an den Parametern darf natürlich nichts geändert werdne und Schleifen darf man auch keine benutzen.....

 

[Robat]

Wie wäre es bspw. damit:

public static boolean x(int a) {
  if(a < 10) {
      return a != 0;
  } else {
      return true ^ x(a/10);
  }
}

 

[Soltan]

Hmm aber wo checkt das ob es ne gerade oder ungerade Anzahl an 0en ist ? Soweit ich das verstehe geht diese lösung immer tiefer bis überprüft wird ob die letzte Stelle keine Null ist. Wenn sie keine null ist dann kommt true zurück und und somit entsteht durch das logische xor ein false. wenn es eine ist dann kommt false zurück und es ist somit true... oder ? Wo wird überprüft ob es ne gearde oder ungerade ANZAHL an 0en ist ?! Was ist die Idee hinter der Lösung ?

 

[Robat]

Vergiss den Post oben. Hatte einen Gedankenfehler

 

[Barista]

Wahrscheinlich sollen die Nullen in der Dezimaldarstellung der Zahl gezählt werden.

Ich würde die übergebene Zahl erst mal in einen String umwandeln.

String numStr = String.valueOf( a );

Dann sollte man die Null-Ziffern zählen.

Am einfachsten mit einer Schleife.

int zeroCount = 0;
for ( int pos = 0 ; pos < numStr.length() ; pos++ )
{
    if ( numStr.charAt( pos ) == '0' )
    {
         zeroCount++;
    }
}

Ob die Zahl gerade ist, kann mit dem Modulo-Operator erfahren.

return ( zeroCount % 2 ) != 0;

Leider ist eine Schleife verboten.

Für eine rekursive Lösung benötigst Du eine weitere Methode.

private int countZerosRecursiv( String numStr )
{
    if ( numStr.isEmpty() )
    {
        // Rekursion terminiert
        return 0;
    }

    final int firstZeroCount;
    if ( numStr.charAt( 0 ) == '0' )
    {
        firstZeroCount = 1;
    }
    else
    {
       firstZeroCount = 0;
    }

    return
         firstZeroCount +
         // rekursiver Aufruf
         countZerosRecursiv(
                // Rest (tail) an rekursiven Aufruf übergeben
                numStr.substring( 1 ) );
}

 

[Soltan]

Hmm... irgendne andere idee ? Finde das Beispiel ist irgendwie derb für nen Anfänger Kurs....

 

[Soltan]

Eine weitere Methode ist nicht gestattet.... Es soll nur diese Methode verwendet werden.

 

[Soltan]

Ja es stand irgendwas mit einer Dezimaldarstellung ....

 

[Robat]

Habs gerade noch mal überarbeitet. Wenn mich nicht alles täuscht dürfte das jetzt funktionieren.

public static boolean x(int a) {
    if(a < 10) {
        return a == 0;
    } else {
        return (a%10 == 0) ^ x(a/10);
    }
}

 

[Barista]

Es soll keine weitere Methode verwendet werden.

Dann wird es ja richtig interessant.

Ist für einen Einsteigerkurs echt heftig.

Ich starte mal meine Eclipse und melde mich in ein paar Minuten wieder.

 

[Soltan]

Ich habe keine Ahnung wie ich üben soll so ein Beispiel aus dem nichts heraus innerhalb von 10 Minuten unter Stress zu bewältigen. Sowas muss doch irgendwie in Ruhe durchdacht werden ... Wie übe ich das am besten ?

 

[Soltan]

Ich glaube Robats Ansatz ist quasi der Base case ist 1ne 0. dh Das ist ein true. Dann wird mit der nächsten ( eine Rekursion zurück) verglichen wenn das auch 0 ist ( 2 0en sind ne gerade Anzahl) dann wird durch das xor ein false daraus usw bis ganz nach oben. Man zählt im Endeffekt garnichts dabei sondern es wrd automatisch umgestellt durch das xor.... Bei jeder Null quasi verändert sich die Ausgabe damit von true zu false bzw umgekehrt.....

 

[Soltan]

ber ganz ehrlich... nicht in 100 Jahren wäre ich da innerhalb kürzester Zeit im labor drauf gekommen.... wie übe ich das ???

 

[Robat]

Man zählt im Endeffekt garnichts dabei sondern es wrd automatisch umgestellt durch das xor.... Bei jeder Null quasi verändert sich die Ausgabe damit von true zu false bzw umgekehrt.....

So sieht es aus. Man will erzielen dass sich nur bei einer 0 etwas ändert.
Hier das ganze noch mal an 2 Beispielen ausführlich durchgespielt.

Spoiler: Beispiele

x(7003812)                           false
--return (2 == 0) ^ x(700381)        false ^ false = false
----return (1 == 0) ^ x(70038)       false ^ false = false
------return (8 == 0) ^ x(7003)      false ^ false = false
--------return (3 == 0) ^ x(700)     false ^ false = false
----------return (0 == 0) ^ x(70)     true ^ true  = false
------------return (0 == 0) ^ x(7)    true ^ false = true
--------------return 7 == 0          false


 

x(45099080)                              true
--return (0 == 0) ^ x(4509908)           true ^ false = true
----return (8 == 0) ^ x(450990)         false ^ false = false
------return (0 == 0) ^ x(45099)         true ^ true  = false
--------return (9 == 0) ^ x(4509)       false ^ true  = true
----------return (9 == 0) ^ x(450)      false ^ true  = true
------------return (0 == 0) ^ x(45)      true ^ false = true
--------------return (5 == 0) ^ x(4)    false ^ false = false
----------------return (4 == 0)         false

Wie man sowas am Besten übt? Naja .. stell dir selber Aufgaben zur Rekursion aus verschiedensten Gebieten und versuche sie zu lösen.

 

[Barista]

Ich glaube, ich habe es.

Bei der Rekursion muss der übergebene Wert einem Abbruchkriterium zustreben.

Deshalb die Division durch 10.

Weiterhin muss bei Verwendung nur dieser einen Methode das Ergebnis-Boolean der aktuellen Null-Prüfung mit dem Ergebnis-Boolean der rekursiv aufgerufenen Null-Prüfung verknüpft werden.

Ich habe hier auf XOR-Verknüpfung getippt.

Ich habe gleich noch einen JUnit4-Test draus gemacht, wenn Du diesen nachvollziehen willst musst Du in der Eclipse die JUnit4-Lib zum Projekt hinzufügen, bei anderen IDEs weiss ich nicht, wie das geht.

package zero_count_is_odd_recursive;

import org.junit.Assert;
import org.junit.Test;

/*
 * https://www.java-forum.org/thema/rekursives-problem.180607/
 */
public class ZeroCountIsOddRecursive {
 public static boolean zeroCountIsOddRecursive(final int a) {
 
  if ( a < 0 ) {
   throw new IllegalArgumentException( String.valueOf( a ) );
  }
 
  if ( a < 10 )
   // Rekursion terminiert
  {
   // eine 0 ist ungerade, also true
   return a == 0;
  }
 
  final boolean lastDigitIsZero = ( a % 10 ) == 0;
 
  // bei der int-Division einer positiven Zahl in Java wird immer abgerundet, dadurch wird die lezte Stelle abgeschnitten
  final int nextA = a / 10;
 
  System.out.println( a + " -> " + nextA );
 
  // Hier wuerde es auch mit XOR klappen
  if ( lastDigitIsZero ) {
   return ! zeroCountIsOddRecursive( nextA );
  } else {
   return zeroCountIsOddRecursive( nextA );
  }
 
 }
 @Test
 public void test0() {
 
  Assert.assertEquals(
    //expected
    true ,
    //actual
    zeroCountIsOddRecursive( 0 ) );
 
 
 }
 @Test
 public void test1() {
 
  Assert.assertEquals(
    //expected: Anzahl 0 ist gerade
    false ,
    //actual
    zeroCountIsOddRecursive( 1 ) );
 
 
 }
 @Test
 public void test10() {
 
  Assert.assertEquals(
    //expected
    true ,
    //actual
    zeroCountIsOddRecursive( 10 ) );
 
 
 }
 @Test
 public void test11() {
 
  Assert.assertEquals(
    //expected: Anzahl 0 ist gerade
    false ,
    //actual
    zeroCountIsOddRecursive( 11 ) );
 
 
 }
 @Test
 public void test110() {
 
  Assert.assertEquals(
    //expected
    true ,
    //actual
    zeroCountIsOddRecursive( 10 ) );
 
 
 }
 @Test
 public void test111() {
 
  Assert.assertEquals(
    //expected: Anzahl 0 ist gerade
    false ,
    //actual
    zeroCountIsOddRecursive( 11 ) );
 
 
 }
 @Test
 public void test100() {
 
  Assert.assertEquals(
    //expected
    false ,
    //actual
    zeroCountIsOddRecursive( 100 ) );
 
 
 }
 @Test
 public void test101() {
 
  Assert.assertEquals(
    //expected
    true ,
    //actual
    zeroCountIsOddRecursive( 101 ) );
 
 
 }
 @Test
 public void test1000() {
 
  Assert.assertEquals(
    //expected
    true ,
    //actual
    zeroCountIsOddRecursive( 1000 ) );
 
 
 }
 @Test
 public void test1001() {
 
  Assert.assertEquals(
    //expected
    false ,
    //actual
    zeroCountIsOddRecursive( 1001 ) );
 
 
 }
 
}

Die Lösung von Robat ist äquivalent zu meiner, aber erheblich kürzer.

 

[Soltan]

Mann.... ich bin so enttäuscht von mir.... Habe vor 4 Monaten angefangen mit dem Programmieren und wollte das wirklich schaffen... Leider waren alle Beispiele die ich im Netz gefunden habe von gänzlich anderer Art.... Es ist echt schwierig so Rekursions Probleme adhoc zu lösen wenn man noch nie vor genau DIESES Problem gestellt wurde oder ein ähnliches.... (und es einmal durchgedacht hat) Muss da irgendeinen Weg finden um das grundlegend zu verstehen ohne darüber nachdenken zu müssen... keine Ahnung. *seufz*

 

[Soltan]

Aber das ist mit Sicherheit die Lösung.... vielen dank euch.... :/