0 Daumen
377 Aufrufe

Vollständige Induktion: Anzahl Wörter der Länge höchstens n über dem Alphabet {0,1}

xx.PNG

ich muss diese Aufgabe mit Vollständige Induktion lösen die Idee dass ich in IS geometrische summenformel verwende aber komme nicht mehr weiter.

von

2 Antworten

0 Daumen

Hallo, fang mit n=2 an, wieviele Worte gibt es mit <=n Buchstaben. 7

Wenn man jetzt von 2 nach 3 geht, wieviele neue kommen dazu? kannst du das aus der Anzahl 7 bei 2 herausfinden, ohne alle aufzuschreiben? auf dieselbe Weise kommst du von n nach n+1

Alle alten bleiben, denn es sind ja alle mit weniger als  3 dabei, Nur neue mit 3 kommen dazu, die stellt man aus den 2 Buchstaben ( bzw n buchstabiegen her) wieviele? das addiere.

Bei der Induktion musst du doch nur benutzen, wieviele  neue Worte du durch zufügen einer 1 und durch zufügen einer 0 machen kannst.

Gruß lul

von
0 Daumen

Du kannst dieses Problem auf einen vollständigen binären Baum der Höhe n zurückführen. Dort wird jedem Wort ein Knoten zugewiesen. Zeige nun durch vollständige Induktion, dass dieser Baum genau 2^{n+1}-1 Knoten hat. Hier mal eine Skizze als Unterstützung:

Bildschirmfoto von 2019-08-26 01-52-09.png

Im Induktionsschritt betrachtest du nun so einen Baum (nach Induktionsvoraussetzung ist die Knotenanzahl ja schon bekannt) und packst zu diesem Baum noch eine Schicht unten dran, sodass du wieder einen vollständigen binären Baum nun mit Höhe n+1 hast.

von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...