Treppensteigen

Hi,
ich hab wieder mal eine Programmieraufgabe für euch (angelehnt an ein 'Hackit'):

Und zwar sollt ihr ein Programm schreiben das ausrechnet wie viele Möglichkeiten es gibt
eine x Stufen lange Treppe zu ersteigen wenn man zwischen 2 und 1 Stufen pro 'Tritt'
wählen kann.

Die Anzahl der Stufen soll vom User kommen,das Programm soll die Möglichkeiten und
deren Anzahl ausgeben.

Mögliches Output:

Treppenstufen: 4
...
Möglichkeiten: 5
1 1 1 1 - 1 1 2 - 1 2 1 - 2 1 1 - 2 2


Happy Coding,
Xalon
 
Die Klasse Treppensteigen:
Code:
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");
	}
}
Die Klasse TreppenTest:
Code:
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();
	}
}
Müsste einwandfrei Funktionieren. Ein Beispiel für die Ausgabe bei 6 Treppenstufen:

Code:
Treppenstufen: 6
Möglichkeiten: 13
111111 - 21111 - 2211 - 222 - 2121 - 2112 - 12111 - 1221 - 1212 - 11211 - 1122 - 11121 - 11112

Gruß, Boar
 
es kommt die Reihe der fibonaccizahlen raus...nur falls jumd ma überprüfen will, ob sein prog auch für größere treppen läuft...
 
Original von Cube
es kommt die Reihe der fibonaccizahlen raus...nur falls jumd ma überprüfen will, ob sein prog auch für größere treppen läuft...
Cool, hat ein bisschen gedauert bis ich verstanden hab was du meinst.

Habs jetzt auch mit 10 Stufen (89 Möglichkeiten) und 15 Stufen (987 Möglichkeiten) getestet. Bei 15 Stufen rechnet er aber schon ne ganze weile.
 
Meine Lösung in C++
Code:
#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;
}
Also bei 15 Stufen geht es noch fast ohne Verzögerung (~50ms). Bei 30 Stufen sinds dann aber gut 5 Sekunden.
 
OMG.Ich glaub ich hab die schnellste Lösung :).Ist ja mal echt nicht schwer gewesen!

# include <stdio.h>

int main () {
int treppen;
printf("Geben Sie bitte die Anzahl der Treppen ein\n");
scanf("%d",&treppen);


int n;
long double a=1,b=0,c;
for (n=0;n<treppen;n++) {
c=a+b;
b=a;
a=c;
}
printf("bei %d Treppen gibt es %Lf Möglichkeiten",treppen,c);
}

edit: Diese Aufgabe wäre sehr gut in Java zu Lösen (BigInteger), weil man da auch sehr große Treppen eingeben kann.Dafür gehts etwas langsamer, denn BigInteger ist ne saulahme Klasse.....

weiteres edit:Hoppla, mit dieser Möglichkeit gibt man ja die Möglichkeiten nicht aus.... Sry.
 
Ich habe das ganze in Python Programmiert (Mein erstes sinnvolles Python Programm)

Code:
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? '))

Richtig testen ob es die korrekten werte liefert konnte ich es nicht.

Ich hab mich jetzt einfach mal an der Aussage von Boar orrientiert das 10 Stufen 89 Möglichkeiten und 15 stufen 987 Möglichkeiten sind.

Das ganze arbeitet recht flott 50000 Stufen unter einer Sekunde, nur die Zahl ist Gigantisch ^^


mfg ba2
 
Hier noch eine Lösung in Perl nach dem bewährten Divide-And-Conquer Verfahren ;-)

Code:
#!/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";
mfg, metax.
 
Habs auch nochmal mit Backtracking unter C gemacht, leider nur so dass es zeigt wie viele Möglichkeiten, aber nicht welche:

Code:
#include <stdio.h>

void treppe(int stufen, int aktuell, int * moeg){
        if(stufen==aktuell) {
                (*moeg)++;
                return;
        }
        if(aktuell+2<=stufen){
                treppe(stufen,aktuell+2, moeg);
        }
        treppe(stufen,aktuell+1, moeg);
}

int main() {
        int moeg=0;
        int stufen=6;
        treppe(stufen,0,&moeg);
        printf("Moeglichkeiten bei %d Stufen: %d\n",stufen,moeg);
        return 0;
}
 
Lest euch mal bitte die Aufgabenstellung durch...

Es kann garnicht sein das bei 10 Stufen es 89 Möglichkeiten gibt jedenfalls nicht nach diese Aufgabenstellung ......

