Rekursives Problem....

S

Soltan

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

gegeben ist die Methode

Code:
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

Robat

Top Contributor
Wie wäre es bspw. damit:
Java:
public static boolean x(int a) {
  if(a < 10) {
      return a != 0;
  } else {
      return true ^ x(a/10);
  }
}
 
S

Soltan

Aktives Mitglied
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 ?
 
B

Barista

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

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

Java:
String numStr = String.valueOf( a );

Dann sollte man die Null-Ziffern zählen.

Am einfachsten mit einer Schleife.
Java:
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.

Java:
return ( zeroCount % 2 ) != 0;

Leider ist eine Schleife verboten.

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

Java:
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 ) );
}
 
S

Soltan

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

Soltan

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

Robat

Top Contributor
Habs gerade noch mal überarbeitet. Wenn mich nicht alles täuscht dürfte das jetzt funktionieren.
Java:
public static boolean x(int a) {
    if(a < 10) {
        return a == 0;
    } else {
        return (a%10 == 0) ^ x(a/10);
    }
}
 
B

Barista

Bekanntes Mitglied
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.
 
S

Soltan

Aktives Mitglied
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 ?
 
S

Soltan

Aktives Mitglied
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.....
 
S

Soltan

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

Robat

Top Contributor
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.
Code:
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.
 
B

Barista

Bekanntes Mitglied
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.

Java:
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.
 
S

Soltan

