binäre Zahlenfolge

Neue Frage »

hilflos09 Auf diesen Beitrag antworten »
binäre Zahlenfolge
Hallo,

ich bräuchte dringend Eure Hilfe bei einer Übungsaufgabe:

Sei an die Anzahl der binären Zeichenfolgen der Länge n, die keine zwei aufeinanderfolgenden Nullen enthalten.
Zeigen Sie, dass an= an-1 + an-2 für n größer gleich 3 und ermitteln Sie daraus einen Ausdruck für an.

Es wäre toll, wenn Ihr mir auf die Sprünge helft.

Danke.
Abakus Auf diesen Beitrag antworten »
RE: binäre Zahlenfolge
Hallo!

Was sind deine Überlegungen dazu? Hast du dir das Ganze als Beispiel mal angeschaut?

Grüße Abakus smile
hilflos09 Auf diesen Beitrag antworten »
Fibonacci???
Generell sieht die Folge ähnlich der Fibonacci-Folge aus, falls ao=0 und a1=1, mit a1=1 und a2=1 beginnend oder falls die Startwerte 1 und 0 sind, dann 0 als a0 setzend. Dann wäre der Ausdruck klar.

Mein Frage ist nun bringt mir dies in Bezug auf die binäre Zahlenfolge etwas???
Abakus Auf diesen Beitrag antworten »
RE: Fibonacci???
Zitat:
Original von hilflos09
Generell sieht die Folge ähnlich der Fibonacci-Folge aus, falls ao=0 und a1=1, mit a1=1 und a2=1 beginnend oder falls die Startwerte 1 und 0 sind, dann 0 als a0 setzend. Dann wäre der Ausdruck klar.

Mein Frage ist nun bringt mir dies in Bezug auf die binäre Zahlenfolge etwas???


Du sollst ja als erstes die Rekursion oben beweisen. Wähle dazu geeignete Bezeichnungen und überlege dann, was gilt:

= Anzahl der Zahlenfolgen der Länge n mit 0 als (n-1)-ster Zahl

= Anzahl der Zahlenfolgen der Länge n mit 1 als (n-1)-ster Zahl

Damit müsstest du schon weiterkommen. Die ersten Folgenglieder sind dann noch zu ermitteln.

Wenn du das hast, ist die (lineare) Rekursion noch in eine explizite Formel umzuwandeln.

Grüße Abakus smile
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »