www.jammni.de

Gepostet:
08.11.2009 22:35

isMajEl Mehrheitselement Anfänger

ich hab folgende Aufgabe:

Als Mehrheitselement einer Liste der Länge n wird ein Element bezeichnet, das mehr als n/2 mal in der Liste enthalten ist.

1. Definieren Sie ein Haskell-Prädikat isMajEl, das für eine Liste und ein gegebenes Element prüft, ob das Element ein Mehrheitselement der Liste ist.
2. Analysieren Sie den Aufwand für ihre Lösung zu a) (O-Notation). Was ist der günstigste Fall, was der ungünstigste?

hab nur den theoretischen ansatz, dass man die zahl mit jedem elemt der liste vergleichen müsste und nebher die anzahl der übereinstimmungen zählen....

Zum Seitenanfang

Siracusa

Gepostet:
09.11.2009 01:50

Hallo,

schau dir mal die Funktion filter an, mit der kannst du aus einer Liste mittels einer beliebigen Filterfunktion bestimmte Elemente raussuchen. Wenn du deine Liste nach deinem potentiellen Mehrheitselement filterst, bekommst du eine Liste die sooft dieses Element enthält, wie das Element in der Liste vorkommt. Dann auf dieser Liste die Funktion length aufrufen und schon weißt du, wie oft das Element in der Ausgangsliste vorkommt. Zum Schluss fehlt dann nur ein einfacher Test, ob das Element auch tatsächlich öfter als n/2 Mal vorkommt.

Noch ein Hinweis zum Aufwand: filter und length gehen die Liste jeweils einmal komplett durch.

Viele Grüße,

Siracusa

Zum Seitenanfang

Luks

Gepostet:
09.11.2009 10:24

irgendwie hab ich nen fehler drinn, aber ich finde ihn nicht.
bei beiden varianten bekomm ich ne fehlermeldung, bei der ersten wird das then nicht akzeptiert und bei der 2ten das ´=` vor True

isMajEl :: Eq a => [a] -> a -> Bool
isMajEl [xs] y		= test(length(filter (==y) [xs]))

test :: a->Bool
--test a			= if a>((length([xs])/2)
--				then True
--			   	else False

test a			| a>((length([xs])/2) 	= True
			        | otherwise		= False

Zum Seitenanfang

Siracusa

Gepostet:
09.11.2009 17:58

Ein klassischer Klammerfehler, da fehlt jeweils ne "Klammer zu". :-)

Zum Seitenanfang

Skater203

Gepostet:
09.11.2009 20:30

Ich habe es so gemacht, dass ich mir eine Hilfsfunktion geschrieben habe, die mir eine Liste mit denen Elementen liefert, für die auch geprüft werden soll, ob es sich um ein Mehrheitselement handelt.

Ist diese Liste größer als die Hälfte der gesamten Liste, so handelt es sich um ein Mehrheitselement, ansonsten nicht.

Zum Seitenanfang

Haskell-Forum