Rekursives Suchen Blue J

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • Rekursives Suchen Blue J

    Ich hab grade gesehen, dass die Aufgabe mit der Literaturliste die falsche Aufgabe ist stattdessen ist das meine Aufgabe...

    Dafür fehlen mir noch das Sortieren und die abschaltbaren Methoden...Kann wer helfen?

    Geben Sie rekursive Lösungen für die binäre Suche in einem Array (bzw. in einer Objekt-
    Sammlung) sowie für das Sortieren durch Auswahl in einem Array (in einer
    Objektsammlung) an. Fügen Sie abschaltbare Ausgaben hinzu, die die Arbeitsweise der
    Methoden verdeutlichen.

  • Hier mal meine bisherige Lösung...

    Quellcode

    1. public class BinaereSuche {
    3. // Attribute
    4. int[] feld; // speichert das zu durchsuchende Array
    5. int l; // linke Grenze des Suchbereichs
    6. int r; // rechte Grenze des Suchbereichs
    7. int m; // Mitte
    8. int s; // das zu suchende Element
    10. // Konstruktor
    11. public BinaereSuche(int[] feld) {
    12. this.feld = feld;
    13. s = l = r = m = 0;
    14. }
    16. // startet die rekursive Suche
    17. // führt Initialisierungsarbeiten aus
    18. public int sucheRekursiv(int s) {
    20. // Array null oder leer?
    21. if (feld == null || feld.length == 0)
    22. return -1; // Fehlerwert zurückgeben
    24. // Variablen initialisieren
    25. l = 0;
    26. r = feld.length - 1;
    27. this.s = s;
    29. // startet die eigentliche Rekursion
    30. return binaerRek();
    31. }
    33. // prüft rekursiv, ob ein bestimmtes Element im
    34. // Array vorhanden ist und gibt den Index der Position
    35. // des gefundenen Elements zurück
    36. public int binaerRek() {
    38. m = (l + r) / 2; // Berechnung der Mitte
    39. print(); // Ausgabe des Status auf der Konsole
    41. // Abbruchbedingung (Rekursionsbasis)
    42. if (l > r)
    43. return -1;
    45. // suche s im linken Teilfeld
    46. if (s < feld[m]) {
    48. r = m - 1;
    49. return binaerRek();
    51. }
    52. // suche s im rechten Teilfeld
    53. else if (s > feld[m]) {
    55. l = m + 1;
    56. return binaerRek();
    58. }
    59. // s wurde an Position m gefunden
    60. else
    61. return m;
    62. }
    64. // gibt den aktuellen Status der Suche auf
    65. // der Konsole aus
    66. public void print() {
    68. // gibt zuerst den Inhalt des Arrays aus
    69. for (int i = 0; i < feld.length; i++)
    70. System.out.print(feld[i] + " ");
    72. System.out.println();
    74. // zeigt die Positionen der einzelnen "Zeiger"
    75. // innerhalb des Arrays an
    76. for (int i = 0; i < feld.length; i++) {
    78. if (i == m)
    79. System.out.print("m");
    80. else if (i == l)
    81. System.out.print("l");
    82. else if (i == r)
    83. System.out.print("r");
    84. else
    85. System.out.print(" ");
    87. System.out.print(" ");
    89. }
    91. // zusätzliche Leerzeilen ausgeben
    92. System.out.println('\n');
    93. }
    95. // testet die Funktionen der Klasse
    96. public static void main(String[] args) {
    97. int[] a = { 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 199 };
    98. BinaereSuche b = new BinaereSuche(a);
    99. int w = b.sucheRekursiv(5);
    100. System.out.println(w);
    101. }
    102. }
    Alles anzeigen

  • fincky87 schrieb:

    fehlen mir die abschaltbaren Methoden

    Nicht Methoden - "Ausgaben"

    Quellcode

    1. public class BinaereSuche
    2. {
    3. public boolean debug = false;
    4. ...
    6. public int binaerRek() {
    7. ...
    8. if(debug) print(); //Ausgabe des Status auf der Konsole
    9. ...
    10. }
    12. public static void main(String[] args) {
    13. int[] a = {3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 199};
    14. BinaereSuche b = new BinaereSuche(a);
    15. b.debug = true;
    16. ...
    17. }
    Alles anzeigen


    fincky87 schrieb:

    Außerdem weiß ich nicht wie das sortieren aussehen soll. Konkret in diesem Beispiel.

    Ich weiß nicht, was ich dir mehr erzählen kann, als die Wikipedia. Die Lösung der Wikipedia ist zwar in Python geschrieben, verwendet aber keine Python Sprachfeatures und sollte somit 1:1 in Java übernommen werden können.

  • D0nut kannst du mir da wirklich nicht helfen...Ich hab echt keinen Plan davon und mein Teampartner kommt nicht mehr online. Ich bräuchte das zu morgen. Ich wäre dir unendlich dankbar. Sollte doch für dich ne Kleinigkeit sein... das ganze hier zu posten. mit der wiki rekursiven suchmethode und der methode.

  • Ne, dein rekursives Sortieren, schreib ich dir wirklich nicht um. Da hättest du dich vorher selbst drum kümmern müssen.

    Hier die Änderung des Debug Flags:

    Quellcode

    1. public class BinaereSuche {
    2. public boolean debug = false;
    4. // Attribute
    5. int[] feld; // speichert das zu durchsuchende Array
    6. int l; // linke Grenze des Suchbereichs
    7. int r; // rechte Grenze des Suchbereichs
    8. int m; // Mitte
    9. int s; // das zu suchende Element
    11. // Konstruktor
    12. public BinaereSuche(int[] feld) {
    13. this.feld = feld;
    14. s = l = r = m = 0;
    15. }
    17. // startet die rekursive Suche
    18. // führt Initialisierungsarbeiten aus
    19. public int sucheRekursiv(int s) {
    21. // Array null oder leer?
    22. if (feld == null || feld.length == 0)
    23. return -1; // Fehlerwert zurückgeben
    25. // Variablen initialisieren
    26. l = 0;
    27. r = feld.length - 1;
    28. this.s = s;
    30. // startet die eigentliche Rekursion
    31. return binaerRek();
    32. }
    34. // prüft rekursiv, ob ein bestimmtes Element im
    35. // Array vorhanden ist und gibt den Index der Position
    36. // des gefundenen Elements zurück
    37. public int binaerRek() {
    39. m = (l + r) / 2; // Berechnung der Mitte
    40. if(debug) print(); //Ausgabe des Status auf der Konsole
    42. // Abbruchbedingung (Rekursionsbasis)
    43. if (l > r)
    44. return -1;
    46. // suche s im linken Teilfeld
    47. if (s < feld[m]) {
    49. r = m - 1;
    50. return binaerRek();
    52. }
    53. // suche s im rechten Teilfeld
    54. else if (s > feld[m]) {
    56. l = m + 1;
    57. return binaerRek();
    59. }
    60. // s wurde an Position m gefunden
    61. else
    62. return m;
    64. }
    66. // gibt den aktuellen Status der Suche auf
    67. // der Konsole aus
    68. public void print() {
    70. // gibt zuerst den Inhalt des Arrays aus
    71. for (int i = 0; i < feld.length; i++)
    72. System.out.print(feld[i] + " ");
    74. System.out.println();
    76. // zeigt die Positionen der einzelnen "Zeiger"
    77. // innerhalb des Arrays an
    78. for (int i = 0; i < feld.length; i++) {
    80. if (i == m)
    81. System.out.print("m");
    82. else if (i == l)
    83. System.out.print("l");
    84. else if (i == r)
    85. System.out.print("r");
    86. else
    87. System.out.print(" ");h
    89. System.out.print(" ");
    91. }
    93. // zusätzliche Leerzeilen ausgeben
    94. System.out.println('\n');
    95. }
    97. // testet die Funktionen der Klasse
    98. public static void main(String[] args) {
    99. int[] a = { 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 199 };
    101. BinaereSuche b = new BinaereSuche(a);
    102. b.debug = true;
    104. int w = b.sucheRekursiv(5);
    106. System.out.println(w);
    108. }
    109. }
    Alles anzeigen

  • Also mit Klassen-Attributen würde ich an dieser Stelle nicht arbeiten. Besser Funktionsparameter.
    Aber ansonsten sieht der Algorithmus zum Suchen korrekt aus.

    Fehlt also der rekursive Selection Sort:

    Quellcode

    1. selectsort(field A, int l, int r) {
    2. if (l < r) then {
    3. q:= max(A, l, l+1, r);
    4. swap(A[q], A[r]);
    5. selectsort(A, l, r-1);
    6. }
    7. }
    9. int max(field A, int q, int l, int r) {
    10. if (l <= r) then {
    11. if (A[l] > A[q]) then {
    12. return max(A, l, l+1, r);
    13. } else {
    14. return max(A, q, l+1, r);
    15. }
    16. } else {
    17. return q;
    18. }
    19. }
    Alles anzeigen

    sortieralgorithmen.de/selectsort/algorithm1.htm