Die möglichkeit 112 und 211 ist doch die gleiche also dürfte es doch nur 1 Möglichkeit sein, oder seh ich etwas falsch.
Hier mein Lösungsansatz ich denk mal die Aufgabe war so gemeint.
 
@CyberPuma:
Ne, ich glaube nicht, außerdem ist das doch gerade schwieriger.

Hier jedenfalls mein Programm, es gibt die Kombinationen zwar noch nicht richtig aus, aber das werde ich noch beheben. Zudem kann man die Maximale Schrittgröße bei mir eingeben. Das Ganze habe ich rekursiv gelöst, wobei ich glaube das man das ja nicht anders machen kann(wenn nicht, dann sagt es mir bitte).
Code:
#include<iostream>

using namespace std;

int GiveNumber(const int NumberHoles,int MaxStep);

int main(void)
{
	  cout<<"Geben sie die Anzahl der Stufen an\n";
	  int NumberHoles=0;
	  int MaxStep=0;
			cin>>NumberHoles;
			if(NumberHoles<1)return 1;
			cout<<"Wie gross darf ein Schritt sein?\n";
			cin>>MaxStep;
			if(MaxStep<1)return 1;
			int InfoSteps=GiveNumber(NumberHoles,MaxStep);
   cout<<"\n\n\nEs gibt "<<InfoSteps<<" Moeglichkeiten\n";
   cin>>NumberHoles;
	  
	  return 0;
}
int GiveNumber(const int NumberHoles,int MaxStep)
{
	  int PossibleSteps=0;
	  int CopyHoles=NumberHoles;
	  for(int i=1;i<=MaxStep;i++)
	  {
				  CopyHoles=NumberHoles;
				  CopyHoles-=i;
				  cout<<i;
				  if(CopyHoles==0)
						{
							  cout<<'\n';
									PossibleSteps++;
									return PossibleSteps;
						}
						PossibleSteps+=GiveNumber(CopyHoles,MaxStep);
			}
	  return PossibleSteps;
}
 
Code:
#!/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"}
Nimmt die Stufenanzahl entweder als erstes Argument oder von STDIN. Außerdem kann man einfach das "Schrittweitenmaximum" ändern beziehungsweise auch einfach irgendeine willkürliche Liste mit Schrittmöglichkeiten eintragen.

Die Anzahl der Möglichkeiten hätte ich extra mit angeben können, aber ich habe lieber eine Möglichkeit pro Zeile und pipe das dann in wc. Wäre ja auch kein Problem das eben mit ins Skript zu nehmen, but i prefer not to.
Code:
./treppenknecht.pl 23|wc -l
46368
 
Wozu muss man sich irgendwelche Algorithmen überlegen? Der Computer ist doch zum Nachdenken da, man muss ihm nur das Problem beschreiben ;)
Code:
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).
Code:
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).

wobei "findall" keine magische und geheime Handlung darstellt, sondern dazu dient alle Lösungen aufeinmal auszugeben (normalerweise liefert Prolog immer nur eine und man muss explizit bestätigen, wenn man eine weitere haben möchte).

Code:
?- 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.
Wobei man sich auch eine Beschreibung als Permutation der Schritte vorstellen könnte (aber solange mache ich Prolog noch nicht).
 
Code:
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.

Ich hab das Problem mit einer Rekursion gelöst.

Eine Beispielausgabe:
Code:
Bitte Anzahl der Stufen eingeben:
5
11111 | 1112 | 1121 | 1211 | 122 | 2111 | 212 | 221 |
Anzahl der Moeglichkeiten:
8

//Edit1: Quelltext berichtigt
 
Meine Java Lösung mit Rekursion :)
Kern ist die doIt Methode.

Code:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class StairsClimbing {

	public static void main(String[] args) {
		Solver sv = new StairsClimbing().new Solver(4);
		System.out.println("Anzahl Möglichkeiten: "+ sv.getSolutionCount());
		System.out.println("Lösungen: "+ sv.getSolutions());
	}

	class Solver {

		private List<String> solutions = null;

		public Solver(int stairsCount) {
			this.solutions = new ArrayList<String>();
			this.doIt(stairsCount, prepareString(stairsCount));
		}

		private String prepareString(int stairsCount) {
			char[] array = new char[stairsCount];
			Arrays.fill(array, '1');
			return String.valueOf(array);
		}

		private void doIt(int pos, String stairs) {
			for(int i=pos; i>1; i--)
				doIt(i-2, stairs.substring(0,i-2) +"2"+ stairs.substring(i));
			solutions.add(stairs);
		}

		public String getSolutions() {
			Collections.reverse(solutions);
			String resultString = Arrays.toString(solutions.toArray());
			return resultString.substring(1, resultString.length()-1);
		}
		
		public int getSolutionCount() {
			return solutions.size();
		}

	}

}

