Haskell - Cantor-Paarungsfkt. < Haskell < Programmiersprachen < Praxis < Informatik < Vorhilfe
|
| Aufgabe | Die Menge [mm] \IN [/mm] x [mm] \IN [/mm] kann man mittels der Relation < total ordnen, indem man fordert:
(m,n) < (m',n') [mm] :\gdw [/mm] (m+n) < [mm] (m'+n')\vee [/mm] ((m+n) = (m'+n') [mm] \wedge [/mm] m < m').
Hierbei ist < die bekannte Ordnung über den natürlichen Zahlen.
Als Cantor-Nummerierung bezeichnen wir eine bijektive Funktion cpn : [mm] \IN [/mm] x [mm] \IN \to \IN [/mm] , für die gilt:
(m,n) < (m',n') [mm] :\gdw [/mm] cpn(m,n) < cpn(m',n'):
Zu cpn sei die Funktion cpi : [mm] \IN \to \IN [/mm] x [mm] \IN [/mm] invers, das hei¼t, es gilt:
cpi(cpn(m,n)) = (m,n) und cpn(cpi(i)) = i:
Implementieren Sie diese Funktionen in Haskell, wobei die folgenden Typvorgaben genutzt werden sollen:
cpn::(Int,Int)->Int
cpi::Int->(Int,Int) |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo...
Also die Aufgabe fordert, das man die Cantor-Paarungsfunktion ausgibt. Einmal durch cpn und durch cpi.
Beispiel wäre: cpn (2,3) = 17 und cpi 17 = (2,3).
Wie man cpn implementier, weiss ich:
cpn::(Integer,Integer)->Integer
cpn(0,0)=0
cpn(0,a)=cant(a-1,0) + 1
cpn(b,a)=cant(b-1,a+1) + 1
aber wie man das bei cpi macht, weiß ich nicht.
cpi ist einfach nur die umkehrfunktion und ich weiß, laut wikepedia, man muss erst ein f(i) bestimmen, das kleiner ist als z.B 17 und das ist f(i) = 5.
Dann ist x = 17 - f(j) = 17 - f(5) = 17 - 15 = 2.
Und y = j - y = 5 - 2 = 3.
Hab das mal auch so versucht zu implementieren, hat aber nicht geklappt. (Bin auch von cpn ausgegangen)
Hier eine Idee:
cpi::Int->(Int,Int)
cpi0=(0,0)
cpi n ....??? (Hier bleib ich immer stecken)
Ich muss sagen, das:
n > cant(i-1,0)
x = n - cant(i-1,0) + 1
y = a - x ...oder so?
Ich weiss nicht, wahrscheinlich ist das auch der falsche Anfang, aber weiß nicht wie ich es anders machen kann.
Also der Anfang:
cpi::Int->(Int,Int)
cpi0=(0,0)
cpi n ...müsste richtig sein, nach cpi n kommen bestimmt die Bedingungen für (x,y),
aber wie sage ich das n größer sein muss als die zu suchende variable i und wie implementier ich dazu x und y?
Kann mit jemand einen Tipp geben?, bitte
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:36 Mo 03.12.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
