[HaBo]

**CDW** · 06.06.07, 00:13

Eingereicht von Ivan Dolvich

(aus dem Bundeswettbewerb Informatik, sollte aber zu schaffen sein, eventuell ist Schwierigkeit 3 sogar übertrieben ;) )

Aufgabenstellung: tratsCH trATsch

Die Leute vom Planeten Chator schreiben gern Schlechtes ubereinander.
Wer vielen uber andere Schlechtes schreibt, gilt als besonders charmant.
Aber natürlich nur, wenn die Kompromittierten nichts davon erfahren.
Chatonen schreiben nur an Leute, die Ihnen sympathisch sind. Doch die
können den Tratsch weitertragen, und eventuell genau an den Falschen.
Ein Chatone muss also gut aufpassen, dass er keinen Charmefehler macht.
Dieses Missgeschick passierte unlängst Ator, als er Btor Schlechtes
über Dtor schrieb. Zu dumm: Dtor ist dem Ctor sympathisch, der wiederum
Btor sympathisch ist.

Und so landete der Tratsch bei Dtor, der uber Ator verständlicherweise
sehr verärgert war. Dies hätte Ator mit ein wenig Übersicht vermeiden
können, denn schließlich wissen alle Chatonen voneinander, wer wem
sympathisch ist.

Aufgabe:
Programmiere einen Charminator, der einliest, welche Chatonen welchen
anderen sympathisch sind. Er soll auf dieser Grundlage möglichst kompakt
für alle Chatonen ausgeben, wem der Betreffende uber wen Schlechtes
schreiben kann, ohne einen Charmefehler zu riskieren.
Teste dein Programm an drei Beispielen für mindestens 5 und höchstens 10
Chatonen; verwende auf jeden Fall das folgende Beispiel:

Code:

  Dem Chatonen      sind sympathisch:
  A                 B E
  B                 C
  C                 D G
  D                 C
  E                 F
  F                 B E G
  G                 H
  H                 D

Bedenke dabei, dass eine Tratschnachricht von Chatone x nach Chatone y
weder x noch y betrifft und dass ein Chatone eine Nachricht, die
ursprünglich von ihm selbst stammt und wieder bei ihm ankommt, nicht
weiterleiten wird ? so dumm sind Chatonen nicht

Lösungsansatz

J.U.B. · 06.06.07, 09:17

Also habe ich das jetzt wie folgt verstanden:
man solle ein Programm entwickeln in dem man zusätlich zu den ausgaben wehm wer sympathish ist noch über wehm er lästern kann ausgeben... ungefär so?:

Code:

Dem Chatonen     sind sympatisch:   und kann über diese lästern:
A                B E
B                C                   A E F
C                D G                 A B E F
D                C                   A B E F
E                F                   A
F                B E G               A
G                H                   A B E F
H                D                   A B E F

Anzeige

- Anzeige -

**CDW** · 06.06.07, 13:38

Wer wem sympatisch ist, soll vom Benutzer eingegeben werden.
Das Programm soll dann ermitteln, wem ein bestimmter Chatone über einen anderen eine Lästernachricht schicken kann, ohne dass der Chatone, über den dabei gelästert wird, es mitbekommt.

Also: ein Chatone lästert über einen andern. Dabei schickt er seine Lästernachricht an die ihm sympatischen Chatonen. Diese wiederum leiten diese Nachricht an die ihnen sympatischen.

Bsp: A lästert über C. Schickt also seine Nachricht an B,E weiter. E schickt diese an F, B dagegen leitet sie an C weiter - Fehler.

J.U.B. · 06.06.07, 16:09

Ok
Ich hätte dann folgende Lösung in PVX

Code:

dim chaton$[8], sym$[8], ok$[8], xy$[1000], okdu$, lehr$(20)
chaton$[1]="A"
chaton$[2]="B"
chaton$[3]="C"
chaton$[4]="D"
chaton$[5]="E"
chaton$[6]="F"
chaton$[7]="G"
chaton$[8]="H"
lehr$(20)="                    "
	
