Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:algorithmen:binaere_suche:binsuchprogramm:start [02.07.2020 10:23] – sbel
+++ faecher:informatik:oberstufe:algorithmen:binaere_suche:binsuchprogramm:start [04.10.2021 17:04] (aktuell) – [Ein Programm zum Zahlenraten] sbel
@@ Zeile 1: / Zeile 1: @@
-====== Ein Programm zur binären Suche ======
+====== Ein Programm zum Zahlenraten ======
-Arbeite mit dem folgenden Programmgerüst:
+Arbeite mit dem folgenden BlueJ Projekt: [[https://codeberg.org/qg-info-unterricht/bluej-binarysearch]]
-<code java App.java>
-/**
- * Erzeugt eine geordnete Zufallsreihe und ermöglicht Abfragen darüber.
- *
- * @author Frank Schiebel
- * @version 1.0
- */
-class BinarySearch
-{
-    private int[] daten;
-    int anzahl;
-    public BinarySearch(int anzahl)
-    {
-        this.anzahl = anzahl;
-        daten = new int[anzahl];
-        int indexvorher = 0;
-        for (int i = 0; i < daten.length; i++)
-        {
-            if ( i>0 ) {
-                indexvorher = i -1;
-            }
-            daten[i] = getZufallszahlOrdered(daten[indexvorher],10*anzahl);
-        }
-    }
-    public int binaereSuche(int zahl) {
+===== Aufgaben: =====
-    }
+==== A1 ====
-    public void anzeigen() {
-        for (int i=0; i< anzahl; i++) {
-             System.out.println( i + " -> " + daten[i] + " ");
-        }
-    }
-    private int getZufallszahlOrdered(int basis, int grenze)
-    {
-        return (int)(2*(grenze-basis)/anzahl*Math.random()+1) + basis;
-    }
-}
-/* App Klasse. Steuerklasse für unser Programm */
-public class App {
-    public static void main(String[] args) {
+  * Beschreibe die Funktion der privaten Methode ''initZahlenreihe''.
-        BinarySearch liste = new BinarySearch(1000);
+  * Implementiere die Methode ''printZahlenreihe''
-        liste.anzeigen();
+==== A2 ====
+Implementiere eine Methode ''binaereSuche'', welche den Index des gesuchten Elements zurückgibt oder ''-1'', wenn der gesuchte Wert nicht gefunden wird. Folge dabei den Tipps und Aufgabenstellungen unten.
-    }
+=== (1) Programmablaufplan ===
-}
-</code>
-===== Aufgaben: =====
+Erstelle ein Flussdiagramm anhand der folgenden Beschreibung.
-==== A1 ====
-Probiere das Programm aus. Beschreibe, was es macht, verändere auch den Parameter ''anzahl'' bei der Erzeugung des BirarySearch Objekts. Welchen Einflüsse hat diese Änderung?
-==== A2 ====
- Implementiere eine Methode ''binaereSuche'', welche den Index des gesuchten Elements zurückgibt oder ''-1'', wenn der gesuchte Wert nicht gefunden wird.
 <code java>
-    // in der main Methode der App Klasse
+  public int binaereSuche(int needle)
-    int gesucht=22;
-    int treffer = liste.binaereSuche(gesucht);
-    System.out.println("Der Wert " + gesucht + " befindet sich im Arrayelement mit dem Index " + treffer);
 </code>
-  * Die Methode ''binaereSuche'' arbeitet auf dem zuvor erzeugten Array und nimmt als Argument die gesuchte Zahl entgegen.
+  * Die Methode ''binaereSuche'' arbeitet auf dem zuvor erzeugten Array und nimmt als Argument die gesuchte Zahl entgegen. Der Rückgabewert ist der Index des Arrayelements, in dem der gesuchte Wert steht - oder -1, wenn dieser nicht gefunden wurde.
-  * Du führst Buch welcher Teil des Arrays zu durchsuchen ist und welcher Teil des Arrays nicht mehr in Frage kommt. wenn deine Methode startet, musst du das gesamte Array betrachten (kleinster Index ''0'', größter Index ''daten.length-1''
+  * Du führst Buch welcher Teil des Arrays zu durchsuchen ist und welcher Teil des Arrays nicht mehr in Frage kommt. wenn deine Methode startet, musst du das gesamte Array betrachten (kleinster Index ''0'', größter Index ''daten.length-1'')
 {{ :faecher:informatik:oberstufe:algorithmen:binaere_suche:binsuchprogramm:step01.png |}}
@@ Zeile 95: / Zeile 35: @@
 </code>
-  * Ist der Wert des Arrayelements **gleich** dem gesuchten Wert, wird der Index mit ''return'' zurückgegeben.
+  * Ist der Wert des Arrayelements **gleich** dem gesuchten Wert, wird der Indexwert mit ''return'' zurückgegeben, denn das Element ist gefunden.
-  * Wenn der gesuchte Wert **kleiner** ist als der Inhalt von ''daten[mitte]'', kann die obere Hälfte des Arrays ausgeschlossen werden, indem man als neue obere Grenze ''mitte'' festlegt.
+  * Wenn der gesuchte Wert **kleiner** ist als der Inhalt von ''daten[mitte]'', kann die obere Hälfte des Arrays ausgeschlossen werden, indem man als neue obere Grenze ''mitte-1'' festlegt.
 <code java>
 if ( gesucht < daten[mitte]) {
-   oben = mitte;
+   oben = mitte-1;
 }
 </code>
@@ Zeile 106: / Zeile 46: @@
-  * Sollte der gesuchte Wert **größer** sein als ''daten[mitte]'' kann die untere Hälfte ausgeschlossen werden, dazu muss der Wert von ''unten'' auf ''mitte'' gesetzt werden.
+  * Sollte der gesuchte Wert **größer** sein als ''daten[mitte]'' kann die untere Hälfte ausgeschlossen werden, dazu muss der Wert von ''unten'' auf ''mitte+1'' gesetzt werden.
 <code java>
 if ( gesucht > daten[mitte]) {
-   unten = mitte;
+   unten = mitte+1;
 }
 </code>
-  * Das ganze muss wiederholt werden, solange der Suchbereich ''oben-unten'' noch mehr als ein Element umfasst.
+  * Das ganze muss wiederholt werden, solange der Suchbereich ''oben-unten'' noch mindestens ein Element umfasst.
+=== (2) Implementation ===
+Implementiere die Methode wie entworfen und teste sie.
+=== Hilfestellungen ===
+++++ Möglicher PAP |
+{{ :faecher:informatik:oberstufe:algorithmen:binaere_suche:binsuchprogramm:flowchart.png |}}
+++++
+++++ Mögliches Methodengerüst |
+<code java>
+public int binarySearch(int needle) {
+        int minindex
+        int maxindex
+        int middleindex
+        int middlevalue
+        while (  ) {
+            if ( ) {
+                return middleindex;
+            }
+            if ( ) {
+               maxindex =
+            } else {
+               minindex =
+            }
+            middleindex =
+            middlevalue =
+        }
+        return -1;
+    }
+</code>
+++++