Muss ein Programm schreiben das eine zahl zwischen 1und 8 möglichst
schnell ermittelt!
Habe das nun so gemacht!
Wie könnte ich es einfacher schreiben?
GIBT ES AUCH DIE MÖGLICHKEIT das ich nur mit j oder n antorten kann und
bei allen anderen tasten die Meldung Erorr kommt!
(für diesen Fall wäre mir das mit dem if nicht klar!)
1
#include<iostream>
2
usingnamespacestd;
3
4
intmain()
5
{
6
7
8
cout<<"Bitte merken Sie sich eine Zahl zwischen [1,8]."<<endl;
9
charans;
10
cout<<"Ist die Zahl kleiner als 5? (j|n): ";cin>>ans;
11
if(ans=='j')
12
{
13
cout<<"Ist die Zahl kleiner als 3? (j|n): ";cin>>ans;
14
if(ans=='j')
15
{
16
cout<<"Ist die Zahl kleiner als 2? (j|n): ";cin>>ans;
17
if(ans=='j')cout<<"Ihre Zahl ist 1."<<endl;
18
elsecout<<"Ihre Zahl ist 2."<<endl;
19
}
20
else
21
{
22
cout<<"Ist die Zahl kleiner als 4? (j|n): ";cin>>ans;
23
if(ans=='j')cout<<"Ihre Zahl ist 3."<<endl;
24
elsecout<<"Ihre Zahl ist 4."<<endl;
25
}
26
}
27
else
28
{
29
cout<<"Ist die Zahl kleiner als 7? (j|n): ";cin>>ans;
30
if(ans=='j')
31
{
32
cout<<"Ist die Zahl kleiner als 6? (j|n): ";cin>>ans;
33
if(ans=='j')cout<<"Ihre Zahl ist 5."<<endl;
34
elsecout<<"Ihre Zahl ist 6."<<endl;
35
}
36
else
37
{
38
cout<<"Ist die Zahl kleiner als 8? (j|n): ";cin>>ans;
jumper wrote:
> Muss ein Programm schreiben das eine zahl zwischen 1und 8 möglichst> schnell ermittelt!>> Habe das nun so gemacht!
Von der grundsätzlichen Idee schon mal nicht schlecht.
> Wie könnte ich es einfacher schreiben?
Mit einer Schleife.
Du suchst Zahlen im zwischen 1 und 8. Diesen Grenzwerten geben wir mal
einen Namen, nennen wir das eine Minimum und das andere Maximum (Gemeint
ist jeweils der Bereich in dem die Zahl liegen könnte. 1 ist also das
Minimum des Bereichs und 8 ist das Maximum.
Wann ist die Suche nach der Zahl abgeschlossen ( =
Schleifenabbruchbedingung)?
Na offenbar dann, wenn du den Bereich so eingeschränkt hast, dass nur
noch eine Zahl in Frage kommt. Wann ist das? Klar: Genau dann wenn
Minimum gleich Maximum ist, dann kennst du die Zahl. In allen anderen
Fällen gäbe es ja noch mehrere Wahlmöglichkeiten.
Mal angenommen, du weist die Zahl noch nicht. Also bietest du deinem
Benutzer eine Zahl an und fragst ihn ob seine gedachte Zahl kleiner als
diese Zahl ist. Welche bietest du ihm an?
Na, wenn Minimum gleich 1 ist, und Maximum gleich 8, dann bietest du ihm
zb mal 4 an, weil 4 halbwegs in der Mitte zwischen 1 und 8 liegt. Wie
könnte man das errechnen. zb so ( Minimum + Maximum ) / 2
Sagt der Benutzer ja, was bedeutet das dann für deinen Bereich. Mach dir
das nochmal anhand konkreter Zahlen klar
Das ist dein ursprünglicher Bereich
Min Max
1 2 3 4 5 6 7 8
Du fragst deinen Benutzer jetzt, was mit der 4 ist.
Er sagt, seine Zahl ist kleiner.
Wie schränkt das jetzt den Suchbereich ein.
Offenbar bleibt das Minimum gleich, aber das Maximum wechselt von 8 auf
3 (weil 4 ja schon zu gross ist) (//// kennzeichnet den Bereich in dem
seine Zahl ganz sicher nicht mehr liegen kann)
Min Max
/////////////////
1 2 3 4 5 6 7 8
Da Minimum nicht gleich Maximum ist, gehts in deiner Schleife in die
nächste Runde und du fragst deinen Benutzer wieder ob ( 1 + 3 ) / 2 = 2
kleiner als seine gedachte Zahl ist.
Der Benutzer teilt dir mit: Nein, ist es nicht
Was bedeutet das für deinen Suchbereich. 2 ist nicht kleiner, also kann
1, das bisherige Minimum auch nicht kleiner sein. Du kennst also ein
neues kleinstes Minimum, nämlich 2 und der Bereich der möglichen Werte
schränkt sich ein zu
Min Max
//// /////////////////
1 2 3 4 5 6 7 8
(und jetzt wirds ein wenig trickreich, denn nach welcher Zahl fragst du
jetzt. ( 2 + 3 ) / 2 = 2 Danach hast du aber schon mal gefragt. Auf
der anderen Seite steht fest, dass der Benutzer sich entweder 2 oder 3
gedacht hat, es also nur mehr 2 Möglichkeiten gibt. Am einfachsten ist
es wohl, wenn deine Schleife in so einem Fall abbricht (wenn also der
Suchbereich nur noch 2 mögliche Zahlen umfasst) und du den Benutzer
direkt fragst: War es 2? Oder war es 3?
(Speziell das letzte Problem vereinfacht sich enorm, wenn du deinen
Benutzer nicht einfach nur fragst, ob seine Zahl kleiner ist. Statt
dessen fragst du ihn ob du seine Zahl erraten hast. Und erst wenn er
dies verneint, fragst du ob deine Zahl kleiner als seine ist. In dem
Fall kannst du dann nämlich die Zahl nach der du fragst in allen Fällen
aus dem Suchbereich ausschliessen und der obige Sonderfall entsteht gar
nicht mehr.
Der Benutzer sagt 2 ist es nicht
Nachfrage: kleiner/größer
Benutzer sagt größer
und dein Suchbereich verändert sich zu
Min
Max
////// /////////////////
1 2 3 4 5 6 7 8
und damit muss seine Zahl die 3 gewesen sein.
)
jumper wrote:
> GIBT ES AUCH DIE MÖGLICHKEIT das ich nur mit j oder n antorten kann und> bei allen anderen tasten die Meldung Erorr kommt!> (für diesen Fall wäre mir das mit dem if nicht klar!)
Sicher geht das. Aber in deinem jetzigen Programm ist das sehr mühsam zu
realisieren.
@Karl heinz Buchegger
Danke dir! echt gut erklärt! Werde ich später gleich mal programmieren!
@ Das sieht ja mal sehr gut aus und funktioniert ja auch ! :-)
Nur mir ist noch nicht ganz klar weshalb
die Schleife durchlaufen muß solange (min+1!=max) hätte gedacht das sie
durchlaufen muß solange (min!=max) ist!
Naja muß ich nochmals kurz durchüberlegen!
Danke euch nochmals!
jumper wrote:
> die Schleife durchlaufen muß solange (min+1!=max) hätte gedacht das sie> durchlaufen muß solange (min!=max) ist!
Schau dir nochmal den Anfang des Programms an
1
intmain(void){
2
unsignedintmin=1;
3
unsignedintmax=8+1;
Hmm. Wie war noch mal dein Bereich? 1 bis 8?
Viele Wege führen nach Rom.
Das Prinzip der Einschränkung des Suchbereichs, indem man eine Hälfte
ausschliessen kann, ist immer gleich. Das ist das Prinzip des binären
Suchens. Aber implementieren kann man das auf viele Arten.
Hmm... garkeine rekursive Lösung dabei...
Wär vielleicht fürs Verständnis nicht schlecht, das Programm auch mal
mit rekursiven Funktionsaufrufen zu formulieren.
also in der Form:
main ruft auf "rate_zahl(1,8)", das ruft auf rate_zahl(1-4), dann
rate_zahl(2-3), dann Ausgabe, "Zahl war 2"...
Uiiih, sehr schön.
Geradezu ein Lehrbuch-Beispiel.
Auf zu Lektion Zwei:
Wie erkenne ich eine Endrekursion/Tail recursion, wie löse ich diese
auf, und warum kommt dann die Lösung von Tim dabei raus?
Aber die kommt vermutlich erst nächste Woche dran, wenn die Hausaufgabe
lautet:
"Erweitere dein Programm, so dass es mit beliebigen Zahlenbereichen
arbeitet, und nicht nur von 1 bis 8"
Nachdem gezeigt wurde, wie man die Aufgabe iterativ, und wie man sie
rekursiv löst, kommt nun eine Variante, die auf die explizite Iteration
und Rekursion komplett verzichtet, das Rad nicht neu erfindet und statt
dessen die eigentliche Binärsuche durch eine Funktion aus der Standard-
bibliothek erledigen lässt.
Die Funktion lower_bound, die dafür verwendet wird, erwartet die zu
durchsuchenden Elemente in einer Sequenz, die durch einen Iterator auf
das erste und letzte Element definiert ist. Üblicherweise handelt es
sich bei dieser Sequenz um einen im Speicher liegenden Container (Vektor
oder Liste).
Normalerweise sind die STL-Klassen und -Funktionen sehr einfach in der
Handhabung. Die vorliegende Anwendung stellt aber einen etwas kniffli-
geren Sonderfall dar, weil hier die Sequenz nicht im Hauptspeicher des
Computers, sondern im Gehirn des Benutzers liegt. Da aber alle Zugriffe
auf die Sequenzelemente über Iteratoren erfolgen, kann das Problem
gelöst werden, indem der Zugriffsoperator auf die Elemente so definiert
wird, dass er den Inhalt des "externen Speichers" per Benutzeranfrage
"ausgelesen" wird.
Das Ganze ist für den, der erst ein paar Tage C++ programmiert, sicher
maximal undurchsichtig. Es zeigt aber schön, welche weitreichenden
Abstraktionsmöglichkeiten diese Sprache und die zugehörige Standard-
bibliothek bieten.
Obwohl das Programm den fertigen Algorithmus aus der STL benutzt, ist es
wegen der notwendigen Iteratorklasse deutlich länger als die von Tim T.
gepostete ausprogrammierte Variante, so dass diese im konkreten Fall
natürlich zu bevorzugen ist. Wenn aber die Binärsuche ein wirklich
komplizierter Algorithmus mit ein paar tausend Codezeilen wäre, würde
man sich schon genau überlegen, ob man diesen mit viel Aufwand
neuprogrammiert oder lieber ein paar Verrenkungen wie die gezeigten in
Kauf nimmt, um ihn zur Anwendung passend zu machen.
Und hier ist der C++-Code:
// Ausgabe des Iteratornummer, also der gesuchten Zahl
73
cout<<"Ihre Zahl ist "<<it<<"."<<endl;
74
return0;
75
}
Disclaimer: Ich bin selber kein C++-Guru, deswegen kann ich nicht
garantieren, dass die Binärsuche aus der STL nicht auch auf einfachere
Weise für den vorliegenden Zweck genutzt werden kann. Für Verbesserungs-
vorschläge bin ich deswegen weit offen :)
ach ja: eine kleine Abkürzung wäre, R_CORRECT und R_NOT_TOO_SMALL
zusmmenzufassen zu einem Wert (also z.B. R_CORRECT weg zu lassen und
stattdessen R_NOT_TOO_SMALL zu nehmen).
(Bei der Gelegenheit könnte die enum auch gleich in die Klasse, z.B. als
public.)
Aber immer noch eine schicke Idee!
Klaus Wachtler:
Vielen Dank für die Hinweise.
> Noch etwas C++-mäßiger wäre es vielleicht, zur Ausgabe nicht nach int zu> wandeln, sondern direkt>> std::ostream &operator<<(std::ostream&,const NumIt&)>> zu definieren;
Das hatte ich zuerst auch so. Dann habe ich mir überlegt, dass man
vielleicht irgendwann einmal das Ergebnis der Suche nicht nur ausgeben,
sondern als Integerzahl in weiteren Berechnungen verwenden möchte. Mit
dem Typecast-Operator sind gleich beide Fälle erschlagen, und man
braucht keine Friend-Deklaration für den Zugriff auf das private Element
m_num. Ist aber sicher auch etwas Geschmackssache.
> ach ja: eine kleine Abkürzung wäre, R_CORRECT und R_NOT_TOO_SMALL> zusmmenzufassen zu einem Wert (also z.B. R_CORRECT weg zu lassen und> stattdessen R_NOT_TOO_SMALL zu nehmen).
Stimmt, der R_CORRECT-Wert ist völlig überflüssig und trägt wahrschein-
lich mehr zur Verwirrung als zum Verständnis bei.
> (Bei der Gelegenheit könnte die enum auch gleich in die Klasse, z.B.> als public.)
Ich weiß nur nicht richtig, wie ich dann das Enum als Template-Argument
an die Basisklasse iterator<random_access_iterator_tag, relation_t> von
NumIt übergeben kann. Mit irgendwelchen Vorwärtsdeklarationen habe ich
es nicht hinbekommen. Gibt es da einen Trick?
Hmm. Du bringst mich auf eine Idee.
Mal sehen, wenn ich Zeit habe probier ich das mal aus.
Man kann ja lower_bound auch eine eigene Vergleichsfunktion unterjubeln.
Die Idee ist dann: befülle einen Vector mit den Bereichswerten, und lass
lower_bound nach irgendeinem Wert suchen (welcher ist ziemlich egal).
Die Vergleichsfunktion (Vergleichsobjekt) gibst du lower_bound mit und
darin machst du die Benutzerabfrage.
> Die Idee ist dann: befülle einen Vector mit den Bereichswerten, und> lass lower_bound nach irgendeinem Wert suchen (welcher ist ziemlich> egal).
Ja, das sollte so gehen. Man erspart sich damit die Deklaration einer
neuen Iteratorklasse und muss nur eine einzelne Funktion definieren.
Dafür hat man halt einen ansonsten nutzlosen Vektor im Speicher
herumliegen, was aber bei 8 Elementen noch kein Problem darstellt.
@yalu:
Dein mieser Trick mit dem gedachten Feld und dem Suchschlüssel
im Kopf statt im Speicher geht übrigens auch in C!
Dort gibt es ja bsearch(), die aber nicht nur auf "kleiner"
testet, sondern "kleiner" oder "gleich" oder "groesser" wissen will.
Damit wird es in C auch noch kürzer:
(int)(op2==dummyKey_p?op1:op2)/* einer von beiden ist der
23
* geratene Wert, der andere
24
* ist der Suchschluessel! */
25
);
26
printf("falls zu klein: k eingeben, "
27
"falls gleich: = eingeben, "
28
"falls zu gross: g eingeben!\n"
29
);
30
do
31
{
32
charAntwort=getchar();
33
switch(Antwort)
34
{
35
case'k':
36
/* Angenommen, op1 ist der geratene Wert und op2 der
37
* Schluessel, und der geratene Wert ist zu klein, dann muss
38
* die Vergleichsfunktion einen Wert kleiner als 0 liefern
39
* (egal welchen).
40
* Ist op1 dagegen der Schlüssel, dann andersrum:
41
*/
42
return(op2==dummyKey_p)?-1:+1;
43
break;
44
45
case'=':
46
return0;
47
break;
48
49
case'g':
50
/* Angenommen, op1 ist der geratene Wert und op2 der
51
* Schluessel, und der geratene Wert ist zu gross, dann muss
52
* die Vergleichsfunktion einen Wert groesser als 0 liefern
53
* (egal welchen):
54
*/
55
return(op2==dummyKey_p)?+1:-1;
56
break;
57
58
default:
59
continue;
60
break;
61
}
62
}
63
while("Merkel"!="ehrlich");/* Endlosschleife */
64
}
65
66
intmain(intnargs,char**args)
67
{
68
printf("die gesuchte Zahl ist %d\n",
69
(int)bsearch(dummyKey_p,/* Zeiger auf Suchschluessel */
70
(void*)1,/* ab 1 testen */
71
8,/* 8 "Feldelemente" testen */
72
1,/* Groesse eines Elements */
73
vergleichsfunktion
74
)
75
);
76
77
78
return0;
79
}
Ich denke mir alle Zahlen ab der Adresse NULL, und jedes Byte ab
dort steht für den Zahlenwert seiner Adresse (also verwende ich die
Adressen 1 bis 8, ohne darauf zuzugreifen).
Schönheitsfehler: bei bsearch() könnte es auch vorkommen, dass ein
gesuchtes Element nicht im Feld ist.
Deshalb wird auch nochmal nach dem richtigen Wert gefragt, wenn er
schon der letzte und einzige im restlichen Teilfeld ist.
Mit dem Wissen, dass das "Feld" vollständig ist, könnte man sich
diesen letzten Test sparen; bsearch() hat dieses Wissen aber nicht.
Um das zu beheben, muesste man bsearch() für die kleiner-Bedingung
umfrisieren (was nicht schwer ist, aber dann halt nicht mehr mit
der Std-Lib arbeitet).
Ansonsten: frohes Suchen und dicke Eier!