Rekursive folge (aus gödel escher bach) hilfeeee!

Wissenschaft Physik
#1

ich lese grade das wundervolle buch „gödel escher bach“ von d. hofstadter.
bisher konnte ich ja noch alles nach mehr oder weniger langem grübeln verstehen, aber jetzt … :[

also:

es geht um einen rekursiven baum G:

nicht erweitert:
 G
 |
 G o
 |--o--|
 |


einmal erweitert:


 G 
 |
 G G o
 | |-o-|
G o |
|-o-| o
 |---o---|
 |

wenn man den nun durchnummeriert, jeweils von links nach rechts erhält man im rechten ast fibonacci ab n=4, schön aber egal.

dann weiter: (S.148 9.auflage)

"(blabla) nun hat diagramm G sogar noch überraschendere eigenschaften.seine gesamte struktur kann in einer einzigen rekursiven definition codiert werden, und zwar:

G(n)=n-G(G(n-1)) für n\>1
G(0)=0

[wenn ich richtig gerechnet habe gibt das die reihe: 0,1,1,2,3,3,4,4,5,6,6,7,8,8,9,9,10,11,11,12,12,13,14,14,15,16…]

wie lässt sich diese funktion G(n) als baumstruktur codieren? GANZ EINFACH, [haha, der setzer] wenn man einen baum konstruiert, indem man G(n) für alle werte von n unter n setzt, wird man das diagramm G neu schaffen."

bidde wie? was will er mir sagen?? „indem man G(n) für alle werte von n unter n setzt“ hä??

hilfe!!

danke schonmal :o)

#2

Die Sache mit der Vermehrung und den Bienen
Hallo,
ich versteh Deine Frage nicht ganz, drum besteht die Gefahr, dass ich daran vorbeirede.
Ein lebensnahes Beispiel zur Interpretation des Ganzen kann ich Dir aber liefern.
Interpretiere G einfach als Stammbaum einer Bienenkönigin.

Dazu kurz zwei Fakten:

  • eine Bienenkönigin ist einem befruchteten Ei entschlüpft und hat damit einen Vater (eine Drohne) und eine Mutter (die Königin)
  • eine Drohne hinwiederum stammt aus einem unbefruchteten Ei, hat also nur eine Königin zur Mutter und keinen Vater.

Wenn wir nun die Symbole in Deinen Skizzen wie folgt interpretieren
o ist eine Biene (Drohne oder Königin)
G ist der Stammbaum einer Königin,

dann besteht der Stammbaum einer Königin (G) aus
a) einem o für sie selbst
b) einer „Mutterlinie“
c) einer „Vaterlinie“

Die Mutterlinie ist wieder der Stammbaum einer Königin (G)
Die Vaterlinie besteht aus dem Vater (o) und dessen Vorfahren, die, da er selbst keinen Vater, aber eine Königin zur Mutter hat, wieder der Stammbaum einer Königin (G) sind.
Das ergibt Deine erste Skizze.

Nun kannst Du Dich daran machen, die beiden G in dieser Skizze durch a) b) c) zu ersetzen, dann erhältst Du die zweite Skizze, u.s.w.

Die Zahl der Bienen pro Generation (waagerecht die „o“ aufsummiert) ergibt die Fibonaccizahlen.

Ich hoffe, das hilft Dir ein bisschen, falls nicht, dann frag nach.
Viel Spaß noch mit GEB
Barbara

#3

danke, das ist mir schon klar. nochmal die frage:
ja irgendwie kommt nicht so ganz raus was ich überhaupt will … sorry.

also soweit ist mir das auch alles klar gewesen (trotzdem danke für das schöne bienenbeispiel)

G(n)=n-G(G(n-1)) für n>1
G(0)=0

[wenn ich richtig gerechnet habe gibt das die reihe:
0,1,1,2,3,3,4,4,5,6,6,7,8,8,9,9,10,11,11,12,12,13,14,14,15,16…:]

das ist mein problem! wie baut sich aus dieser rekursiven formel (und nur daraus) der obige baum auf. ich stehe da mit meiner reihe die ich bis n=ziemlich-viel-und-hat-auch-ne-zeit-gedauert ausgerechnet hab, aber ich kommm net dahinter wie ich damit den baum aufbauen soll!?!?

ich habe alles was dazu im buch steht zitiert. mehr gibts dazu nicht her:

„wie lässt sich diese funktion G(n) als baumstruktur codieren?
GANZ EINFACH, [haha, der setzer] wenn man einen baum
konstruiert, indem man G(n) für alle werte von n unter n setzt,
wird man das diagramm G neu schaffen.“