FOR B=1 TO 8 STEP 1
PRINT 'CS',
PRINT "Bitte geben Sie ein wer ",chaton$[B]," sympatisch ist."
INPUT "Eingabe: ",sym$[B]
NEXT

PRINT 'CS',

for I=1 TO 8 STEP 1
	LET A=1
	FOR K=1 TO 8 STEP 1
		IF chaton$[I]=chaton$[K] THEN {
		} ELSE {
			okdu$=""
			LET A=1
			xy$[A]=chaton$[I]
			L=LEN(sym$[I])
			FOR H=1 TO L STEP 1
				A++
				xy$[A]=sym$[I](H,1)
			NEXT
			FOR D=A-L TO 20 STEP 1
				FOR E=1 TO A-1 STEP 1
					IF xy$[E]=xy$[D] THEN {
						IF okdu$<>"Y" THEN {
							okdu$="X"
						}
					}
					IF xy$[E+1]=chaton$[K] THEN {
						okdu$="Y"
					}
				NEXT
				F=0
				FOR G=1 TO 8 STEP 1
					IF chaton$[G]=xy$[D] THEN {
						F=G
					}
				NEXT
				L=LEN(sym$[F])
				FOR H=1 TO L STEP 1
					A++
					xy$[A]=sym$[F](H,1)
				NEXT
			NEXT
			IF okdu$="X" THEN {
				ok$[I]=ok$[I]+chaton$[K]+" "
			}
		}
	NEXT
NEXT
PRINT "Dem Chatonen:    sind symphatisch:    und kann ",CHR(252),"ber folgende l",CHR(228),"stern:"
FOR I=1 TO 8 STEP 1
L=LEN(sym$[I])
PRINT chaton$[I],"                ",sym$[I],lehr$(L),ok$[I]
NEXT

[EDIT]
und der gleiche code etwas umgeschrieben für NOMADS mit GUI sieht dann so aus:

Ivan Dolvich · 13.06.07, 16:50

Hier ist meine Lösung mit Groovy, hab sie nach der Lösungsidee gemacht. Die Idee klingt vielleicht etwas kompliziert, die Lösung ist aber einfach.

Code:

class Chaton 
{
    String name      // Name des Chatonen
    List symps       // sympatische Chatonen
    
    Boolean marked   // Markierung für die Suche
    
    void markDeep()
    {
        if (!marked) {
            marked = true      // sich selbst markieren
            symps.each { 
                it.markDeep()  // rekursiv weiter markieren
            }
        }
    }
}

List createChatons()
{
    Chaton a = new Chaton(name:"A")
    Chaton b = new Chaton(name:"B")
    Chaton c = new Chaton(name:"C")
    Chaton d = new Chaton(name:"D")
    Chaton e = new Chaton(name:"E")
    Chaton f = new Chaton(name:"F")
    Chaton g = new Chaton(name:"G")
    Chaton h = new Chaton(name:"H")
    
    a.symps = [b, e]
    b.symps = [c]
    c.symps = [d, g]
    d.symps = [c]
    e.symps = [f]
    f.symps = [b, e, g]
    g.symps = [h]
    h.symps = [d]
    
    return [a, b, c, d, e, f, g, h]
}

List chatons = createChatons()

for (chaton in chatons) {
    chatons.each { it.marked = false }
    chaton.markDeep()
    List result = chatons.findAll { !it.marked }
    println "${chaton.name}: ${result*.name}"
}

Ausgabe

Code:

A: []
B: ["A", "E", "F"]
C: ["A", "B", "E", "F"]
D: ["A", "B", "E", "F"]
E: ["A"]
F: ["A"]
G: ["A", "B", "E", "F"]
H: ["A", "B", "E", "F"]

J.U.B. · 14.06.07, 09:40

@ CDW:

Diese Aufgabe hätte ruhig Schwierigkeit: 1 bekommen könne (oder evtl auch 2).

@ Ivan:

