Gepostet: 05.07.2006 13:30 |
Erklärung der Programme |
|
hi, hab das forum grad gefunden. ich glaub ich bin mit blizz im gleichen studiengang, ich muss die gleichen programme abgeben! :)
nun mein anliegen: könntet ihr mir die programme von blizz schrit für schritt und zeile für zeile erklären was da gemacht wird? ich komm mit haskell nämlich nicht so gut klar, vielleicht erweitert das dann meinen Horizont *g*
hab mal die ersten 3 Proggs mit eingefügt! ich glaub das wär ne große Hilfe für mich wenn das jemand machen könnte!
Progg 1
countstring str leng=co(zerlege str leng [] []) where co ((c,i):[])=((concat c),i):[] co ((c,i):ws)=((concat c),i):(co ws)
zerlege [] leng [] liste= liste zerlege [] leng teil liste=inlist [teil] liste zerlege (s:str) leng teil liste | ( (length(teil++[s]))==leng )= zerlege str leng [] (inlist [teil++[s]] liste) | otherwise =zerlege str leng (teil++[s]) liste
inlist x []= ((x,1):[]) inlist x ((c,count):list) |(x==c) = (c,(count+1)): list | otherwise = (c,count): (inlist x list)
--stringStatistik :: String -> Int -> [(String,Double)] stringStatistik str leng= rechne (countstring str leng) where rechne ((c,i):[]) = (c,(i `div` length str)) :[] rechne ((c,i):list) = (c,(i `div` length str)) : rechne list
Progg 2
substitute::String->(Char,Char)->String substitute [] (a,b)="" substitute (w:wort) (a,b) |(w==a) = [ b ] ++substitute wort (a,b) |otherwise =[w]++substitute wort (a,b)
substituteAll::String->[(Char,Char)]->String substituteAll wort []="" substituteAll wort ((a,b):liste) = (substitute wort (a,b))++substituteAll wort liste
caesar::Int->[(Char,Char)] caesar zahl= ('A',toEnum((fromEnum 'A')+zahl)::Char):('B',toEnum((fromEnum 'B')+zahl)::Char):[]
Progg3
import Char -- für Zeichenumwandlung "toUpper"
getLetters:: String -> String getLetters = map toUpper . filter isAlpha . filter isAscii
vigenere :: String -> String -> String vigenere key text=vignere2 key key (getLetters text) vignere2 key acc []="" vignere2 key [] t=vignere2 key key t vignere2 key (a:acc) (s:text)=[(toEnum( ( (fromEnum a)+(fromEnum s)-128 )`mod`26 +64)::Char)]++(vignere2 key acc text)
|
Zum Seitenanfang |
|
|
|
Gepostet: 05.07.2006 16:53 |
|
|
prog1
--zählt alle strings der länge leng...die variable str ist der eingabestring countstring str leng=co(zerlege str leng [] []) where co ((c,i):[])=((concat c),i):[]--das hier wird nur gemacht damit die listen vereinigt werden co ((c,i):ws)=((concat c),i):(co ws) --zerlege teilt den string in stücke der leng --man hat dabei 2 listen(die variablen liste und teil) die man mitführt um sich zwischenwerte zu speichern... --in liste ist die bisher aufgebaute liste mit teilstückchen der länge leng enthalten und in teil der teil der liste den man --bisher schon aus dem string genommen hat..
zerlege [] leng [] liste= liste zerlege [] leng teil liste=inlist [teil] liste zerlege (s:str) leng teil liste --wenn das teilstück gleich der länge leng ist wird es in die Liste liste eingefügt und die zerlegefunktion wird rekursiv --aufgerufen mit teil==[] | ( (length(teil++[s]))==leng )= zerlege str leng [] (inlist [teil++[s]] liste) | otherwise =zerlege str leng (teil++[s]) liste--ansonsten werden weitere buchstaben zu teil hinzugefügt
--hier wird geprüft ob ein teilstück in der liste enthalten ist...wenn ja wird der zähler count erhöht...wenn nein wird das teilstück in die liste --mit dem zählerwert count eingefügt inlist x []= ((x,1):[]) inlist x ((c,count):list) |(x==c) = (c,(count+1)): list | otherwise = (c,count): (inlist x list)
--stringStatistik :: String -> Int -> [(String,Double)] stringStatistik str leng= rechne (countstring str leng) where rechne ((c,i):[]) = (c,(i `div` length str)) :[] rechne ((c,i):list) = (c,(i `div` length str)) : rechne list
Progg 2
--substitute ersetzt einen buchstaben durch einen anderen substitute::String->(Char,Char)->String substitute [] (a,b)=""-- der rekursionsanker substitute (w:wort) (a,b)--hier wird immer der erste Buchstabe aus dem string genommen und überprüft ob dieser gleich dem zu ersetzenden char ist...wenn ja ersetzen |(w==a) = [ b ] ++substitute wort (a,b) |otherwise =[w]++substitute wort (a,b)---ansonsten wird der buchstabe nicht verändert --das ergebnis ist ein string und man fügt alle buchstaben hintereinander --substituteall erhält eine liste von buchstaben und ersetzt alle davon , dafür wird für substituteAll::String->[(Char,Char)]->String substituteAll wort []="" substituteAll wort ((a,b):liste) = (substitute wort (a,b))++substituteAll wort liste
--in caesar ist die liste der strings die substituiert werden sollen...mit (fromEnum einChar) verwandelt man einen char in einen numerischen wert --die funktion toEnum (eine zahl)::Char macht aus einen numerischen wert wieder einen char caesar::Int->[(Char,Char)] caesar zahl= ('A',toEnum((fromEnum 'A')+zahl)::Char):('B',toEnum((fromEnum 'B')+zahl)::Char):[]
Progg3
import Char -- für Zeichenumwandlung "toUpper" --iliefert nur großbuchstaben getLetters:: String -> String getLetters = map toUpper . filter isAlpha . filter isAscii
--addiert ein wort auf einen text auf vigenere :: String -> String -> String vigenere key text=vignere2 key key (getLetters text) vignere2 key acc []=""** vignere2 key [] t=vignere2 key key t* --ist eine hilfsfunktion die immer den key der auf das wort aufaddiert wird...dabei geht man immer buchstabenweise vor --man nimmt sich den ersten buchstaben aus dem key und addiert ihn zum ersten buchstaben aus dem text der zu verschlüßeln ist --dann den zweiten buchstaben aus dem key zu dem zeiten buchstaben aus dem text... ---sollte der key dann irgendwann aufgebraucht werden tritt der fall sternchen auf und die funktion wird wieder mit dem neuen key aufgerufen --sollte irgendwann der text leer sein tritt der fall** win...und es wird nur noch ein leerer string zurrückgegeben... ---das programm addiert rekursiv alle so geänderten buchstaben zusammen mit (fromEnum einChar) verwandelt man einen char in einen numerischen wert --die funktion toEnum (eine zahl)::Char macht aus einen numerischen wert wieder einen char vignere2 key (a:acc) (s:text)=[(toEnum( ( (fromEnum a)+(fromEnum s)-128 )`mod`26 +64)::Char)]++(vignere2 key acc text)
ich hoffe das war einigermassen verständlich gruß jacke |
Zum Seitenanfang |
|
|
|
Gepostet: 06.07.2006 14:25 |
|
|
Danke, ich werds mir mal anschauen! Könntest du das bei den anderen auch machen?
Progg4
test=vigenere "akey" "geheimnis"
korre::String->String->Int korre s [] = 0 korre [] t = 0 korre (si:s) (ti:t) |(si==ti)=1+ (korre s t) |otherwise= 0 + (korre s t)
--in acc steckt der um jeweils ein leerzeichen verschobene text auto2::String->String->[Int] auto2 [] acc=[] auto2 (ti:t) acc= (korre (ti:t) acc): (auto2 t (' ':acc))
auto t =auto2 t ((' '):t) --hier wird die hilfsfunktion 2mal mit dem ursprungstext aufgerufen, die erste verschiebung wird auch gleich gemacht
Progg5
da wurds schon erklärt hab ich gesehen
Progg6
newtype Node a = Node a deriving (Read,Show,Eq) data Edge a b = Edge (Node a,Node a) b deriving (Read,Show,Eq) data Graph a b = Graph [Edge a b] deriving (Read, Show)
--qsort:: Ord a => [a] -> [a]
qsort (Graph x)=(Graph (qsort2 x)) qsort2 []=[] qsort2 ((Edge (Node c,Node d) x):xs) = ((qsort2 kleiner) ++[(Edge (Node c,Node d) x)] ++ (qsort2 groesser)) where kleiner = ([y|y <- xs, (getgewicht y)<x]) groesser= ([y|y <- xs, (getgewicht y)>x]) getgewicht (Edge (Node l,Node s) m)=m
test=(Graph ([(Edge (Node 'a',Node 'b') 7),(Edge (Node 'b',Node 'c') 3),(Edge (Node 'c',Node 'e') 6),(Edge (Node 'b',Node 'e') 2)]))
--kreisfrei prüft ob der graph immernoch kreisfrei ist wenn man einen knoten dazu nimmt --suche ist eine unterfunktion die prüft ob auch der andere knoten drin ist kreisfrei x (Graph []) =True kreisfrei (Edge (Node c,Node d) k) (Graph ((Edge (Node e,Node f) x):xs)) | ((c == e)||(c==f))&&((d == e)||(d==f))=False --wenn diesselbe kante schon drin ist | ((c == e)||(c==f)) =suche d xs | ((d == e)||(d==f)) =suche e xs | otherwise = kreisfrei (Edge (Node c,Node d) k) (Graph xs) where suche v []=True suche v ((Edge (Node h,Node l) m):ms) |((v == h)||(v==l))=False |otherwise = suche v ms
Progg7
data Polynomial a = Polynomial [a] deriving (Show,Eq,Read)
instance (Num a) => Num (Polynomial a) where (Polynomial x) + (Polynomial y) = addFunktion x y
addFunktion x [] =Polynomial x
addFunktion [] x =Polynomial x addFunktion (x) (y) = Polynomial (rechne x y) where rechne [] h=h rechne z []=z rechne (m:ms) (n:ns)=(m+n):(rechne ms ns)
Danke schonmal im vorraus :) |
Zum Seitenanfang |
|
|
|
Gepostet: 06.07.2006 15:38 |
|
|
ok dann fang ich mal an
Progg4
//hier wird ein text"geheimnis" verschlüsselt test=vigenere "akey" "geheimnis"
--liefert die korreltation...die korreltionsfunktion funktioniert so das wenn zwei buchstaben gleich sind der rückgabewert um eins erhöht wird --siehe formel...ansonsten wird null zum rückgabewert addiert --die korrelation wird auf dem text und dem verschobenen text angewendet...unter wikipedia(nach vigenere suchen) ist das gut erklärt --damit kann man die länge des schlüssels ermitteln, weil die korreltion für die verschiebung dann am ähnlichsten ist korre::String->String->Int korre s [] = 0 korre [] t = 0 korre (si:s) (ti:t) |(si==ti)=1+ (korre s t) |otherwise= 0 + (korre s t)
--in acc steckt der um jeweils ein leerzeichen verschobene text --in der autokorrelationsfunktion wird der text bei jedem aufruf immer um ein zeichen nach rechts verschoben und dann die korreltionsfunktion --damit aufgerufen auto2::String->String->[Int] auto2 [] acc=[] auto2 (ti:t) acc= (korre (ti:t) acc): (auto2 t (' ':acc))
--ruft die hilfsfunktion auf auto t =auto2 t ((' '):t) --hier wird die hilfsfunktion 2mal mit dem ursprungstext aufgerufen, die erste verschiebung wird auch gleich gemacht
Progg6
--das ist der datentyp eines graphen...sollte klar sein newtype Node a = Node a deriving (Read,Show,Eq)--ein knoten data Edge a b = Edge (Node a,Node a) b deriving (Read,Show,Eq)--eine kante die zwei knoten verbindet und ein gewicht b hat data Graph a b = Graph [Edge a b] deriving (Read, Show)--ein graph der aus kanten besteht
--qsort:: Ord a => [a] -> [a] --kruskal ist ein greedy algorithmuns, und funktioniert so, dass man sich immer die kleinste kante nimmt --deshalb ist es praktisch die kanten der größe nach zu sortieren qsort (Graph x)=(Graph (qsort2 x)) qsort2 []=[]
--man nimmt sich die erste kante und fügt alle knoten die kleiner als die erste kannte sind links von x ein und alle knoten die größer als x sind rechts von x ein --es wird nach kanten gewicht sortiert qsort2 ((Edge (Node c,Node d) x):xs) = ((qsort2 kleiner) ++[(Edge (Node c,Node d) x)] ++ (qsort2 groesser)) where kleiner = ([y|y <- xs, (getgewicht y)<x])--eine mapfunktion die eine liste von alle kanten erstellt die kleiner als x sind groesser= ([y|y <- xs, (getgewicht y)>x])--eine mapfunktion die eine liste von alle kanten erstellt die größer als x sind getgewicht (Edge (Node l,Node s) m)=m--liefert das gewicht einer kante
--ein testgraph test=(Graph ([(Edge (Node 'a',Node 'b') 7),(Edge (Node 'b',Node 'c') 3),(Edge (Node 'c',Node 'e') 6),(Edge (Node 'b',Node 'e') 2)]))
--kreisfrei prüft ob der graph immernoch kreisfrei ist wenn man einen knoten dazu nimmt --suche ist eine unterfunktion die prüft ob auch der andere knoten drin ist kreisfrei x (Graph []) =True--wenn der knoten kreisfrei ist wird true zurückgegeben kreisfrei (Edge (Node c,Node d) k) (Graph ((Edge (Node e,Node f) x):xs))--wird mit der neuen kante aufgerufen die eingefügt werden soll | ((c == e)||(c==f))&&((d == e)||(d==f))=False --wenn diesselbe kante schon drin ist | ((c == e)||(c==f)) =suche d xs--wenn einer der beiden knoten schon drin ist, muß noch geschaut werden ob der andere knoten der kante enthalten ist | ((d == e)||(d==f)) =suche e xs--anlog zum fall davor | otherwise = kreisfrei (Edge (Node c,Node d) k) (Graph xs)--es wird immer eine kante nach der anderen aus dem graphen geprüft ->Rekursion where suche v []=True --der graph ist kreisfrei weil der zweite knoten nicht drin ist suche v ((Edge (Node h,Node l) m):ms) |((v == h)||(v==l))=False --der graph ist nicht kreisfrei weil der zweite knoten auch noch drin ist |otherwise = suche v ms --ansonsten den graph weiter nach dem zweiten knoten absuchen
--bei dem algorithmus hilft es sich den grapeh mal aufzumalen
Progg7
--was nen datentyp ist sollte man auch so wissen data Polynomial a = Polynomial [a] deriving (Show,Eq,Read) --num definieren..ins skript schauen ! instance (Num a) => Num (Polynomial a) where (Polynomial x) + (Polynomial y) = addFunktion x y
--addiert zwei polynome
addFunktion x [] =Polynomial x
addFunktion [] x =Polynomial x addFunktion (x) (y) = Polynomial (rechne x y) where rechne [] h=h--rechne ist ne hilfsfunktion zum addieren rechne z []=z rechne (m:ms) (n:ns)=(m+n):(rechne ms ns)--arbeitet rekursiv
Danke schonmal im vorraus :)
ok gern geschehen...bin erst samstag abend wieder da...hoffe die erklärungen reichen...ich glaube es ist auch gut zum lernen wenn man sich selber in den code reindenkt und nicht alles erklärt bekommt
gruß jacke |
Zum Seitenanfang |
|
|
|
Gepostet: 11.07.2006 12:46 |
|
|
eine frage hätte ich noch:
sortByChar :: [(Char, Integer)] -> [(Char, Integer)] sortByChar list = sortBy compareChar list
compareChar:: (Char, Integer) -> (Char, Integer) -> Ordering compareChar (ch1,i1) (ch2,i2) = compare ch1 ch2
sortByNumber :: [(Char, Integer)] -> [(Char, Integer)] sortByNumber list = sortBy compareNumber list
compareNumber :: (Char, Integer) -> (Char, Integer) -> Ordering compareNumber (ch1,i1) (ch2,i2) = compare i1 i2
das sortiert ja eine liste.
aber was macht die funktion "compare" hier genau? |
Zum Seitenanfang |
|
|
|
Gepostet: 11.07.2006 17:47 |
|
|
also compare vergleicht zwei werte, das können chars sein oder ints sein
ein beispiel compare 1 2 gibt LT zurück (kleiner) compare 1 1 gibt EQ zurück (gleich) compare 1 1 gibt GQ zurück (größer)
compare a b gibt LT zurück (kleiner) compare a a gibt EQ zurück (gleich) compare c a gibt GQ zurück (größer)
comparechar ruft compare nur auf den chars der tupel auf und vergleicht diese
comparenaumber auf den ints
gruß jacke
|
Zum Seitenanfang |
|
|
|