Ermitteln des ggT in Haskel < Haskell < Programmiersprachen < Praxis < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 06:51 So 02.11.2008 | | Autor: | setag19 |
| Aufgabe | Aufgabe : Der Euklidische Algorithmus ist eine Methode zur Bestimmung des größten
gemeinsamen Teilers (ggT) zweier ganzer Zahlen.
1. Ermitteln Sie die Funktionsweise und beschreiben Sie diese mit Worten.
2. Implementieren Sie den Algorithmus in HASKELL. |
Hallo,
ich bin neu hier im Forum und wollte hier mal um etwas Hilfe bitte.
Die Lösung der Aufgaben habe ich schon fast alleine geschafft, jedoch bin ich ein totaler Haskell Neuling und tu mich bei der Umsetzung etwas schwer. Der Algorithmus zur Berechnung des ggT ist nicht sehr kompliziert:
Sind zwei Zahlen a (=1473) und b(=1824) gegeben, so errechnet man den ggT auf folgenden Weg:
Solange b [mm] \not= [/mm] 0 :
- Wenn a > b ist, dann gilt a - b = a
- Wenn a < b ist, dann gilt b - a = b
Ist b = 0:
- ist a der ggT
Ich hab das ganze auf einem Zettel ausprobiert, der ggT ist in diesem Fall 3. So, nun wollte ich das ganze in Haskell implementieren. Ich kopiere hier am besten mal meine Idee rein:
> ggt :: Int -> Int -> Int
> ggt a b
> | a > b = a - b = a
"wenn a > b ist, soll a - b = a sein"
> | a < b = b - a = b
"wenn a < b ist, soll b - a = b sein"
> | b = 0
> | ggt = a
"ist b jedoch null, ist a der ggT."
So ungefähr sollte das Programm ablaufen. Hab das ganze schon mit diversen Veränderungen in Haskell versucht umzusetzen, jedoch funktioniert es einfach nicht. Das ist gerade mal mein 2. Programm in Haskell und mein 3. Programm überhaupt, weshalb ich euch bitte, mir solch große Syntaxfehler zu verzeihen.
Es wäre nett wenn mit jemand helfen könnte, das Programm zum laufen zu bringen bzw. die Syntax gerade zu biegen.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Danke im Vorraus für jede Hilfe.
|
|
| |
|
Hi, machs dir nich schwerer als es eigentlich is.
Du weißt, dass EUKLIDs Algorithmus folgende Beziehungen nutzt:
ggt(x,y) = ggt(y, Rest von x/y) falls y>0
ggt(x,y) = x falls y=0
Eine mögliche Realisierung in Haskell:
ggt :: Int -> Int -> Int
ggt x y =
if y > 0 then ggt y(rem x y)
else if y == 0 then x
else error "ggt: Argument y darf nicht negativ sein"
Oder: Alternative Lösung mit Wächtern (guards):
ggt x y
| y > 0 = ggt y (rem x y)
| y == 0 = x
| otherwise = error "ggt: Argument y darf nicht negativ sein"
Wenn du die Syntax-Zeichen nicht verstehst, solltest du danach googeln, denn diese sind in Haskell (besonders bei Rekursion) wichtig!
Lg von auch Haskell-Neulings-Dame ;)
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 00:37 Di 18.11.2008 | | Autor: | scaary |
Wenn ich hierzu auch noch eine Frage stellen duerfte:
Ich hab mir folgenden Code zum GGT ausgedacht:
ggt :: (Int, Int) -> Int
ggt a = if a == 0 then a
else ggt (a,b) = ggt (b,a mod b)
Kriege hierzu aber dann folgende Fehlermeldung:
[mm] C:\Documents [/mm] and [mm] Settings\Sascha\My Documents\Eclipse Workspace\Haskell\src\Ggt.hs:6:18:
[/mm]
parse error on input `=
Ich weiss leider nicht, was an dem = falsch sein soll?
Ahja, eine Sache noch, benutze ich deinen code (also den ersten Code, den du angegeben hast, Realisierung 1), erhalte ich folgende Fehlermeldung:
*Ggt> 4 3
<interactive>:1:0:
No instance for (Num (t -> t1))
*Ggt> arising from the literal `4' at <interactive>:1:0-2
Possible fix: add an instance declaration for (Num (t -> t1))
In the expression: 4 3
In the definition of `it': it = 4 3
Was genau hat er denn zu bemaengeln?
Vielen lieben Dank im Vorraus!!
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:31 Di 18.11.2008 | | Autor: | rainerS |
Hallo!
> Wenn ich hierzu auch noch eine Frage stellen duerfte:
>
> Ich hab mir folgenden Code zum GGT ausgedacht:
>
> ggt :: (Int, Int) -> Int
> ggt a = if a == 0 then a
Was bedeutet denn ggt mit nur einer Zahl?
> else ggt (a,b) = ggt (b,a mod b)
Da steht in else-Zweig eine Funktionsdefinition.
Überleg dir auch mal, was in deiner Funktion im Fall b>a passieren sollte!
> Ahja, eine Sache noch, benutze ich deinen code (also den
> ersten Code, den du angegeben hast, Realisierung 1),
> erhalte ich folgende Fehlermeldung:
>
> *Ggt> 4 3
Wo rufst du denn deine Funktion ggt auf? Schreibe einen Funktionsaufruf statt zweier Zahlen: ggt 4 3
Viele Grüße
Rainer
|
|
|
|