Mach das selbe mal mit benutzereingabe für die sympatischen Chatonen.

Ivan Dolvich · 14.06.07, 10:32

Die Benutzereingabe habe ich mir jetzt gespart weil das nichts spannendes ist, und von das eigentliche Problem (den Graphen abbilden und durchsuchen) abweicht.

mauralix · 16.06.07, 12:43

Mir gefällt diese Aufgabe. Erinnert mich voll ans echte Leben. In meiner Gemeinde leben wohl viele Chatonen.

**CDW** · 08.06.08, 00:09

das ganze mal in Prolog (SWI). Und ja, ich lerne es gerade

selbsterklärend ;)

kommentiert

ausgabe:

Code:

?- laesterListe(Chatone,Opfer).
Chatone = a,
Opfer = [] ;
Chatone = b,
Opfer = [a, e, f] ;
Chatone = c,
Opfer = [a, b, e, f] ;
Chatone = d,
Opfer = [a, b, e, f] ;
Chatone = e,
Opfer = [a] ;
Chatone = f,
Opfer = [a] ;
Chatone = g,
Opfer = [a, b, e, f] ;
Chatone = h,
Opfer = [a, b, e, f] ;

**CDW** · 15.08.08, 16:09

nochmal SWI/SICStus Prolog, in "schön kurz"

Startbar mit "laestern.". Einzelne Chatonen prüfen: laestern(Chatonenname).
Erweitern: einfach in die sympatic - Übersicht was hinzufügen/löschen, nach dem Muster: sym(Chatonenname,[Sympatisch,Sympatisch ...]).
Nicht-Isoprädikate: member,format
Ausgabe:

Zitat:

1163 ?- laestern.

Chatone a darf laestern ueber:
Chatone b darf laestern ueber:a e f
Chatone c darf laestern ueber:a b e f
Chatone d darf laestern ueber:a b e f
Chatone e darf laestern ueber:a
Chatone f darf laestern ueber:a
Chatone g darf laestern ueber:a b e f
Chatone h darf laestern ueber:a b e f
true.

MontyPerl · 26.11.08, 20:02

Auch prolog, mit hardgecodeten Sympathiebeziehungen und canTalkAbout Prädikat:

foo

Code:

?- canTalkAbout(c, X).

X = a ;

X = b ;

X = e ;

X = f ;

edit: Jahre später....
Hier mal eine kleine C Lösung:

charminator.c

Code:

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    char ID;
    int visited;
    struct node *links[9];
} node;

void conn(node *n, const char *dests, node **all);
void traverse(node *n, char senderID);
void canTalk(node *s, node **all);

int main(void) {
    /*   Dem Chatonen      sind sympathisch:
     *   A                 B E
     *   B                 C
     *   C                 D G
     *   D                 C
     *   E                 F
     *   F                 B E G
     *   G                 H
     *   H                 D
     */
    node a = { 'a', 0, { NULL } };
    node b = { 'b', 0, { NULL } };
    node c = { 'c', 0, { NULL } };
    node d = { 'd', 0, { NULL } };
    node e = { 'e', 0, { NULL } };
    node f = { 'f', 0, { NULL } };
    node g = { 'g', 0, { NULL } };
    node h = { 'h', 0, { NULL } };

    node all = { '\0', 0, { &a, &b, &c, &d, &e, &f, &g, &h, NULL } };

    conn(&a, "be",  all.links);
    conn(&b, "c",   all.links);
    conn(&c, "dg",  all.links);
    conn(&d, "c",   all.links);
    conn(&e, "f",   all.links);
    conn(&f, "beg", all.links);
    conn(&g, "h",   all.links);
    conn(&h, "d",   all.links);

    int i;
    for (i = 0; all.links[i]; i++) {
        canTalk(all.links[i], all.links);
    }
    return 0;
}

