Haskell - Cantornummerirung < 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) < ((m+n) = (m'+n') 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
Durch k-fache Anwendung der Funktion cpn kann man die Nummerierung auf Folgen
[mm] \alpha \in \IN^{k+1} [/mm] der Länge
k + 1 erweitern:
[mm] ctn^{k} (m_{k}m_{k-1}...m_{1}m_{0}) [/mm] = [mm] cpn(m_{k},cpn(m_{k-1},...cpn(m_{1},m_{0})...)):
[/mm]
Das heißt, es ist [mm] ctn^{k}: \IN^{k} \to \IN [/mm] induktiv de¯niert durch:
[mm] ctn^{0} (m_{0}) [/mm] = [mm] m_{0}, ctn^{k+1} (m_{k+1}+m_{k}...m_{0}) [/mm] = [mm] cpn(m_{k},ctn^{k} (mx_{k}...mx_{0})):
[/mm]
Zu [mm] ctn^{k} [/mm] sei die Funktion [mm] cti^{k} [/mm] : [mm] \IN \to \IN^{k} [/mm] invers, das heißt, es gilt:
[mm] cti^{k} (ctn^{k} (m_{k},m_{k-1},...,m_{1},m_{0})= (m_{k},m_{k-1},...,m_{1},m_{0}) [/mm] und [mm] ctn^{k} (cti^{k}(i)) [/mm] = i:
Schließlich kann man zur Nummerierung der Menge [mm] \IN^{+} [/mm] |= [mm] \IN^{*} [/mm] - { [mm] \varepsilon [/mm] } eine bijektive Funktion cfn : [mm] \IN^{+} \to \IN [/mm] definieren durch:
[mm] cfn(\alpha) [/mm] = [mm] cpn(|\alpha| [/mm] - 1, [mm] ctn^{|\alpha|-1} (\alpha));
[/mm]
wobei [mm] |\alpha| [/mm] die Länge der Folge [mm] \alpha [/mm] ist. Hierzu sei cfi die inverse Funktion.
Implementieren Sie diese Funktionen in Haskell, wobei die folgenden Typvorgaben genutzt werden sollen:
cfn::[Int]->Int
cfi::Int->[Int] |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallöchen..........
Kann mir einer bitte erklähren, was ich jetzt machen soll?
Verstehh weder die Aufgabenstellung, noch die Definitionen.
Ich weiss, es handelt sich hier um die Cantornummerierung.
Kann jemand helfen und mir beim Anfang helfen?
--Standard-Testfall cfn [2,3] == 172
cfn::[Int]->Int
--Standard-Testfall cfi 172 == [2,3]
cfi::Int->[Int]
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:44 Mo 03.12.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