Die Ausgabe für die Stufenanzahl 4 sieht dann so aus:
Code:
Anzahl Möglichkeiten: 5
Lösungen: 1111, 211, 121, 112, 22
 
Python rekurisv
Code:
def step(n,steps_before):
    global stufen
    if n + 1 <= stufen:
        step(n + 1, steps_before + str(1))
    if n + 2 <= stufen:
        step(n + 2, steps_before + str(2))
    if n == stufen:
        global counter
        print steps_before
        counter += 1

counter = 0
stufen = int(raw_input("Wieviele Stufen gibt es?"))
step(0,"")
print "Ways: " + str(counter)

und weil ich Langeweile habe:
Scheme
Code:
(define (treppe n stufen)
  (cond
    ((> stufen n) (+ (treppe (+ n 1) stufen) (treppe (+ n 2) stufen)))
    ((= stufen n) 1)
    ((< stufen n) 0)))

15 Stufen bleiben unter einer Sekunde
 
C++

Hier mal meine Lösung in C++, wenn jemand lust hat kann er mir ya mal schreiben was ich verbessern könnte.

Code:
#include <iostream>

using namespace std;
int treppe( int stufe );
    int stufen;
    char* pointer;
    int counte;
    int moeglichkeiten;
int main( )
{
    // Eingabe:
    cout << "Treppenstufen: ";
    cin >> stufen;
    treppe( stufen );
    cout << "Moeglichkeiten: " << moeglichkeiten;
    delete [] pointer;
    return 0;
}
int treppe( int stufe ) {
    counte++;
    if ( stufe == stufen ) { // Am Anfang wird der char array für die lösung erstellt
    pointer = new char[stufen];
    }
    if ( stufe-2>-1 ) { // Wenn die stufenanzahl -2 nicht ins minus geht rekursion
        pointer[counte] = '2';
        counte = treppe(stufe-2); 
    }
    if ( stufe-1>-1 ) { // Wenn die Stufenzahl -1 nicht ins minus geht: rekursion
        pointer[counte] = '1';
        counte = treppe(stufe-1);
    }
    if ( stufe < 1 ) { // Wenn eine Lösung gefunden wurde ausgeben.
        for( int i=1; i < counte; i++) {
            cout << pointer[i] << " ";
        }
        cout << endl;
        moeglichkeiten++;
    }
        return counte-1; // Einen Schritt zurück gehen
}
 
Für die reine Berechnung der Anzahl:
Man kann das Ganze auch als ein kombinatorisches Problem auffassen: Für k Zweier-Schritte, gibt es genau (n - 2*k + k) über k Möglichkeiten, diese anzuordnen. Dies summiert man dann für 0..n / 2 auf und man hat die Anzahl der Möglichkeiten:
(In Haskell: )
Code:
fac 0 = 1
fac n = product [1..n]

n `binom` k = fac n `quot` (fac k * fac (n-k))

treppe :: Integer -> Integer
treppe n = sum [(n - 2*k + k) `binom` k | k <- [0..n `quot` 2]]

Dabei sieht man auch, dass es, wie oben erwähnt, sich um die Folge der Fibonacci-Zahlen handelt, daher als Einzeiler/Zweizeiler(mit Absicht unverständlich):
Code:
import Control.Monad.Fix
treppe n = fix ((1:) . scanl (+) 1) !! n
 
Zuletzt bearbeitet:
Für ein ähnliches Problem(Projekt Euler 31) hab ich einige Optimierungen vernehmen müssen die ganz gut passen. Dabei nimmt man einfach an dass sie die neuen Möglichkeiten aus der der Stufe vorher und der 2 voher zusammen setzten.(Im Grunde Fibonacci). Bis 2000 geht das Programm fast ohne Verzögerung:
Code:
def moeglichkeiten(n):
    ergebnis = 0
    global muenzen
    for    muenze in muenzen:
    if muenze == n:
            ergebnis +=    1
    if muenze < n:
            global posibilities
            ergebnis += posibilities[n - muenze]
    return ergebnis
posibilities = []
posibilities.append(0)
muenzen    = [1,2]#,5,10,20,50,100,200]                                            
for i in range(1,2001):
    posibilities.append(moeglichkeiten(i))
    print str(i) + ': '+ str(posibilities[i])
Leider passt es aber nicht auf das Ursprungsproblem:)
 
Zurück
Oben