void conn(node *n, const char *dests, node **all) {
    int i, j, k;
    k = 0;
    for (i = 0; dests[i]; i++) {
        for (j = 0; all[j]; j++) {
            if (dests[i] == all[j]->ID) {
                n->links[k] = all[j];
                k++;
            }
        }
    }
    n->links[k] = NULL;
    return;
}

void canTalk(node *s, node **all) {
    int i;
    for (i = 0; s->links[i]; i++) {
        traverse(s->links[i], s->ID);
    }
    s->visited = 1;

    printf("%c can talk about:\t", s->ID);
    for (i = 0; all[i]; i++) {
        if (!all[i]->visited) {
            printf("%c ", all[i]->ID);
        }
        all[i]->visited = 0;
    }
    printf("\n");

    return;
}

void traverse(node *n, char senderID) {
    n->visited = 1;
    if (n->ID == senderID) {
        return;
    }
    int i;
    for (i = 0; n->links[i]; i++) {
        if (! n->links[i]->visited) {
            traverse(n->links[i], senderID);
        }
    }
    return;
}

Lesco · 17.06.09, 19:01

Hier noch eine Variante in Haskell:

Code:

import Control.Arrow
type Persons a = [(a,[a])]

persons = [("a",["b","e"])
          ,("b",["c"])
          ,("c",["d","g"])
          ,("d",["c"])
          ,("e",["f","g"])
          ,("f",["b","e","g"])
          ,("g",["h"])
          ,("h",["d"]) ]

isPath :: Ord a => Persons a -> a -> a -> [a] -> Bool
isPath ps src dst visited
    | src == dst = True
    | src `elem` visited = False
    | otherwise = any (\src' -> isPath ps src' dst (src:visited)) . maybe [] id . lookup src $ ps

canTalkAbout :: Ord a => Persons a -> a -> a -> Bool
canTalkAbout ps a b = not . isPath ps a b $ []

potTargets :: Ord a => Persons a -> a -> [a]
potTargets ps a = filter (canTalkAbout ps a) . map fst $ ps

fullList ps = map ((id &&& potTargets ps) . fst) ps

Anzeige

- Anzeige -

06.06.07, 00:13	#1 (permalink)
CDW Moderator Registriert seit: 20.07.05 Likes: 202	Charminator Anzeige Eingereicht von Ivan Dolvich (aus dem Bundeswettbewerb Informatik, sollte aber zu schaffen sein, eventuell ist Schwierigkeit 3 sogar übertrieben ;) ) Aufgabenstellung: tratsCH trATsch Die Leute vom Planeten Chator schreiben gern Schlechtes ubereinander. Wer vielen uber andere Schlechtes schreibt, gilt als besonders charmant. Aber natürlich nur, wenn die Kompromittierten nichts davon erfahren. Chatonen schreiben nur an Leute, die Ihnen sympathisch sind. Doch die können den Tratsch weitertragen, und eventuell genau an den Falschen. Ein Chatone muss also gut aufpassen, dass er keinen Charmefehler macht. Dieses Missgeschick passierte unlängst Ator, als er Btor Schlechtes über Dtor schrieb. Zu dumm: Dtor ist dem Ctor sympathisch, der wiederum Btor sympathisch ist. Und so landete der Tratsch bei Dtor, der uber Ator verständlicherweise sehr verärgert war. Dies hätte Ator mit ein wenig Übersicht vermeiden können, denn schließlich wissen alle Chatonen voneinander, wer wem sympathisch ist. Aufgabe: Programmiere einen Charminator, der einliest, welche Chatonen welchen anderen sympathisch sind. Er soll auf dieser Grundlage möglichst kompakt für alle Chatonen ausgeben, wem der Betreffende uber wen Schlechtes schreiben kann, ohne einen Charmefehler zu riskieren. Teste dein Programm an drei Beispielen für mindestens 5 und höchstens 10 Chatonen; verwende auf jeden Fall das folgende Beispiel: Code: Dem Chatonen sind sympathisch: A B E B C C D G D C E F F B E G G H H D Bedenke dabei, dass eine Tratschnachricht von Chatone x nach Chatone y weder x noch y betrifft und dass ein Chatone eine Nachricht, die ursprünglich von ihm selbst stammt und wieder bei ihm ankommt, nicht weiterleiten wird ? so dumm sind Chatonen nicht Lösungsansatz Losungsidee nach Benjamin Berger Die Sympathiebeziehungen der Chatonen werden als ein gerichteter Graph aufgefasst: die Chatonen sind die Knoten, die direkten Sympathiebeziehungen die gerichteten Kanten. Dann wird der Weg einer Nachricht von einem Chatonen S (Sender) an einen dem S sympathischen Chatonen E (Empfänger) für alle möglichen Paare (S,E) wie folgt nachvollzogen: Der Graph wird beginnend bei E rekursiv durchsucht (Tiefensuche), bis entweder S selbst erreicht wird (der die Nachricht nicht weiterleitet) oder ein gefundener Chatone schon besucht wurde, die Nachricht also schon erhalten hat. Über alle Chatonen, die nicht besucht wurden, kann S bei E tratschen ? da E an sie den Tratsch eben nicht weiterleiten kann. __________________ Noch mal, für alle Pseudo-Geeks: 1+1=0. -> 10 wäre Überlauf! Selig, wer nichts zu sagen hat und trotzdem schweigt.

