Hallöchen,
ich denke mal für euch ist das total easy...für mich naja...ich habe Informatik im Grundstudium für IM und brauche Hilfe bei einer Aufgabe (evtl auch bei mehreren, daher hab ich mich mal angemeldet):
Die folgende Funktion berechnet den Zweierlogarithmus von n nach der Regel:
log2(n)=log2(2*n/2)=log2(2)+log2(n/2)= 1+ log2(n/2)
(die 2 direkt nach dem log sollte tiefergestellt sein..sprich die Basis 2)
Ich versteh die Formel absolut, weiß allgemein auch was der Trivialfall ist...hier mal meine lösung (Einrückung NICHT BERÜCKSICHTIGT, aber vollkommen LOGISCH!!!)
def log(n):
if n==2:
return 1
else:
return 1 + log(n/2)
jetz die Frage, was ist daran falsch? wo ist der haken? man muss berücksichtigen dass wir hier mit ganzzahlen rechnen, das heißt man kann nur Ganzzahlen eingeben und als Ergebnis kommen auch nur Ganzzahlen raus!, Also müsste bei log(3) ja 2 rauskommen....kommt aber nicht....... wo hab ich den Fehler???
Bitte helft mir ich will das endlich wissen..rechne schon ne Weile rum....
Funktion - 2er Logarithmus berechnen
- cofi
- Python-Forum Veteran
- Beiträge: 4432
- Registriert: Sonntag 30. März 2008, 04:16
- Wohnort: RGFybXN0YWR0
1. Es gibt [ python][ /python] Code Tags, damit geht auch die Einrückung nicht baden.
2. DasIch meint das hier:
In dem Fall rufst du in der naechsten Iteration auf .. und dann immer wieder .. bis zur maximalen Rekursionstiefe. Sprich: Du brauchst mehr Basisfaelle.
2. DasIch meint das hier:
Code: Alles auswählen
In [2]: 3 / 2
Out[2]: 1
Code: Alles auswählen
1 + log(0)
Michael Markert ❖ PEP 8 Übersetzung ❖ Tutorial Übersetzung (3.x) ⇒ Online-Version (Python 3.3) ❖ Deutscher Python-Insider ❖ Projekte
cofi hat geschrieben:1. Es gibt [ python][ /python] Code Tags, damit geht auch die Einrückung nicht baden.
2. DasIch meint das hier:In dem Fall rufst du in der naechsten IterationCode: Alles auswählen
In [2]: 3 / 2 Out[2]: 1
auf .. und dann immer wieder .. bis zur maximalen Rekursionstiefe. Sprich: Du brauchst mehr Basisfaelle.Code: Alles auswählen
1 + log(0)
ok, also ich versteh schon dass ich dann sozusagen ja gleich "am Ende" angelangt bin...jedoch, wie kann ich das ändern? was für zusätzliche Basisfälle brauch ich? ich meine, wenn ich n==0 setze, das ist der trivialfall...dann kommt ja im endeffekt 1 raus....wenn ich aber z.B. log(3) eingebe, dann müsste doch 3/2=1 + 1 = 2 rauskommen oder?
liege ich falsch? wieso funktioniert es nicht.....?
@linnsche: Schreib es Dir doch einfach mal auf was bei ``log(3)`` jeweils für den Aufruf ersetzt wird. Oder mal anders gefragt was soll ``log(0)`` ergeben und was ergibt das bei Dir?
ok, log(0) ergibt immer eins...weil ja a^0 immer 1 ergibt........und das hab ich ja jetz geschrieben:
if n==0:
return 1
stimmt das nicht...??
ich hab jetzt den test gemacht..normal müsste für log(100) 7 rauskommen (also eigentlich 6,6....)....be mir kommt 8 raus....jetz frag ich mich, wieso? ach ich mag das mit log nicht....garnicht
if n==0:
return 1
stimmt das nicht...??
ich hab jetzt den test gemacht..normal müsste für log(100) 7 rauskommen (also eigentlich 6,6....)....be mir kommt 8 raus....jetz frag ich mich, wieso? ach ich mag das mit log nicht....garnicht
- cofi
- Python-Forum Veteran
- Beiträge: 4432
- Registriert: Sonntag 30. März 2008, 04:16
- Wohnort: RGFybXN0YWR0
Aem log_x(x^y) = y. Also log_x(a^0) = 0, nicht eins. Andersherum: log(1) = 0, fuer alle Basen.
log(0) dagegen ist ziemlich undefiniert (Mit welchem Exponenten bekommt man denn eine 0?!)
log(0) dagegen ist ziemlich undefiniert (Mit welchem Exponenten bekommt man denn eine 0?!)
Michael Markert ❖ PEP 8 Übersetzung ❖ Tutorial Übersetzung (3.x) ⇒ Online-Version (Python 3.3) ❖ Deutscher Python-Insider ❖ Projekte
@linnsche: Schreib Dir doch mal die Rechnung hin wodurch der `log()`-Aufruf in jedem Schritt ersetzt wird. (Und es gibt hier Tags für Code im allgemeinen und Python im besonderen.)
ja aber es gibt doch 1 wenn ich die oben genannte REchnung ausführe? sprich:BlackJack hat geschrieben:@linnsche: Schreib Dir doch mal die Rechnung hin wodurch der `log()`-Aufruf in jedem Schritt ersetzt wird. (Und es gibt hier Tags für Code im allgemeinen und Python im besonderen.)
log2(0)= 1+log(0/2) und das gäb doch 1.....
ich versteh nicht genau was du meinst, BlackJack!
Ich steh wohl mega auf dem Schlauch und raub euch jeglichen Nerv, aber ich weiß echt nicht wie ich vorgehen soll.......wo genau find ich die Tags? vorallem für Python??? und wie soll ich die Rechnung "aufschreiben"?????
die Rechnung steht doch schon oben. Oder was meinst du???
Gehen wir mal von einer ursprünglichen Definition aus:
``log(3)`` ist equivalent zu ``1 + log(3 / 2)`` bzw. ``1 + log(1)``. Dies lässt sich weiter auflösen zu ``1 + (1 + log(1 / 2))`` und da ``1 / 2 == 1`` haben wir auch hier einen Aufruf ``log(1)``. Jetzt könnten wir dies auflösen aber letztendlich ändert sich nichts mehr und die Rekursion läuft weiter bis der Stack überläuft oder das Interpreter Limit erreicht ist was zu einem RuntimeError führt.
Wir stellen also fest dass die Abbruchbedingung ``n == 2`` nicht ausreichend (und möglicherweise unnötig) oder falsch ist. Da die Funktion die Eigenschaft ``log(2 ** 2) == 1`` erfüllt trifft ersteres zu.
Ich könnte jetzt noch eine Haskell Lösung posten aber dann wird es wirklich zu einfach.
Code: Alles auswählen
def log(n):
if n == 2:
return 1
else:
return 1 + log(n / 2)
Wir stellen also fest dass die Abbruchbedingung ``n == 2`` nicht ausreichend (und möglicherweise unnötig) oder falsch ist. Da die Funktion die Eigenschaft ``log(2 ** 2) == 1`` erfüllt trifft ersteres zu.
Ich könnte jetzt noch eine Haskell Lösung posten aber dann wird es wirklich zu einfach.
ok, also daher kommt auch immer die runtime-error-meldung!
ja aber wenn ich das Ganze abänder auf n==0: return 1, dann stimmts doch oder? Denn wenn ich n==0 setze, also log(0), dann return ich 1......und sonst zählt es ja runter...also wenn ich log(3) mach dann ist es doch 1+log(3/2), das dann 1+(1+log(2/2) etc...oder?
stimmt es dann nicht?
ja aber wenn ich das Ganze abänder auf n==0: return 1, dann stimmts doch oder? Denn wenn ich n==0 setze, also log(0), dann return ich 1......und sonst zählt es ja runter...also wenn ich log(3) mach dann ist es doch 1+log(3/2), das dann 1+(1+log(2/2) etc...oder?
stimmt es dann nicht?
- cofi
- Python-Forum Veteran
- Beiträge: 4432
- Registriert: Sonntag 30. März 2008, 04:16
- Wohnort: RGFybXN0YWR0
Schau dir nochmal meinen Post an. Bei log(0) 1 zurueckzugeben ist aber in jedem Fall falsch.
Michael Markert ❖ PEP 8 Übersetzung ❖ Tutorial Übersetzung (3.x) ⇒ Online-Version (Python 3.3) ❖ Deutscher Python-Insider ❖ Projekte
ach mist...für n==1: return 0 oder??????? genau anders rum......mann..wieso bin ich sowas von DOOF in python...??? ich versteh zwar schon vieles viel ebsser als im letzten semester (bin durchgerasselt) aber bei so mathematischen dingen (obwohl ich mathe liebe und kann.......) stell ich mich immer total doof an.... :Kcofi hat geschrieben:Schau dir nochmal meinen Post an. Bei log(0) 1 zurueckzugeben ist aber in jedem Fall falsch.
also heißt es nun:
Code: Alles auswählen
def log(n):
if n==1:
return 0
else:
return 1+log(n/2)
- cofi
- Python-Forum Veteran
- Beiträge: 4432
- Registriert: Sonntag 30. März 2008, 04:16
- Wohnort: RGFybXN0YWR0
Das ist schonmal deutlich besser. Sinnvollerweise solltest du noch den Fall < 1 abfangen (und eine Exception werfen), um Endlosrekursionen zu vermeiden
Michael Markert ❖ PEP 8 Übersetzung ❖ Tutorial Übersetzung (3.x) ⇒ Online-Version (Python 3.3) ❖ Deutscher Python-Insider ❖ Projekte
stimmt das hab ich mir vorhin noch überlegt, aber dann dachte ich, es sei doch sinnvoller mit n==1....aber hey,
DANKE EUCH für die hilfestellung! echt, ich bin so dankbar dass ich es jetz doch noch rausgefunden hab
DANKE!
DANKE EUCH für die hilfestellung! echt, ich bin so dankbar dass ich es jetz doch noch rausgefunden hab
DANKE!
So sieht übrigens die Haskell Lösung mit Test aus:
Code: Alles auswählen
import Test.QuickCheck (Property, (==>), quickCheck)
log2 :: Fractional a => a -> Integer
log2 1 = 0
log2 n = 1 + log2 (n / 2)
testLog2 :: Integer -> Property
testLog2 n = n > 0 ==> log2 (2 ^ n) == n
main :: IO ()
main = quickCheck testLog2
Ich konnte nicht widerstehen etwas RPL in meinen HP-Taschenrechner zu hacken:
Das Programm muss unter dem Namen ``L2`` gespeichert werden, damit das mit der Rekursion klappt.
Code: Alles auswählen
«
CASE DUP 1 <
THEN 772 DOERR END
DUP 1 ==
THEN DROP 0
END 2 / FLOOR L2 1 +
END
»
Bin nicht sicher, ob Du mit int (oder nicht doch lieber mit float) rechnen willst.linnsche hat geschrieben:also heißt es nun:
Code: Alles auswählen
def log(n): if n==1: return 0 else: return 1+log(n/2)
Für Vielfache von 2 (2, 4, 8, 16) scheint das ja so zu klappen. Für die Werte dazwischen (z.B. 7) eher weniger. Das Abfangen der Endlosrekursion in der Weise, daß das Ergebnis bei den Werten dazwischen dann stimmt, sehe ich auch noch nicht.