Hallo,
ich bin neu hier und habe ein Problem mit einer Aufgabe und hoffe, dass mir vielleicht einer helfen kann. Ich stell die Aufgabe einfach mal hier rein und danke für jede Antwort.
Suchen und Sortieren gehören zu häufigen Aufgaben von Programmen, die mit großen Datenmengen
arbeiten. Besonders leicht tut man sich, wenn man in bereits der Größe nach
sortierten Daten sucht. Dann kann man das Verfahren der binären Suche verwenden, dass
sehr effizient ist. Das Verfahren lässt sich am besten am Beispiel erklären:
Daten: -4 -2 0 3 6 8 10 15 45 99
Gesucht wird: 15
• Betrachte das Array der Daten und vergleiche die gesuchte Zahl (hier 15) mit
dem Element an der mittleren Indexposition (hier 6, oder 8).
• Ist die gesuchte Zahl kleiner, wiederhole die Suche in der linken Hälfte der
Daten.
• Ist das gesuchte Element größer, wiederhole die Suche in der rechten Hälfte
der Daten. (her 8 10 15 45 99).
• Ist das gesuchte Element gleich, beende die Suche.
Das Suchintervall in den Daten wird also Schritt für Schritt immer kleiner.
Schreiben Sie eine Funktion, die in einem Feld der Größe nach sortierter ganzer Zahlen eine
Zahl (beide vom Datentyp long int). sucht. Die Deklaration der Funktion ist:
int bin_suche(long int x, long int v[], int n);
Dabei ist:
• x die gesuchte Zahl
• v das Feld in dem gesucht wird
• n die Zahl der Elemente des Feldes v
Das Resultat der Funktion ist der Index der gesuchten Zahl im Feld oder -1 falls die gesuchte
Zahl nicht im Feld enthalten ist
Zum Testen der Funktion stehen Testdaten in der Datei a2.dat zur Verfügung. Es handelt
sich dabei um 2000 ganze Zahlen, die jeweils in einer Zeile stehen.
Schreiben Sie sich ein Hauptprogramm, dass
• jede der 2000 ganzen Zahlen als String einliest, per str_to_long() umwandelt
und dann in einem Feld ablegt.
• einen Suchwert vom Benutzer eingeben lässt
• diesen Suchwert mit bin_suche() in dem Feld sucht
• das Resultat der Suche in einer geeigneten Ausgabe bekannt gibt.
DANKE IM VORRAUS!
ich bin neu hier und habe ein Problem mit einer Aufgabe und hoffe, dass mir vielleicht einer helfen kann. Ich stell die Aufgabe einfach mal hier rein und danke für jede Antwort.
Suchen und Sortieren gehören zu häufigen Aufgaben von Programmen, die mit großen Datenmengen
arbeiten. Besonders leicht tut man sich, wenn man in bereits der Größe nach
sortierten Daten sucht. Dann kann man das Verfahren der binären Suche verwenden, dass
sehr effizient ist. Das Verfahren lässt sich am besten am Beispiel erklären:
Daten: -4 -2 0 3 6 8 10 15 45 99
Gesucht wird: 15
• Betrachte das Array der Daten und vergleiche die gesuchte Zahl (hier 15) mit
dem Element an der mittleren Indexposition (hier 6, oder 8).
• Ist die gesuchte Zahl kleiner, wiederhole die Suche in der linken Hälfte der
Daten.
• Ist das gesuchte Element größer, wiederhole die Suche in der rechten Hälfte
der Daten. (her 8 10 15 45 99).
• Ist das gesuchte Element gleich, beende die Suche.
Das Suchintervall in den Daten wird also Schritt für Schritt immer kleiner.
Schreiben Sie eine Funktion, die in einem Feld der Größe nach sortierter ganzer Zahlen eine
Zahl (beide vom Datentyp long int). sucht. Die Deklaration der Funktion ist:
int bin_suche(long int x, long int v[], int n);
Dabei ist:
• x die gesuchte Zahl
• v das Feld in dem gesucht wird
• n die Zahl der Elemente des Feldes v
Das Resultat der Funktion ist der Index der gesuchten Zahl im Feld oder -1 falls die gesuchte
Zahl nicht im Feld enthalten ist
Zum Testen der Funktion stehen Testdaten in der Datei a2.dat zur Verfügung. Es handelt
sich dabei um 2000 ganze Zahlen, die jeweils in einer Zeile stehen.
Schreiben Sie sich ein Hauptprogramm, dass
• jede der 2000 ganzen Zahlen als String einliest, per str_to_long() umwandelt
und dann in einem Feld ablegt.
• einen Suchwert vom Benutzer eingeben lässt
• diesen Suchwert mit bin_suche() in dem Feld sucht
• das Resultat der Suche in einer geeigneten Ausgabe bekannt gibt.
DANKE IM VORRAUS!
