{"id":2583,"date":"2009-10-24T11:31:50","date_gmt":"2009-10-24T09:31:50","guid":{"rendered":"https:\/\/www.herr-rau.de\/wordpress\/?p=2583"},"modified":"2023-05-24T15:45:19","modified_gmt":"2023-05-24T13:45:19","slug":"einfach-verkettete-liste-rekursion-und-entdeckungen-bei-powerpoint","status":"publish","type":"post","link":"https:\/\/www.herr-rau.de\/wordpress\/2009\/10\/einfach-verkettete-liste-rekursion-und-entdeckungen-bei-powerpoint.htm","title":{"rendered":"Einfach verkettete Liste, Rekursion und Entdeckungen bei Powerpoint"},"content":{"rendered":"
(8 Kommentare.<\/a>)<\/small> <\/div>\n

Gestern habe ich in Informatik die erste rekursive Methode<\/strong> eingef\u00fchrt: die L\u00e4nge einer Liste bestimmen. Hm, ja. Dann muss ich wohl zuerst erkl\u00e4ren, was eine Liste ist. Das wird jetzt etwas technisch. wer durchh\u00e4lt, wird mit Videos belohnt.<\/p>\n\n\n\n

1. Die Liste <\/h2>\n\n\n\n

Eine beliebig lange Liste von Objekten, zum Beispiel W\u00f6rtern, oder Sch\u00fclern, oder Gegenst\u00e4nden im Computerspiel, kann man mit einer einfach verketteten Liste<\/strong> darstellen. Einfach verkettet hei\u00dft, dass sich einfach jedes Element seinen unmittelbaren Nachfolger merkt. Das sieht dann so aus:<\/p>\n\n\n\n

\"liste1\"<\/figure>\n\n\n\n

Die Liste ist hier dargestellt als waagrechte Schnur mit Knoten daran, und an jedem Knoten baumelt – wie bei einem Adventskalender – ein S\u00e4ckchen mit dem von dem Knoten verwalteten Element – Wort, Sch\u00fcler, Patient, Gegenstand, was man halt alles auflistet. Und jeder Knoten merkt sich seinen Nachfolger; er hat quasi einen Zeiger hat, der auf den Nachfolger verweist. Eine Ausnahme ist nur der Zeiger des letzten Knotens; der verweist ins Leere, informatisch null<\/em> genannt.<\/p>\n\n\n\n

Das mit den Knoten und dem Baumeln geschieht deshalb, weil es einem Wort, Sch\u00fcler, Patient, Gegenstand ja egal sein sollte, wer sein Nachfolger ist; mit diesen Verwaltungsaufgaben ist der dazu geh\u00f6rende Knoten besch\u00e4ftigt. Diese Verwaltungsaufgaben werden sp\u00e4ter immer mehr, wenn es darum geht, die Liste zum Beispiel alphabetisch zu sortieren, oder Elemente daraus zu l\u00f6schen oder welche hinzuzuf\u00fcgen. Das machen dann die Knoten unter sich aus, welche Elemente unter ihnen baumeln, ist weitgehend egal.<\/p>\n\n\n\n

Mit einer kleinen Geschichte gesagt:<\/p>\n\n\n\n

\n

Im Reich der Sch\u00e4tze und Dschinn<\/p>\n\n\n\n

Harun ar-Raschid, Kalif von Baghdad, der herrlichsten Stadt des Landes und aller anderen L\u00e4nder unter der Sonne, hatte viele Frauen, viele Pal\u00e4ste, viele Sch\u00e4tze. Eifers\u00fcchtig h\u00fctete er seinen Besitz und war stets voller Misstrauen, deshalb verf\u00fcgte er, dass jedes St\u00fcck durch einen Dschinn, einen Geist, bewacht werden sollte.<\/p>\n\n\n\n

Jeder Dschinn erhielt eine Kiste f\u00fcr das Gut, das er bewachen konnte. So konnte es dem Dschinn egal sein, was er bewachte, Hauptsache, es passte in die Kiste.<\/p>\n\n\n\n

Nun hatte Harun so viel Besitzt\u00fcmer, dass er sie nicht z\u00e4hlen konnte, so viele, dass er ihre Namen nicht wusste, so viele, dass er sie nicht zu finden wusste, wenn es ihm nach einem besonderen Kleinod verlangte.<\/p>\n\n\n\n

Deshalb verf\u00fcgte er, dass sich in Zukunft Verwalter um die F\u00fclle seines Besitzes k\u00fcmmern sollten. Den ersten unter ihnen, Jaffar, ernannte er zum Herren \u00fcber die Sch\u00e4tze, also Juwelen und Perlen und Ringe und anderes Geschmeide.
Jaffar erhielt eine magische Lampe, in der ein Dschinn wohnte, der einen Schatz bewachte. Und dieser Dschinn hatte ebenfalls eine Lampe, und in dieser hauste ein weiterer Dschinn mit seinem Schatz, und auch der hatte wieder eine Lampe mit einem Dschinn darin.
Nur der letzte Dschinn, der bewachte zwar auch noch einen Schatz, er hatte auch eine Lampe, aber diese Lampe war leer und kein weiterer Dschinn wohnte darin.<\/p>\n<\/blockquote>\n\n\n\n

Das sieht dann zum Beispiel so aus:<\/p>\n\n\n\n

\"liste\"<\/figure>\n\n\n\n

Diese Liste verwaltet zwei Elemente (Perlen und Gold). Jeder Dschinn kennt genau einen Nachfolger, bis auf den letzten in der Liste. Jeder Dschinn ist ein Knoten der Liste.<\/p>\n\n\n\n

Ich f\u00fcrchte, dieser Schnelldurchgang muss vorerst reichen. Ich k\u00f6nnte das ausf\u00fchrlicher erkl\u00e4ren, und bei Sch\u00fclern geschieht das ja auch langsamer und mit st\u00e4ndiger Umsetzung in Java. Aber das ist ja ein Blog und kein Fernkurs Informatik.<\/p>\n\n\n\n

2. Eine Methode, um die L\u00e4nge zu bestimmen<\/h2>\n\n\n\n

Also: Die Liste soll eine Methode haben, herauszufinden, wie lange sie ist. Da gibt es grunds\u00e4tzlich zwei M\u00f6glichkeiten. Die eine kennen die Sch\u00fcler schon und manche k\u00f6nnen sie bereits progammieren. Das ist die, auf die man – nach ersten Programmiererfahrungen – am ehesten kommt. Diese Methode hei\u00dft iterativ<\/strong> und sieht so aus, dass die Liste – Jaffar – einfach die ganze Reihe abgeht und mitz\u00e4hlt, und das solange, bis die Liste leer ist. Kennzeichen daf\u00fcr ist eine while-Schleife und die Tatsache, dass ein Objekt – Jaffar – die ganze Rechenarbeit \u00fcbernimmt. Man kann es sich so vorstellen, dass man mit dem Zeigefinger die Elemente der Liste durchgeht und bei jedem Knoten den Z\u00e4hler um eins erh\u00f6ht. Ist man beim letzten Knoten angekommen, hat man die Anzahl ausgerechnet.<\/p>\n\n\n\n

(Wenn man das mit einer Reihe von Sch\u00fclern vorne im Klassenzimmer macht, wird das Prinzip klar.)<\/p>\n\n\n\n

Die andere M\u00f6glichkeit ist die rekursive<\/strong> Programmierung. Die ist elegant, und wenn man sie einmal begriffen hat, auch einfach. Aber auf dem Papier l\u00e4sst sie sicher schwer erkl\u00e4ren. Auch hier wieder nur ganz kurz: es gibt keine while-Schleife. Daf\u00fcr wird die Aufgabe auf mehrere Schultern verteilt. Jeder Dschinn l\u00e4sst seinen Nachfolger einen Teil der Arbeit machen. Wenn man den ersten Dschinn fragt, wie lang die Liste ist, sagt der: „Warte mal, ich frage meinen Nachfolger, wie lange die Liste ab ihm ist“. Und wenn der dann antwortet, z\u00e4hlt der erste Dschinn eins dazu, und das ist dann die L\u00e4nge der Liste.<\/p>\n\n\n\n

Wie kriegt der zweite Dschinn heraus, wieviele hinter ihm stehen? Genau so wie der erste: er fragt wiederum seinen<\/em> Nachfolger, wartet auf die Antwort, und z\u00e4hlt 1 dazu – das ist dann seine<\/em> Antwort. Und das macht jeder Dschinn so, bis auf den letzten, der muss niemanden fragen, der sagt einfach: 1. (Auf die Frage des Vorhergehenden.)<\/p>\n\n\n\n

Um das zu illustrieren, sollten sich neun Sch\u00fcler in einer Reihe aufstellen. Jeder bekam den gleichen Zettel in die Hand:<\/p>\n\n\n\n

Das wird ein Experiment. Bitte lesen Sie die Anweisungen genau.
Wenn Ihnen jemand eine Frage stellt, verhalten Sie sich folgenderma\u00dfen:
Fall a) Wenn Sie nicht der letzte in der Reihe sind, also ihr Nachfolger nicht null ist:
1.Stellen Sie bitte die w\u00f6rtlich gleiche Frage an ihren Nachfolger.
2.Warten Sie mit gespanntem Gesichtsausdruck auf seine Antwort. (Schauen Sie ihn dabei an.) Das kann eine Weile dauern.
3.Sobald die Antwort kommt, addieren Sie im Kopf 1 dazu. Teilen Sie diese Antwort laut dem mit, der Ihnen die urspr\u00fcngliche Frage gestellt hat.
Fall b) Wenn Sie der letzte sind, also ihr Nachfolger null ist: Antworten Sie laut: Eins.<\/p>\n\n\n\n

