[HaBo]

package treppen;

import java.util.Vector;

public class Treppensteigen {
	private int stufen;
	private Vector<String> moeglichkeit = new Vector<String>();
	private boolean add;
	
	public Treppensteigen(int stufen) {
		this.stufen = stufen;		
		String buffer = "";
		for(int i=0; i<stufen; i++) {
			buffer+= "1";
		}
		moeglichkeit.addElement(buffer);
		suche(buffer,-1,0);
	}

	private void suche(String buffer,int a, int b) {
		if(a!=-1) {
			// Lösche die 1en an den Stellen a und b
			// und ersetze sie durch eine 2
			if(b!=buffer.length()-1) {
				buffer = buffer.substring(0, a)+"2"+buffer.substring(b+1);
			} else {
				buffer = buffer.substring(0, a)+"2";
			}	
			
			//Vermeiden von doppelten Lösungen
			add = true;
			for(int i=0; i<moeglichkeit.size(); i++) {
				if(buffer.equals(moeglichkeit.elementAt(i))) {
					add = false;
				}
			}
			if(add) {
				moeglichkeit.addElement(buffer);
			}			
		}		
		
		// Suche nach zwei 1ern nebeneinander
		if((stufen % 2 == 0 && buffer.length()>(stufen/2))
				|| (stufen % 2 !=0 && buffer.length()>(stufen/2+1))){
			for(int i=0; i<buffer.length()-1; i++) {
				if(buffer.charAt(i)== '1' && buffer.charAt(i+1)=='1') {
					suche(buffer,i,i+1);
				}
			}
		}	
	}
	
	public void ausgabe() {
		System.out.println("Treppenstufen: "+stufen);
		System.out.println("Möglichkeiten: "+moeglichkeit.size());
		for(int i=0; i<moeglichkeit.size(); i++) {		
			System.out.print(moeglichkeit.elementAt(i));
			if(i!= moeglichkeit.size()-1) {
				System.out.print(" - ");
			}
		}
		System.out.println("\n");
	}
}

package treppen;

public class TreppenTest {
	public static void main(String[] args) {
		Treppensteigen vier = new Treppensteigen(4);
		vier.ausgabe();
		
		Treppensteigen fuenf = new Treppensteigen(5);
		fuenf.ausgabe();
	}
}

#include <iostream>

using namespace std;

int main()
{
	int i = 0, co = 0, num, l = 0;
	cout << "Treppenstufen: " << flush;
	cin >> num;

	char *c = new char [num];
	c[0] = 0;
	i = 0;
	for (;;) {
		if (c[i] <= 1 && co < num) {
			++c[i];
			++co;
			++i;
			c[i] = 0;
			if (co == num) {
				if (l != 0)
					cout << " - ";
				for (int j = 0; j < i; ++j)
					cout << (unsigned int) c[j];
				++l;
			}
		} else {
			co -= c[i];
			--i;
			if (i < 0)
				break;
		}
	}
	delete [] c;
	cout << "\nMoeglichkeiten: " << l << endl;
	return 0;
}

def stufen(stufen):
	a=0
	b=1
	i=0
	
	while i < stufen:
		c=a+b
		a=b
		b=c
		i=i+1
	return b
	
print 'Ergebnis: ', stufen(input('Anzal der Stufen? '))

#!/usr/bin/perl -w

use strict;
use warnings;

my $gesamt;

sub stufen {
  my $l = shift;
  my $c = shift;

  if($l < 1) {
    return;
  } else {
    if ($l == 1) {
      print $c . '1' . "\n";
      $gesamt++;
    } else {
      if ($l == 2) {
        stufen ($l - 1, $c . '1-');
        print $c . '2' . "\n";
        $gesamt++;
      } else {
        stufen ($l - 1, $c . '1-');
        stufen ($l - 2, $c . '2-');
      }
    }
  }
}

print "Bitte ganze Zahl fuer Anzhal Schritte eingeben:\n";
chomp(my $a = <STDIN>);
print "--------\n\n";

stufen($a, '');
print "\nGesamt:$gesamt\n";

#!/usr/bin/env perl
use warnings;
use strict;

our $STEPMAXIMUM = 2;

my $stufenCount;
if (@ARGV) {$stufenCount = $ARGV[0]}
else {chomp($stufenCount = <>)}

sub treppenKnecht {
    my ($cur, $sol, $pos, $max) = @_;
    if ($pos == $max) {push(@$sol, join('', @$cur)); return 1}
    if ($pos > $max) {return 0}
    for my $step (1..$STEPMAXIMUM) {
        if (treppenKnecht([@$cur, $step], $sol, $pos+$step, $max)) {return 0}
    }
}

my @solutions;
treppenKnecht([], \@solutions, 0, $stufenCount);

foreach (@solutions) {print "$_\n"}

schritt(1).  %es gibt zwei Arten von Schritten.
schritt(2).
%Problem des Treppensteigens ist gelöst
%sofern man alle Stufen überwunden hat (wer hätte es gedacht ;) )
loesung(Stufen_gesamt,Zurueckgelegt):-
	Stufen_gesamt =:= Zurueckgelegt.
%sonst:
loesung(Stufen_gesamt,Zurueckgelegt):-
	Stufen_gesamt>Zurueckgelegt,  %hat man noch nicht alle Stufen zurückgelegt,
	schritt(Schrittweite),  %gibt es einen Schritt, der uns vielleicht 
	loesung(Stufen_gesamt,Zurueckgelegt+Schrittweite), %in Lösungsnähe bringt	
	write(Schrittweite),write(' '). %wenn es so war, 
        %sollte man den Schritt ausgeben

%gehört nicht mehr zur Lösung, sondern dient eher bequemeren Ausgabe
loesungen(Stufen_gesamt, Anzahl):-
	findall(X,(loesung(Stufen_gesamt,0),nl),Ergebnis),
	length(Ergebnis,Anzahl).

schritt(1). 
schritt(2).

loesung(St,Zu):- St is Zu.

loesung(St,Zu):- St>Zu, 	
       schritt(Sw),loesung(St,Zu+Sw),write(Sw),write(' ').

loesungen(Stufen_gesamt, Anzahl):-
	findall(X,(loesung(Stufen_gesamt,0),nl),Ergebnis),
	length(Ergebnis,Anzahl).

?- loesungen(5,Anzahl).
1 1 1 1 1 
2 1 1 1 
1 2 1 1 
1 1 2 1 
2 2 1 
1 1 1 2 
2 1 2 
1 2 2 
Anzahl = 8.

?- loesungen(4,Anzahl).
1 1 1 1 
2 1 1 
1 2 1 
1 1 2 
2 2 
Anzahl = 5.

program Project1;

{$APPTYPE CONSOLE}

uses
  SysUtils;

var global_stufen : integer;
    global_string : string;
    Stufen : Integer;

procedure Stufe(iZähler : Integer; Str : String);
  begin
    if iZähler >=2 then
    begin
       Stufe(iZähler-1, Str+ '1');
       Stufe(iZähler-2, Str+ '2');
    end else
      if iZähler = 1 then
      Stufe(iZähler-1, Str+ '1')
      else begin
       inc(global_stufen);
       global_string := global_string + Str + ' | ';
      end;
  end;

begin
  global_stufen := 0;
  writeln('Bitte Anzahl der Stufen eingeben:');
  readln(Stufen);
  Stufe(Stufen, '');
   writeln(global_string);
   writeln('Anzahl der Moeglichkeiten:');
   writeln(global_stufen);
   readln;
end.
end.