[Python-de] Kleine Aufgabe, große Wirkung

Christian Tismer tismer at tismer.com
Mon Apr 7 02:46:56 EDT 2003


Hi Michael,

> On Sun, 6 Apr 2003, Christian Tismer wrote:
...

>>Die Aufgabe ist eigentlich nicht wirklich schwer und sollte
> 
> gar nicht so leicht zu bestimmen, nicht wahr?

Doch.

>>Also, jetzt geht's los: Gegeben ist ein unsortierter Baum.
> 
> wieviel Sinn macht so ein Baum? Sag es mir bitte einer, denn ich bin kein
> Informatikstudent.

Abgesehen von Martin's Kommentar, der Sinn macht, sage ich
hier, "das ist völlig egal, wenn das Problem so auftritt,
muß man es so lösen". Man muß sich auch von dem Sinn lösen,
es ist eine einfache mathematische Struktur gegeben, und
es gibt eine einfache Lösung.

...

> "zu durchsuchen" bedeutet, dass man Knoten nur aufsuchen soll, wenn man
> vorher schon weiss, ob sie die richtigen sind. Beispielsweise ein Test, ob
> ein Knoten die id 8 hat ist verboten. Für jeden Knoten den man *finden*
> will zuerst alles zu durchsuchen, bis man ihn hat ist verboten. Schon
> *finden* wäre der falsche Ausdruck: es geht darum das Bäumchen mit einem
> Durchlauf in id Reihenfolge zu durchlaufen.

Du sollst den Baum in der angegebenen Reihenfolge durchsuchen,
das heißt, einen Test mit jedem Knoten durchführen. Wenn der
zieht, bist Du fertig. Aber darum ging es nicht. Es ging darum,
das Prinzip zu verstehen, oder sich daran zu erinnern.

...

>>Der Einfachheit halber gebe ich hier einen Test-Baum vor, der
>>trivialerweise die Knotennummern in dieser Reihenfolge
>>enthält. Das ist zwar nicht der generelle Fall, aber für das
>>Beispiel völlig ausreichend.
> 
> davon werde ich keinen Gebrauch machen. Das ist ja eh immer die Frage bei
> solchen Aufgaben: von wievielem darf man als gegeben ausgehen? Z.B: kommen
> die Knoten ids lückenlos oder nicht? Wenn man eine große Menge an
> Eigenschaften des Bäumchens benutzen darf, dann kann man auch mit soetwas
> die Aufgabe lösen:
> 
> for n in range(1,16): print n  # ;-)

Nein, das darf man freilich nicht, denn die Randbedingungen
waren glasklar gestellt: Der Baum ist nicht sortiert.
Die Testdaten waren nur zur Vereinfachung gegeben, damit
man leicht testen kann. Bei Aufgaben dieser Art gilt
zwischen den Einzel-Aussagen immer eine Und-Verknüpfung, man
kann nicht einfach weglassen, was einem nicht gefällt.
Auch das ist ein Teil des Tests. :-)

> Ich bin überzeugt, dass man mit dieser Antwort sofort Abteilungsleiter
> wird ;-)

Na, dann wünsche ich viel Glück.

...

> Lösung A: umschreiben des völlig nutzlosen Bäumchens (upps, dass hab ich
> jetzt in meiner Kenntnisarmut mal so gesagt) in etwas der Aufgabe
> entsprechendes: eine Liste (Speicherbedarf lass ich mal außer Acht).
...

> leveled = make_flat(t, [], 1)
> leveled.sort()
> for e in leveled:
>    print e

Ist nicht! Der Baum ist unsortiert, die Testdaten widersprechen
dem zwar, aber die Struktur ist allein durch die Art des
Enthaltenseins gegeben, das muß man respektieren.

...

>         for node in t:
>             if is_leave(node):
>                 print node
>                 continue
>             for e in node:
>                 back.append(e)
>         t = back

Hab's nicht weiter getestet, aber es sieht aus, als ginge es in die
richtige Richtung.

...

> ich habe "Probleme" mit t ;-) Vielleicht hab ich ja was schrecklich
> einfaches übersehen. Sag es mir dann bitte. Ansonsten geh ich davon aus,
> dass das hier eine Aufgabe aus nem Bewerbungstest war, also den Probanden
> nicht zuletzt durch unlösbare oder nicht vernünftig lösbare Aufgaben unter
> Stress setzen soll.  Weil ich mich als open source Programmierer fühle,
> brauch ich sowas nicht und würde eher t neu implementieren als mir über
> dessen Sortierung den Kopf zu zerbrechen.

Tut mir leid, wenn Du Dich angegriffen fühlst. Mit Open Source
hat das nichts zu tun, ich lebe übrigens von Open Source.
Dieser Baum ist in der Tat nichts dolles, nicht sortiert,
und man soll ihn auf vorgegebene Weise abklappern.
Das Problem ist ganz einfach, unter den gegebenen Vorgaben
optional zu funktionieren. Abstrahiere, finde die Struktur
heraus, stelle fest, was getan werden muß, nämlich eine
Warteschlange bauen für den nächsten Knoten, der dran ist,
dann bastele eine kurze Funktion drum herum.

Hier ging's nicht um "what is it good for", sondern um
Algorithmen, Verständnis, Modellbildung, effiziente
Problemlösung.

Der Test ist gut, werde ihn weiter verwenden.

Viel Glück -- chris
-- 
Christian Tismer             :^)   <mailto:tismer at tismer.com>
Mission Impossible 5oftware  :     Have a break! Take a ride on Python's
Johannes-Niemeyer-Weg 9a     :    *Starship* http://starship.python.net/
14109 Berlin                 :     PGP key -> http://wwwkeys.pgp.net/
work +49 30 89 09 53 34  home +49 30 802 86 56  pager +49 173 24 18 776
PGP 0x57F3BF04       9064 F4E1 D754 C2FF 1619  305B C09C 5A3B 57F3 BF04
      whom do you want to sponsor today?   http://www.stackless.com/






More information about the Python-de mailing list