Seite 1 von 1
Zahlenraten
Verfasst: Montag 24. November 2008, 23:51
von knuffi123
Hallo,
ich mache gerade einen "Zahlenraten" Algorithmus.
Allerdings weiss ich nicht mehr weiter.
Es soll sich einer natürliche Zahl x annähern in einem bekanten Intervall.
Folgendes habe ich gemacht, es führt aber logischerweise zu einem infinite loop:
Code: Alles auswählen
n = 100
m = (n/2)
x = 20
def Raten(m):
if x > m:
return Raten(m+m/2)
elif x < m:
return Raten(m-m/2)
elif x == m:
return "Die gesuchte Zahl x ist: m"
Kann mir jemand weiterhelfen?
Danke
Verfasst: Dienstag 25. November 2008, 00:00
von DasIch
Du verwendest Rekursion, keine gute Idee in Python da es im Gegensatz zu z.B. Scheme keine tail-call optimization gibt.
Verwende besser eine while Schleife und definiere n und x nicht global sondern lokal.
Verfasst: Dienstag 25. November 2008, 00:23
von lunar
DasIch hat geschrieben:Du verwendest Rekursion, keine gute Idee in Python da es im Gegensatz zu z.B. Scheme keine tail-call optimization gibt.
Die binäre Suche hat logarithmische Komplexität, bei der Verdoppelung des Intervalls wächst die Rekursionstiefe nur um eine Ebene. Man muss also schon sehr große Intervalle angeben, um das Rekursionslimit zu überschreiten.
Außerdem mag die Rekursion Bestandteil der Aufgabestellung sein, wenn es sich – wie ich vermute – um eine Hausaufgabe handelt.
Re: Zahlenraten
Verfasst: Dienstag 25. November 2008, 00:34
von Qubit
knuffi123 hat geschrieben:
if x > m:
return Raten(m+m/2)
elif x < m:
return Raten(m-m/2)
Kann mir jemand weiterhelfen?
Danke
Füg mal über dem "if" ein
ein und überleg dann noch mal, ob "m/2" so richtig ist
Verfasst: Dienstag 25. November 2008, 08:48
von veers
Ich mache gerade einen generischen Algorithmus um Hausaufgaben zu lösen...
Zu dem Code:
Also bei mir passiert da nichts.
Das elif x == m: kannst du dir zumindest solange du mit integer arbeitest sparen.
m-m/2 liest sich auch etwas komisch.
Aber zu deinem eigentlichen Problem gib dem Intervall einen Start und eine Länge, das macht das ganze einfacher.
DasIch, damit du da Probleme mit der Rekursion bekommst brauchst du aber schon ein grosses Intervall.
- Jonas
Verfasst: Dienstag 25. November 2008, 09:30
von sma
Kann man überhaupt Zahlen in einem offenen Intervall raten?
Mit einer Rekursionsstiefe von 1000 (sys.getrecursionlimit()) kommt man auf maximal
1071508607186267320948425049060001810561404811705533607443750388370351051124936
1224931983788156958581275946729175531468251871452856923140435984577574698574803
9345677748242309854210746050623711418779541821530464749835819412673987675591655
43946077062914571196477686542167660429831652624386837205668069376L :)
Diese Zahl (2 ** sys.getrecursionlimit()) könnte also die obere Grenze sein und 0 bietet sich als untere Grenze an. Dann fängt man in der Mitte an und variiert um die halbe Differenz von m und der passenden Intervallgrenze. Dabei ist darauf zu achten, dass man sich um mindestens 1 bewegt.
Der jetzige Algorithmus endet nicht, weil er 20 nicht trifft. Seine Periode ist 14, 21, 11, 16, 24, 12, 18, 27.