mathematische Operationen

24.04.2010, 23:24

Bognari

mathematische Operationen

Huhu, ich habe als aufgabe in Haskell rekursiv mathematische Operationen zu implemetieren. Ok um den Code an sich geht es mir nicht sondern mehr um das mathematische Verständnis. Für alle grund Operationen(Plus bis Potenz) gilt ja:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:

plus :: Integer -> Integer -> Integer
plus a 0 = a
plus a b = (succ a) `plus` (pred b)
			
mult :: Integer -> Integer -> Integer
mult a 0 = 0
mult a 1 = a
mult a b = a `plus` (a `mult` (pred b))

pot :: Integer -> Integer -> Integer
pot a 0 = 0
pot a 1 = a
pot a b = a `mult` (a `pot` (pred b))

Kurze Erklärung zur Syntax also succ gibt einem immer den Nachfolger und pred den Vorgänger. "--" Kommentar also ist dem ghci völlig egal was da steht.

Hier raus kann man sich die alg Form ableiten die da wäre:

code:
1: 2: 3: 4:	meta :: Integer -> Integer -> Integer -> Integer meta n a b = meta (pred n) a (meta n a (pred b))

Problem ist nun nur die Abbruchfälle.

Bis jetzt sind diese:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:

meta 0 a 0 = a 								-- abbruch plus
meta 0 a b = meta 0 (succ a) (pred b)		                -- plus normal
meta 1 a 0 = 0								-- abbruch mal
--meta 1 a 1 = a								-- abbruch mal
--meta 2 a 0 = 1								-- abbruch pot
--meta 2 a 1 = a 								-- abbruch pot
meta n a 0 = 1								-- zusammen gefasst
meta n a 1 = a								-- zusammen gefasst

Jedoch funktioniert das ganze nicht richtig. Ok solange n < 3 ist geht alles. Nur bei 3 und höher "bricht er ins Essen"

kleine I/O Tabelle

meta 3 1 1 --> 1
meta 3 1 2 --> 1
meta 3 2 1 --> 2
meta 3 2 2 --> 4
meta 3 2 3 --> 16
meta 3 2 4 --> *
meta 3 3 1 --> 3
meta 3 3 2 --> 27
meta 3 3 3 --> *
meta 3 4 1 --> 4
meta 3 4 2 --> 256

* = keine ausgabe, 100% CPU auslastung, ok auch verständlich wegen der sehr verschachtelten Rekursion. aber ein Stack Overflow tritt nicht auf.

Nun meine eigendliche Frage. Hat wer einen logischen Fehler bei der Funktion gefunden? Also in den Abbruch Bedingungen usw?

Ist das mathematische wirklich für meta 3 a b --> a^a für die anzahl von b?
b = 2 --> a^a
b = 3 --> a^a^a
b = 4 --> a^a^a^a

Was wäre dann meta von 4 ? usw

Danke schonmal für eine Antwort

24.04.2010, 23:26

Bognari

Auf diesen Beitrag antworten »

Hier die ganze Funktion:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:

meta :: Integer -> Integer -> Integer -> Integer
meta 0 a 0 = a 								-- abbruch plus
meta 0 a b = meta 0 (succ a) (pred b)		-- plus normal
meta 1 a 0 = 0								-- abbruch mal
--meta 1 a 1 = a								-- abbruch mal
--meta 2 a 0 = 1								-- abbruch pot
--meta 2 a 1 = a 								-- abbruch pot
meta n a 0 = 1								-- zusammen gefasst
meta n a 1 = a								-- zusammen gefasst
meta n a b = meta (pred n) a (meta n a (pred b)) -- standartfall

25.04.2010, 08:26

kiste

Auf diesen Beitrag antworten »

Sieht mir ziemlich nach der http://de.wikipedia.org/wiki/Ackermannfunktion aus.

Neue Frage »

Antworten »

mathematische Operationen

Verwandte Themen