Aktives Mitglied
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*
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
M Rekursives Programm zum Anzeigen von Primzahlen Java Basics - Anfänger-Themen 3
C Rekursives Backtracking beim Spiel Peg Java Basics - Anfänger-Themen 22
G Rekursives Programmieren --> harmonische Reihe Java Basics - Anfänger-Themen 3
S Rekursives Durchlaufen eines Verzeichnisses - AccessDeniedException behandeln Java Basics - Anfänger-Themen 1
S Rekursives Zählen einer Zahl Java Basics - Anfänger-Themen 8
J Rekursives Parsen (ohne Reg Expressions) Java Basics - Anfänger-Themen 8
S Rekursives Umdrehen, Spiegeln. etc. von Strings Java Basics - Anfänger-Themen 3
I Rekursives Löschen in Binärem Suchbaum Java Basics - Anfänger-Themen 2
L rekursives spiel programmieren Java Basics - Anfänger-Themen 4
G Rekursives aufrufen führt zu StackOverflowError Panel durchl Java Basics - Anfänger-Themen 5
M Rekursives suchen im TreeMenu Java Basics - Anfänger-Themen 10
N Rekursives suchen in einer Liste Java Basics - Anfänger-Themen 8
G Primzahlentester als rekursives Programm! Java Basics - Anfänger-Themen 13
H Rekursives einlesen von Lokalen Ordner Java Basics - Anfänger-Themen 4
J Allgemeines Problem mit Klassen Java Basics - Anfänger-Themen 2
U Problem mit dem initialisieren meines Strings in einer Schleife Java Basics - Anfänger-Themen 4
amgadalghabra algorithmisches Problem Java Basics - Anfänger-Themen 19
J Traveling Salesman Problem [Arrays] Java Basics - Anfänger-Themen 9
R ArrayList Problem Java Basics - Anfänger-Themen 6
InfinityDE Problem mit Datenübergabe an Konstruktor Java Basics - Anfänger-Themen 7
C RegEx Problem Java Basics - Anfänger-Themen 4
J Anfänger TicTacToe, Problem bei Gewinnoption, sowohl Unentschieden Java Basics - Anfänger-Themen 8
E Taschenrechner GUI Problem mit Fehlerhandling Java Basics - Anfänger-Themen 6
M Input/Output Fallunterscheidung Problem Java Basics - Anfänger-Themen 17
P Problem beim Überschreiben einer vererbten Methode Java Basics - Anfänger-Themen 4
M Problem bei Ausgabe Java Basics - Anfänger-Themen 7
S Java Array Problem... Java Basics - Anfänger-Themen 2
G Problem bei der Ausgabe einer Main Claase Java Basics - Anfänger-Themen 7
F Problem mit KeyListener in kombination mit dem ActionListener Java Basics - Anfänger-Themen 4
L Subset sum problem mit Backtracking Java Basics - Anfänger-Themen 18
N Problem mit Scanner Java Basics - Anfänger-Themen 2
J Klassen Problem Java Basics - Anfänger-Themen 8
A Out.format problem. Java Basics - Anfänger-Themen 3
J Problem bei der Programmierung eines Tannenbaums Java Basics - Anfänger-Themen 9
A Array problem Java Basics - Anfänger-Themen 16
2 Taschenrechner mit GUI Problem bei der Berechnung Java Basics - Anfänger-Themen 8
W Remote Method Invocation RMI - Problem Java Basics - Anfänger-Themen 0
I Ich habe ein Problem Java Basics - Anfänger-Themen 3
A Problem bei returnen eines Wertes Java Basics - Anfänger-Themen 6
M Regex Erstellung Problem Java Basics - Anfänger-Themen 2
D Input/Output Problem bei der Benutzereingabe eines Befehls Java Basics - Anfänger-Themen 14
M (Sehr großes Problem) Listen als static in anderen Klassen verwendet Java Basics - Anfänger-Themen 12
F Habe ein problem mit dem ActionListener Java Basics - Anfänger-Themen 3
C Regex-Problem Java Basics - Anfänger-Themen 4
J Problem beim vergleich von zwei Integer Java Basics - Anfänger-Themen 3
M Problem in der Modellierung Java Basics - Anfänger-Themen 20
W Wo ist das URL-Problem ? Java Basics - Anfänger-Themen 1
S Generics-Problem: Class, Class<?>, Class<Object> Java Basics - Anfänger-Themen 4
D FileWriter / FileReader Problem Java Basics - Anfänger-Themen 10
G Problem beim Speichern von Objekten in einer Datei Java Basics - Anfänger-Themen 7
S Compiler-Fehler Exception in thread "main" java.lang.Error: Unresolved compilation problem: Java Basics - Anfänger-Themen 6
J Problem mit Array: 2 Klassen Java Basics - Anfänger-Themen 2
S Collections funktionale Listen (ListNode<E>) review und problem beim clone Java Basics - Anfänger-Themen 0
W OOP Vererbung und Problem bei Zählschleife in einer Methode Java Basics - Anfänger-Themen 10
C Problem mit If Else If und Überprüfung eines Counters Java Basics - Anfänger-Themen 3
F Problem mit Listen Java Basics - Anfänger-Themen 5
I wieder mit einer Umwandelung habe ich Problem (diesmal von char Array zu char) Java Basics - Anfänger-Themen 1
J Problem bei Umrechnung von Hex in Bin Java Basics - Anfänger-Themen 4
W Problem bei Programmierung von Monte-Carlo-Integration Java Basics - Anfänger-Themen 12
C Java Methoden "Parameter" Problem Java Basics - Anfänger-Themen 16
T Bruchrechner Problem Java Basics - Anfänger-Themen 16
M Problem mit meinem Programm Java Basics - Anfänger-Themen 6
pkm Problem mit der JSP-Syntax Java Basics - Anfänger-Themen 2
J Rückgabe-Problem Java Basics - Anfänger-Themen 10
D Problem mit der Serialisierung Java Basics - Anfänger-Themen 31
W Problem mit dem Wert von boolean-Variable Java Basics - Anfänger-Themen 3
W Problem mit Konsolenausgabe bei StringTokenizer Java Basics - Anfänger-Themen 2
O Verständniss Problem bei abstract class Java Basics - Anfänger-Themen 7
K Java Problem mit Übergabe von argumenten Java Basics - Anfänger-Themen 3
J "travelling salesman problem" mit Java Editor Java Basics - Anfänger-Themen 17
M Problem mit ArrayList Java Basics - Anfänger-Themen 32
B Array Problem Java Basics - Anfänger-Themen 3
O Problem mit SOAP / javax.xml importieren Java Basics - Anfänger-Themen 7
V Variablen Problem mit Matheaufgabe / int first = mScanner.nextInt(); Java Basics - Anfänger-Themen 5
X Problem mit Arraylist in Arraylist Java Basics - Anfänger-Themen 2
cpt.Tomato Scanner problem mit Passwort Login Java Basics - Anfänger-Themen 3
F Switch Case Problem mit Regex lösen? Java Basics - Anfänger-Themen 6
CT9288 Mini Anfänger-Problem mit loops, statements und ; Java Basics - Anfänger-Themen 4
C Two-Center Problem in Java Java Basics - Anfänger-Themen 0
H regex-Problem Java Basics - Anfänger-Themen 2
J Problem bei seriellem Start von Threads Java Basics - Anfänger-Themen 11
E Weg-Suche-Problem rekursiv Java Basics - Anfänger-Themen 12
C Problem: PC ohne Internet und keine Möglichkeit Programme zu laden Java Basics - Anfänger-Themen 5
E Problem mit static Methode Java Basics - Anfänger-Themen 4
J Problem bei Aufgabe "Geldstückelung" Java Basics - Anfänger-Themen 5
P Problem bei Java-Aufgabe Java Basics - Anfänger-Themen 12
T Rückgabewert Problem Java Basics - Anfänger-Themen 2
O Problem gleiche Zahlen Java Basics - Anfänger-Themen 2
C Methoden Problem beim Speichern von Variablen Java Basics - Anfänger-Themen 1
W Problem bei JUnit Test Aufgabe Java Basics - Anfänger-Themen 15
D Break Sprungmarken Problem einer While True in While True Java Basics - Anfänger-Themen 6
J "Tetris" - Problem bei der Grafik Java Basics - Anfänger-Themen 5
L Klassen NFC Reader und JavaFx Problem -> threads? Java Basics - Anfänger-Themen 2
C Hamster Simulator Problem Java Basics - Anfänger-Themen 2
S CSV auslesen UTF-8 Problem Java Basics - Anfänger-Themen 7
F Problem beim entfernen von mehreren Listenelementen auf einmal (Programmierung des Spiels Arschloch) Java Basics - Anfänger-Themen 1
felix92 eclipse Problem Java Basics - Anfänger-Themen 12
J unzip Problem Java Basics - Anfänger-Themen 5
J Pizza und Pasta Problem.. Java Basics - Anfänger-Themen 19
F Problem mit der Aufgabe(Array) Java Basics - Anfänger-Themen 21

Ähnliche Java Themen

Anzeige

Neue Themen


Oben