06.06.07, 09:17	#2 (permalink)
J.U.B. Registriert seit: 30.05.07 Likes: 0	Also habe ich das jetzt wie folgt verstanden: man solle ein Programm entwickeln in dem man zusätlich zu den ausgaben wehm wer sympathish ist noch über wehm er lästern kann ausgeben... ungefär so?: Code: Dem Chatonen sind sympatisch: und kann über diese lästern: A B E B C A E F C D G A B E F D C A B E F E F A F B E G A G H A B E F H D A B E F

06.06.07, 13:38	#3 (permalink)
CDW Moderator Themenstarter Registriert seit: 20.07.05 Likes: 202	Wer wem sympatisch ist, soll vom Benutzer eingegeben werden. Das Programm soll dann ermitteln, wem ein bestimmter Chatone über einen anderen eine Lästernachricht schicken kann, ohne dass der Chatone, über den dabei gelästert wird, es mitbekommt. Also: ein Chatone lästert über einen andern. Dabei schickt er seine Lästernachricht an die ihm sympatischen Chatonen. Diese wiederum leiten diese Nachricht an die ihnen sympatischen. Bsp: A lästert über C. Schickt also seine Nachricht an B,E weiter. E schickt diese an F, B dagegen leitet sie an C weiter - Fehler. __________________ Noch mal, für alle Pseudo-Geeks: 1+1=0. -> 10 wäre Überlauf! Selig, wer nichts zu sagen hat und trotzdem schweigt.

16.06.07, 12:43	#8 (permalink)
mauralix Registriert seit: 17.04.06 Likes: 3	Mir gefällt diese Aufgabe. Erinnert mich voll ans echte Leben. In meiner Gemeinde leben wohl viele Chatonen. __________________ http://chm0815.blogspot.com

Themen-Optionen
Druckbare Version zeigen Jemanden per E-Mail auf dieses Thema hinweisen
Ansicht
Linear-Darstellung Zur Hybrid-Darstellung wechseln Zur Baum-Darstellung wechseln

14.06.07, 09:40	#6 (permalink)
J.U.B. Registriert seit: 30.05.07 Likes: 0	@ CDW: Diese Aufgabe hätte ruhig Schwierigkeit: 1 bekommen könne (oder evtl auch 2). @ Ivan: Mach das selbe mal mit benutzereingabe für die sympatischen Chatonen.

14.06.07, 10:32	#7 (permalink)
Ivan Dolvich Registriert seit: 12.01.07 Likes: 0	Die Benutzereingabe habe ich mir jetzt gespart weil das nichts spannendes ist, und von das eigentliche Problem (den Graphen abbilden und durchsuchen) abweicht.

[HaBo]

Charminator