ggT

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.
BlackMamba
User
Beiträge: 77
Registriert: Samstag 24. März 2007, 23:22
Wohnort: Germany,NRW,

Mittwoch 6. Februar 2008, 23:21

Hallo, in der Uni mussten wir die Programiersprache Haskell lernen....sehr blöde Sache....
Naja, ich habe mal probiert etwas in Python zu übertragen und zwar den ggt Algorithmus. Leider gibt es immer eine ErrorMeldung und da ich leider noch kein Vernünftiges Programm habe, das mit die Fehler in meinem Quellcode anzeigt (kennt jemand ein gutes was auch unter Vista läuft?) bzw, zumindest die Zeile anzeigt, stelle ich das hier mal rein.
Danke schon im Vorraus für die Hilfe.

Code: Alles auswählen

def ggT(a,b):
    if a > b :
        if b == 0 :
            print a
        else :
            ggT b ( a % b)
    else :
        ggT(b,a)
    return [a]
    return [b]



print ggT(1234567891, 123456789)        
Gnushi
User
Beiträge: 77
Registriert: Dienstag 12. Dezember 2006, 09:49

Mittwoch 6. Februar 2008, 23:48

N'Abend!
BlackMamba hat geschrieben:Leider gibt es immer eine ErrorMeldung und da ich leider noch kein Vernünftiges Programm habe, das mit die Fehler in meinem Quellcode anzeigt (kennt jemand ein gutes was auch unter Vista läuft?) bzw, zumindest die Zeile anzeigt, stelle ich das hier mal rein.
Das von dir geschriebene Programm ist nicht in Python geschrieben. Bitte lies mal irgendein Tutorial, wo Schlüsselworte wie "return" erklärt werden und man auf den Aufbau von Funktionen eingeht.

Fehlermeldungen siehst du, wenn du
python programm.py
eintippst, am besten im DOS-Fenster.

GnuShi
noise
User
Beiträge: 62
Registriert: Donnerstag 7. Februar 2008, 00:15

Donnerstag 7. Februar 2008, 00:52

BlackMamba hat geschrieben:Leider gibt es immer eine ErrorMeldung und da ich leider noch kein Vernünftiges Programm habe, das mit die Fehler in meinem Quellcode anzeigt
Huch? Was genau ist an dem traceback unverständlich?

Code: Alles auswählen

    ggT b ( a % b)
        ^
SyntaxError: invalid syntax
BlackMamba
User
Beiträge: 77
Registriert: Samstag 24. März 2007, 23:22
Wohnort: Germany,NRW,

Donnerstag 7. Februar 2008, 09:39

hab meinen Fehler gefunden.

Danke für die Hilfe!
Zuletzt geändert von BlackMamba am Donnerstag 7. Februar 2008, 15:20, insgesamt 1-mal geändert.
BlackJack

Donnerstag 7. Februar 2008, 11:14

Einzahl? Da sind wohl mehrere drin. Allerdings ist eine rekursive Lösung nicht so günstig, wenn es eine einfache Iterative gibt. In Haskell kann man so etwas nur als Rekursion ausdrücken, in Python sollte man Rekursion auf Probleme beschränken, die Rekursion wirklich benötigen weil ein Funktionsaufruf relativ teuer ist, es das Rekursionslimit gibt, und der Compiler keine Endrekursion erkennt und optimiert.

Code: Alles auswählen

def ggT(a, b):
    if a < b:
        a, b = b, a
    while b:
        a, b = b, a % b
    return a
noise
User
Beiträge: 62
Registriert: Donnerstag 7. Februar 2008, 00:15

Donnerstag 7. Februar 2008, 14:54

BlackJack hat geschrieben:in Python sollte man Rekursion auf Probleme beschränken, die Rekursion wirklich benötigen weil ein Funktionsaufruf relativ teuer ist, es das Rekursionslimit gibt, und der Compiler keine Endrekursion erkennt und optimiert.
Ja, das finde ich auch. Vor allem sind viele "offensichtlich" rekursive Algorithmen auch iterative ausdrückbar, wie zum beispiel das flatten von listen.

Naja, tail call optimization würde Pyhon gut stehen, aber das für und gegen bzw. die Machbarkeit war ja schon Gegenstand diverser Diskurse auf einigen mailing lists.

EDIT: Der Vollständigkeitshalber: dafür gibt es ein Dekorator der aber langsam ist. Zumindest hat man aber dadurch nicht das Problem mit dem Rekursionslimit. Natürlich nur für echte rekursive Strukturen nutzen, da echt langsam! ;)

