Zahlenraten

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
knuffi123
User
Beiträge: 12
Registriert: Mittwoch 7. November 2007, 19:26

Montag 24. November 2008, 23:51

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
DasIch
User
Beiträge: 2462
Registriert: Montag 19. Mai 2008, 04:21
Wohnort: Berlin

Dienstag 25. November 2008, 00:00

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.
lunar

Dienstag 25. November 2008, 00:23

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.
Qubit
User
Beiträge: 75
Registriert: Dienstag 7. Oktober 2008, 09:07

Dienstag 25. November 2008, 00:34

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

Code: Alles auswählen

print "m=",m
ein und überleg dann noch mal, ob "m/2" so richtig ist ;-)
Benutzeravatar
veers
User
Beiträge: 1219
Registriert: Mittwoch 28. Februar 2007, 20:01
Wohnort: Zürich (CH)
Kontaktdaten:

Dienstag 25. November 2008, 08:48

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
[url=http://29a.ch/]My Website - 29a.ch[/url]
"If privacy is outlawed, only outlaws will have privacy." - Phil Zimmermann
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Dienstag 25. November 2008, 09:30

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.
Antworten