Zur Themenübersicht     

Das Treppenproblem

Es gibt eine Treppe mit einer Anzahl von n Stufen. Man kann diese Treppe hochsteigen, indem man entweder Einzelschritte ( 1 Stufe ) oder Doppelschritte ( 2 Stufen ) macht. Wie viele verschiedene Möglichkeiten gibt es nun die Treppe hoch zu laufen ?

Konkrete Lösung am Beispiel von 4 Stufen:

(Die Zahlen bedeuten die Anzahl der Stufen)

1.Möglichkeit: 1,1,1,1
2.Möglichkeit: 1,2,1
3.Möglichkeit: 2,1,1

4.Möglichkeit: 1,1,2
5.Möglichkeit: 2,2

Man erkennt am obigen Beispiel, dass es zwei Arten von Möglichkeiten gibt. In den ersten drei Fällen ist der letzte Schritt ein Einzelschritt; bei den letzten beiden ein Doppelschritt. Lässt man nun jeweils den letzten Schritt weg, so sind die ersten drei Möglichkeiten die möglichen Schrittfolgen, wenn man vorher drei Stufen erklommen hat, und die letzten beiden Möglichkeiten die möglichen Schrittfolgen, wenn man vorher zwei Stufen erklimmt. Aus diesen Überlegungen am konkreten Beispiel ergibt sich nun folgende allgemeine Lösung.

Allgemeine Lösung:

Will man eine Treppe mit n Stufen in 1er- oder 2er- Schritten hochlaufen, so muss man die Summe der Möglichkeiten bei n-1 Stufen und n-2 Stufen bilden. Es ergibt sich folgende Gleichung:

Möglichkeiten (n) := Möglichkeiten (n-1) + Möglichkeiten (n-2)

Stufenanzahl	Möglichkeiten
1	1
2	2
3	3
4	5
5	8
6	13

Die so entstehende Zahlenfolge 1,2,3,5,8,13.... wird auch Fibonacci-Folge genannt und wurde 1202 von Leonardo da Pisa im Zusammenhang mit einer Frage nach der Vermehrung ewig lebender Kaninchen erstmalig untersucht.

Programmumsetzung in Delphi 2.0 als rekursive Funktion

Funktionsdeklaration der Funktion moeglichkeiten



Anhand einer case ... of - Schleife werden 


die Möglichkeiten für eine  ==>
und für zwei Stufen          ==>
festgelegt, aus denen sich später alle anderen 
Möglichkeiten mit Hilfe der oben erstelleten Formel 
berechnen lassen. Dies passiert nur im  else
- Fall, wenn der Benutzer nicht für die Anzahl der
Stufen 1 oder 2 eingibt, da die Möglichkeiten für
diese Fälle bereits oben deklariert sind.  

function TForm1.moeglichkeiten 
        (Stufen:Integer) : Integer;
begin
  case Stufen of 
      

       1 : moeglichkeiten := 1;
       2 : moeglichkeiten := 2;


  else  moeglichkeiten := moeglichkeiten(Stufen-1)
                      + moeglichkeiten (Stufen -2)
   end;
end;

Prozedurdeklaration der Prozedur BtBerechneClick
Es wird zunächst eine Variable AnzahlT festgelegt,



unter der später die vom Benutzer eingegebene Stufenanzahl
gespeichert wird.
Das Ergebnis wird im zweiten Edit-Feld (EdErg) ausgegeben,
nachdem es indem die Funktion moeglichkeiten auf-
gerufen wird, die ihrerseits das Ergebnis liefert.

procedure TForm1.BtBerechneClick(Sender: TObject);
var AnzahlT: Integer;      


begin
   AnzahlT := StrToInt (EdStufen.Text);
  

 EdErg.text := IntToStr (moeglichkeiten(AnzahlT));     
end;

Zur Themenübersicht
Zum Seitenanfang
Zur vorigen Seite	Zur nächsten Seite

	© 2000 LK 12 If und G. Kubitz  •  Hannah-Arendt-Gymnasium, Lengerich