http://aspn.activestate.com/ASPN/Cookbo ... ipe/474088
BlackMamba
User
Beiträge: 77
Registriert: Samstag 24. März 2007, 23:22
Wohnort: Germany,NRW,

Donnerstag 7. Februar 2008, 15:20

jetzt funktionierts....war ein bischen mit der Syntax durcheinander gekommen.

Code: Alles auswählen

def Euclid (a,b):
    if (b == 0) :
        return a
    else :
        return Euclid (b, (a % b))




print Euclid (123456789,12345678)    
Zuletzt geändert von BlackMamba am Donnerstag 7. Februar 2008, 15:21, insgesamt 1-mal geändert.
BlackMamba
User
Beiträge: 77
Registriert: Samstag 24. März 2007, 23:22
Wohnort: Germany,NRW,

Donnerstag 7. Februar 2008, 15:21

ich habs aber wieder rekursiv gelöst.

Danke nochmal für eure Tipps.
BlackMamba
User
Beiträge: 77
Registriert: Samstag 24. März 2007, 23:22
Wohnort: Germany,NRW,

Donnerstag 7. Februar 2008, 15:48

@ BlackJack : Da hast du recht, in Haskell weiß man vor lauter Rekursionen nicht wo man hin soll...
BlackJack

Donnerstag 7. Februar 2008, 16:17

Na, immer einen rekursiven Abstieg weiter runter, bis man den Rekursionsanker trifft und dann wieder rauf. Ist doch ganz einfach. :-D

Oder halt möglichst viel mit den Funktionen höherer Ordnung ausdrücken.
noise
User
Beiträge: 62
Registriert: Donnerstag 7. Februar 2008, 00:15

Donnerstag 7. Februar 2008, 16:37

BlackJack hat geschrieben:Na, immer einen rekursiven Abstieg weiter runter, bis man den Rekursionsanker trifft und dann wieder rauf. Ist doch ganz einfach. :-D
:lol: ;)
BlackJack

Donnerstag 7. Februar 2008, 16:43

Wobei beim ggT von der Klarheit her die explizit rekursive Variante gewinnt:

Code: Alles auswählen

ggt a 0 = a
ggt a b = ggt b (a `mod` b)

ggt' a b = let f (x, y) = (y, x `mod` y) in
    fst . head . dropWhile (\z -> snd z /= 0) $ iterate f (a, b)
Wobei die kürzeste Variante wohl noch das hier sein dürfte:

Code: Alles auswählen

ggt = gcd
:-)
BlackMamba
User
Beiträge: 77
Registriert: Samstag 24. März 2007, 23:22
Wohnort: Germany,NRW,

Freitag 8. Februar 2008, 09:00

@ BlackJack:
>> fst . head . dropWhile (\z -> snd z /= 0) $ iterate f (a, b)

Ist das so eine Art Listenbeschreibung, wie man sie auch in Haskell verwendet?
Kann man dann z.B. die folgende Permutationsfunktion auch in Python generieren? Um z.B. den Algorithmus für den TSP zu programieren?

Code: Alles auswählen

permut :: [Stadt] -> [[Stadt]]
permut [] = [[]]
permut (xs) = [ y:ys | y <- xs , ys <- permut (remove y xs) ]
-- Permutation
BlackJack

Freitag 8. Februar 2008, 12:25

Hallo! Das ist alles *Haskell* in meinem letzten Beitrag. Ich denke Du kennst die Sprache!? `ggt'` verwendet nur Funktionen aus der `Prelude`. Und dort ist auch `gcd` schon definiert ─ "greatest common divisior", also "ggt" auf englisch.

`permut` lässt sich selbstverständlich auch in Python realisieren, aber das würde man so nicht machen. Haskell ist eine "lazy" Sprache, d.h. es wird von Listen immer nur so viel ausgewertet, wie auch zu Berechnungen an anderer Stelle gebraucht wird. Die Haskell-Funktion erstellt also nicht alle möglichen Listen auf einmal. Das würde nämlich eine Menge Speicher verbrauchen, obwohl man in dem TSP-Algorithmus nie alle Listen auf einmal betrachtet, sondern immer eine nach der anderen. In Python würde man deshalb dafür eher eine Generator-Funktion schreiben, also explizit "lazy" arbeiten.
BlackMamba
User
Beiträge: 77
Registriert: Samstag 24. März 2007, 23:22
Wohnort: Germany,NRW,

Freitag 8. Februar 2008, 17:33

ups.....peinlich, klar ist das Haskell Code.....da war ich heute morgen wohl noch nicht ganz wach.... Entschuldigung!

Aber wie könnte man denn so eine Generatorfunktion schreiben? Gibts da Tutorials oder ähnliches zu?

Danke für die Hilfe!
Antworten