Dazu muss man sagen, dass die Sch\u00fcler zu diesem Zeitpunkt mit den angesprochen Konzepten bereits vertraut sein sollten. „Nachfolger“, „null“, das sind bekannte Fachausdr\u00fccke.<\/p>\n\n\n\n

Wenn die Sch\u00fcler sich an diese Regeln halten k\u00f6nnen, sieht das ganz eindrucksvoll aus. (Sie k\u00f6nnen es leider nicht immer. Lesekompetenz und so.) Wenn man einen Sch\u00fcler fragt: „Wie lange ist die Liste noch?“, dann schaut der seinen Nachbarn an und stellt ihm die gleiche Frage. (Und wartet auf Antwort.) Der Nachbar schaut seinen Nachbarn an und stellt ihm die gleiche Frage. (Und wartet auf Antwort.) Und der fragt seinen Nachfolger, und so weiter, bis zum letzten Sch\u00fcler. Der sagt laut „eins“, vorauf der vorletzte „zwei“ sagt. Und der vor ihm „drei“. Und so weiter bis zum ersten, der „neun“ sagt, wenn die Liste neun Elemente enth\u00e4lt.<\/p>\n\n\n\n

Wenn man es sieht, kapiert man’s.<\/p>\n\n\n\n

Eigentlich wollte ich das durch folgende Pr\u00e4sentation erg\u00e4nzen, aber leider hat der Beamer gestreikt. Hier kurz als Video:<\/p>\n\n\n\n

