Natürliche Zahlen nachbauen

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
Karl
User
Beiträge: 252
Registriert: Freitag 29. Juni 2007, 17:49

Hallo.
Aufgrund der Wikipedia-Funktion für die Fakultät einer Zahl n, die etwas unvollständig ist (sie gibt bei negativen Werten stets 1 zurück, was aber gar nicht definiert ist [bzw ich hab schonmal von einer Erweiterung auf reelle und komplexe Zahlen gehört, aber ist ja jetzt auch egal]), hab ich mir gedacht, ich erweitere das durch ein Klasse N (Natürliche Zahl).
Ein if x < 0 wär ja zu einfach gewesen :D

Code: Alles auswählen

class N(int):
    def __init__(self, x):
        self = x
        if self < 0:
            raise "Invalid!"

def fakultaet(x):
    if N(x) > 1:
        return x * fakultaet(x - 1)
    else:
        return 1
Das würde bei negativen Zahlen dann einen Error raisen.
Meine Frage ist jetzt, was ihr von der Klasse N haltet, bzw wie "Profis" das machen würden.
Würd mich einfach mal interessieren.
EyDu
User
Beiträge: 4881
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Karl hat geschrieben:Aufgrund der Wikipedia-Funktion für die Fakultät einer Zahl n, die etwas unvollständig ist
Da steht doch ganz klar:
Für alle natürlichen Zahlen n ist: n! = 1*2*...*n
n kann per Definition nicht negativ werden.

Die Klasse ist vollkommen überflüssig, ob die Zahl negativ ist kannst du gleich in der Funktion testen. Außerdem würde ich die Fakultät in Python nicht unbeding rekursiv berechnen.
Karl
User
Beiträge: 252
Registriert: Freitag 29. Juni 2007, 17:49

EyDu hat geschrieben:
Karl hat geschrieben:Aufgrund der Wikipedia-Funktion für die Fakultät einer Zahl n, die etwas unvollständig ist
Da steht doch ganz klar:
Für alle natürlichen Zahlen n ist: n! = 1*2*...*n
n kann per Definition nicht negativ werden.

Die Klasse ist vollkommen überflüssig, ob die Zahl negativ ist kannst du gleich in der Funktion testen. Außerdem würde ich die Fakultät in Python nicht unbeding rekursiv berechnen.
:roll:
Also darum ging's mir jetzt auch grade gar nicht.
Mir ist klar, dass die Klasse vollkommen überflüssig ist, ich bin aber eben durch dieses Beispiel (die Fakultät) auf die Idee gekommen, eine Klasse für natürliche Zahlen zu machen (egal wie sinnvoll, bzw sinnlos).
Außerdem, wie willst du die Fakultät sonst (exakt) berechnen, wenn nicht rekursiv? Dass es ineffizient ist, ist schon klar, wobei man das ganze auch noch ausbaun könnte, um es effizienter zu machen, aber darum geht's mir auch nicht. Es ist das Wikipedia-Beispiel, das ich 1:1 (naja bis auf das N(x)) übernommen habe.
Es ging mir nämlich eigentlich darum, was ihr von der Klasse N haltet, also würdet ihr das auch so machen? Anders? Warum?
Ich hab zwar keinen praktischen Nutzen davon, aber ich würd's einfach mal gerne wissen ...
audax
User
Beiträge: 830
Registriert: Mittwoch 19. Dezember 2007, 10:38

Karl hat geschrieben: Außerdem, wie willst du die Fakultät sonst (exakt) berechnen, wenn nicht rekursiv?

Code: Alles auswählen

>>> from operator import mul
>>> fak = lambda n: reduce(mul, xrange(1, n+1))
>>> fak(6)
720
Iterativ ;)
Leonidas
Python-Forum Veteran
Beiträge: 16025
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

EyDu hat geschrieben:Die Klasse ist vollkommen überflüssig, ob die Zahl negativ ist kannst du gleich in der Funktion testen. Außerdem würde ich die Fakultät in Python nicht unbeding rekursiv berechnen.
Schaltet man halt dann die Tail Call Optimierung ein ;)
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
BlackJack

@Leonidas: Wenn man dazu den rekursiven Algorithmus aus Wikipedia umschreiben muss, damit man Endrekursion hat und den Dekorator auch anwenden kann, kann man auch gleich eine iterative Variante schreiben. ;-)

@Karl: Dein Quelltext funktioniert nicht, weil `self` ein ganz normaler lokaler Name ist, der beim Aufruf an ein Exemplar der Klasse gebunden ist. Das heisst wenn Du `self` in einer Methode an ein anderes Objekt bindest, hat das, wie überall in Python, keinen Einfluss auf das Objekt, welches vorher an diesen Namen gebunden war.

Und bei `int` kommt noch zusätzlich hinzu, dass es sich um einen Typ handelt, der nicht verändert werden kann. Wenn `__init__()` aufgerufen wird, dann existiert das Exemplar bereits, es wird ja als erstes Argument an die Methode übergeben, und man kann den Wert nicht mehr verändern. In solchen Fällen muss man `__new__()` implementieren.

Aber letztendlich ist eine Prüfung des Arguments in der Fakultäts-Funktion und auslösen eines `ValueError` falls sie <0 ist, die einfachere Lösung.
Karl
User
Beiträge: 252
Registriert: Freitag 29. Juni 2007, 17:49

