Algorithmusentwurf und Laufzei < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:19 So 25.11.2007 | | Autor: | tommy987 |
| Aufgabe | Zwei Supermarktketten (A und B) haben sich geeinigt in einem noch unberührten Land (d.h. ohne
Supermärkte) ihre Läden folgendermaßen zu errichten:
In jedem Ort soll es genau einen Supermarkt geben.
Sind zwei Orte benachbart, so sollen die Supermäkte je zu einer Firma gehören.
Sie sollen nun einen Algorithmus (Pseudocode + verst¨andliche Erkl¨arung) entwerfen, welcher überpr
üft, ob eine solche Aufteilung möglich ist. Zu jedem Ort x gibt es eine Liste x ! n[1 . . . k] der k
Nachbarorte (der Einfachheit halber nehen wir an daß jeder Ort genau k Nachbarorte besitzt). Sie
können beliebige Zusatzinformationen in Zusammenhang mit einem Ort speichern. Zum Beispiel
k¨onnte x ! m angeben zu welcher Supermarktkette (A oder B) der Supermarkt im Ort x schlußendlich
geh¨ort. Weiters d¨urfen Sie die drei Funktionen push(S,x), pop(S) und is_empty(S) für
einen beliebigen Stack S verwenden. Analysieren Sie weiters die Laufzeit Ihrer Lösung.
STAPEL_LEER(S)
1: IF t=0
2: RETURN TRUE
3: ELSE FALSE
PUSH (S,x)
1: IF t=n THEN 'overflow'
2: ELSE
3: t=t+1
4: S[t]=x
POP (S)
1: IF STACK_LEER THEN 'underflow'
2: ELSE
3: x=S[t]
4: t=t-1 |
Hallo!
Ich weiß hier nicht mal einen Ansatz wie man das lösen könnte, kann mir wer weiterhelfen?
lg Thomas
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:12 Di 27.11.2007 | | Autor: | tommy987 |
Man braucht glaub ich Graphentheorie und Färbbarkeit eines
Graphen, wobei mir das in dieser Beziehung auch nicht viel sagt...
Mfg Thomas
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:40 Mi 28.11.2007 | | Autor: | Gilga |
Färbarkeit im einfachsten Fall (ausser Graph hat keine Kanten)
2-Färbbarkeit = bipartiter Graph (schau mal im web). z.B. Schwar und Weiß
Du fängst mit einem Knoten an. z.B. schwarz färben. dann gehst du zu allen nachbarn die müssen alle weiß werden. Jetzt du deren Nachbarn .....
Dabei wäre aber eine Queue nötig.
Beim Stack läuft man in die tiefe.
Man überprüft also immer ob der Knoten schon eine Farbe hat und welche Farbe der ausgehende Knoten hat....
|
|
|
|
