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

Michael Janssen Janssen at rz.uni-frankfurt.de
Sun Apr 6 20:27:11 EDT 2003


On Sun, 6 Apr 2003, Christian Tismer wrote:

> Liebe Python-de Liste,

Auch meinerseits, hallo Python-de,

> nicht ganz trivialen Aufgabe getestet und sind zu einem bestürzenden
....
> Die Aufgabe ist eigentlich nicht wirklich schwer und sollte

gar nicht so leicht zu bestimmen, nicht wahr?

> 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.

> Den sollt Ihr "breadth-first" durchsuchen, linear, also es ist
> gar kein Such-Problem, einfach nur eine Frage der richtigen
> Reihenfolge. Die Knoten des Baums sehen beispielsweise so aus:
>
>              1
>      2               3
>   4      5       6       7
> 8 9   10 11   12 13   14 15
>
> Was man tun soll, ist, diese Knoten in der durch die Zahlen
> angegebenen Reihenfolge zu durchsuchen. Der Vorschlag ist,

"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.

> eine Testfunktion zu übergeben, welche versucht, den richtigen
> Knoten zurückzugeben. Ich empfehle, ein print-Statement

hört sich für mich nach einer verbotenen Strategie an.... Ich stelle mir
grad vor mein Dateisystem würde so arbeiten.

> einzubauen, welches verifiziert, daß Ihr wirklich in der
> vorgegebenen Reihenfolge sucht.
>
> 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  # ;-)

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

>
> Hier der Beispiel-Baum: [value, child1, child2]
>
> t = [1,
>       [2,
>        [4,
>         [8, None, None],
>         [9, None, None]],
>        [5,
>         [10, None, None],
>         [11, None, None]]],
>       [3,
>        [6,
>         [12, None, None],
>         [13, None, None]],
>        [7,
>         [14, None, None],
>         [15, None, None]]]]

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).

def is_leave(node):
    for e in node:
        if type(e) == type(t):
            break
    else: # we havn't breaked out --> no sublist (subnode) found
        return 1
    return 0 # we havn't "else-returned out"

def make_flat(tree, back, only_leaves=0):
    if not only_leaves:
        back.append(tree)
    if is_leave(tree):
        if only_leaves:
            back.append(tree)
        # since we are recursive in a "for node in tree" loop, we needn't
	# care for the "other leave/ node".
        return back
    for node in tree[1:]:
        make_flat(node, back,only_leaves)
    return back

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


lösung B: Before man eine node betritt, überprüfen ob es die Richtige ist.
Test auf Richtigkeit per min() und type(elem) == type(0)

"Betreten der node" ist hier: den nodeinhalt in die top-level-liste von t
zu stellen (aha, eigentlich schon wieder make_flat):

def step_through(t):
    # while-loop trough levels of t
    while t:
        # loop to remove each node_id
        while 1:
            # catch case, when remove has emptied t
            try: m = min(t)
            except: break
            if type(m) == type(0):
                # now we got a minimal thing and this thing is a node_id
                t.remove(m)
            else:
                # the minor thing was a list
                break
        # step a level deeper: place each list-item into t-toplevel
        back = []
        for node in t:
            if is_leave(node):
                print node
                continue
            for e in node:
                back.append(e)
        t = back

step_through(t)

> Jetzt bin ich wirklich gespannt, ob die Deutsche
> Informatik-Grundausbildung effektiver ist als die Amerikanische.

Dann sagt mir mal, ob es effektiver geht :-) Ich frage mich, ob man mit
einem raffinierten Algorithmus quasi einen iterator für t schreiben kann?

Oder: wie würden Dateisysteme ihre Trees organisieren, damit effizient
gesucht werden kann?

> Sollten sich genügend viele finden, die mit dieser Aufgabe
> substantielle Probleme haben, schlage ich hingegen folgendes

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.

Michael






More information about the Python-de mailing list