audax hat geschrieben:

Code: Alles auswählen

>>> from operator import mul
>>> fak = lambda n: reduce(mul, xrange(1, n+1))
>>> fak(6)
720
Iterativ ;)
Ach ja, gut ... Stimmt ;)
Aber wenn man die Rekursion etwas optimiert (keine Ahnung, ob es dieses Tail Call Optimierungs-Teil von Leonidas ist), kommt's ja im Prinzip auf das Selbe hinaus. Aber okay, diese 2 Zeilen sind wohl deutlich knapper :p
BlackJack hat geschrieben: @Karl: Dein Quelltext funktioniert nicht, weil `self` ein ganz normaler lokaler Name ist, der beim Aufruf an ein Exemplar der Klasse gebunden ist. Das heisst wenn Du `self` in einer Methode an ein anderes Objekt bindest, hat das, wie überall in Python, keinen Einfluss auf das Objekt, welches vorher an diesen Namen gebunden war.

Und bei `int` kommt noch zusätzlich hinzu, dass es sich um einen Typ handelt, der nicht verändert werden kann. Wenn `__init__()` aufgerufen wird, dann existiert das Exemplar bereits, es wird ja als erstes Argument an die Methode übergeben, und man kann den Wert nicht mehr verändern. In solchen Fällen muss man `__new__()` implementieren.

Aber letztendlich ist eine Prüfung des Arguments in der Fakultäts-Funktion und auslösen eines `ValueError` falls sie <0 ist, die einfachere Lösung.
Dass die Prüfung von <0 einfacher ist, war mir schon klar.
Hm ich dachte das mit dem `self` funktioniert vielleicht, weil es ja bei `list` auch so geht ;p
Aber warum sind eigentlich immer alle so OffTopic?
Es ging ja nicht um die Rekursion, ich hab einfach nur das Wikipedia-Beispiel gepostet. Mir ging's wie schonmal erwähnt nur um die Klasse.
Ich wollte einfach nur mal wissen, wie man in Python denn einen Datentyp für Natürliche Zahlen implementieren würde (ob's jemals gebraucht wird, ka).
`int` ist ja praktisch schon Z, man muss das ja eigentlich nur auf >=0 beschränken?
Aber so ganz haut das mit dem Erben von `int` auch nicht hin, oder? Weil man dann ja die ganzen Methoden wie __add__() usw alle noch auf >= 0 im Ergebnis beschränken müsste oO Jedenfalls wenn der Rückgabewert auch eine Natürliche Zahl werden soll
BlackJack

Was meinst Du mit "weil es bei `list` auch so geht"? Auch dort hat das binden von `self` innerhalb der Methoden keinen Einfluss auf die Liste, die als erstes Argument übergeben wird.

Entweder musst Du mit Delegation arbeiten und den Integer-Wert als Attribut der Exemplare implementieren, dann geht `__init__()`, oder Du musst eben `__new__()` als Konstruktor implementieren und dort die Überprüfung machen.

Die Ergebnisse von Rechenoperationen würde ich nicht auf ganze Zahlen beschränken.
Karl
User
Beiträge: 252
Registriert: Freitag 29. Juni 2007, 17:49

BlackJack hat geschrieben:Was meinst Du mit "weil es bei `list` auch so geht"? Auch dort hat das binden von `self` innerhalb der Methoden keinen Einfluss auf die Liste, die als erstes Argument übergeben wird.
Aber dort kann man mit `self` auf die Elemente zugreifen, also `self[x]`, weswegen ich angenommen hatte, dass self = x sinn machen _könnte_ ;p
BlackJack hat geschrieben:Entweder musst Du mit Delegation arbeiten und den Integer-Wert als Attribut der Exemplare implementieren, dann geht `__init__()`, oder Du musst eben `__new__()` als Konstruktor implementieren und dort die Überprüfung machen.
Okay, ich werd mir das mal angucken.
BlackJack hat geschrieben:Die Ergebnisse von Rechenoperationen würde ich nicht auf ganze Zahlen beschränken.
Darum hab ich ja auch das hinzugefügt
Jedenfalls wenn der Rückgabewert auch eine Natürliche Zahl werden soll
Aber eigentlich hast du recht :p
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Karl, deine Lösung finde ich nicht gut, denn du erzeugst ein N-Objekt einzig, um den Seiteneffekt auszunutzen, dass dein Konstruktor eine Exception wirft, wenn das int-Objekt negativ ist. Hier ist ein "if n < 0: raise ..." die bessere Lösung (meinetwegen auch ein assert).

Wenn schon eigene Zahlen, dann bitte auch richtig:

Code: Alles auswählen

class Nat(object):
  def __init__(self, pred): self.pred = pred
  def __nonzero__(self): return True
  def __add__(self, other): return self.succ if other else self
  def __sub__(self, other): return self.pred if other else self
  def __mul__(self, other): return self + self * (other -1) if other else one
  @property
  def succ(self): return Nat(self)
 
class Zero(Nat):
  def __init__(self): super(Zero, self).__init__(self)
  def __nonzero__(self): return False

zero = Zero()
one = zero.succ
two = one + one
three = one + two

def fac(n): return n * fac(n - one) if n else one

print fac(two * three)
PS: (End)rekursion gewinnt an Eleganz immer gegen for- oder while-Schleifen, besonders, wenn diese eine Variable ändern.

Stefan
Antworten