3. Powerpoint-Basteleien<\/h2>\n\n\n\n

Erzeugt habe ich den Film mit der Demoversion von E.M. PowerPoint Video Converter<\/a>. Der macht Videos aus Powerpoint-Dateien. Leider tats\u00e4chlich nur aus diesen, nicht aus Impress. (In der Demoversion ist die Auswahl an Videoformaten beschr\u00e4nkt.) Man kann das Programm als Video Capture nutzen, dann nimmt es in der Geschwindigkeit auf, in der man jeweils arbeitet. Das ist praktisch, wenn man in Echtzeit Ton dazu sprechen m\u00f6chte; auch das erm\u00f6glicht das Programm. Will man keinen Ton, geht es noch einfacher, weil automatisiert: Dann gibt man einfach an, wieviel Sekunden zwischen zwei Folien und wieviel zwischen den einzelnen Animationen vergehen sollen, und den Rest macht das Programm allein. Vielleicht machen das neue PP-Version schon selber; ich arbeite mit Impress und habe nur ein recht altes PP herumliegen.<\/p>\n\n\n\n

Wo ich gerade bei Powerpoint bin, will ich auf ein richtig cooles Makro daf\u00fcr hinweisen: The Magic PowerPoint Macro<\/a>. Leider auch wieder nicht f\u00fcr Impress. Damit kann man das machen, was man eigentlich mit jedem vern\u00fcnftigen Pr\u00e4sentationsprogramm machen k\u00f6nnen sollte, und zwar: die Objekte auf der Pr\u00e4sentationsoberfl\u00e4che per drag & drop verschieben<\/strong>. W\u00e4hrend der Pr\u00e4sentation nat\u00fcrlich. Das sieht dann so aus:<\/p>\n\n\n\n

Gibt es Pr\u00e4sentationsprogramm, mit dem ich das ohne Makro machen kann? W\u00e4hrend der Vorf\u00fchrung anklicken und bewegen, und vergr\u00f6\u00dfern und drehen und so weiter. Prezi.com<\/a> ist mir da schon mehrfach empfohlen worden. Ich glaube, ich sollte mich mal ernsthaft damit besch\u00e4ftigen – allerdings verwende ich eh nicht viele Pr\u00e4sentationen.<\/p>\n","protected":false},"excerpt":{"rendered":"

(8 Kommentare.) Gestern habe ich in Informatik die erste rekursive Methode eingef\u00fchrt: die L\u00e4nge einer Liste bestimmen. Hm, ja. Dann muss ich wohl zuerst erkl\u00e4ren, was eine Liste ist. Das wird jetzt etwas technisch. wer durchh\u00e4lt, wird mit Videos belohnt. 1. Die Liste Eine beliebig lange Liste von Objekten, zum Beispiel W\u00f6rtern, oder Sch\u00fclern, oder […]<\/p>\n","protected":false},"author":2,"featured_media":2584,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[25],"tags":[227,116,74],"class_list":["post-2583","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-informatik","tag-informatik","tag-praesentieren","tag-software"],"_links":{"self":[{"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/posts\/2583","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/comments?post=2583"}],"version-history":[{"count":3,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/posts\/2583\/revisions"}],"predecessor-version":[{"id":57960,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/posts\/2583\/revisions\/57960"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/media\/2584"}],"wp:attachment":[{"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/media?parent=2583"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/categories?post=2583"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/tags?post=2583"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}