Kleines Programmierrätsel

[Tobi]

Hallo zusammen,

ich knacke zurzeit an einer kleinen Programmieraufgabe und benötige die Lösung und den Zeitaufwand. :P

"Das Treppenproblem. Eine Treppe hat 15 Stufen und es gibt verschiedene Arten die Streppe zu besteigen. Immer eine Stufe, 2 Stufen gleichzeitig oder 3 Stufen gleichzeitig. Wie viele Varianten gibt es, um die Treppe mit 15 Stufen zu besteigen."

Also wer lust hat, kann hier gerne seine Antwort posten.

Viele Grüße
Tobi

[lemar]

Kann es sein, dass die Anzahl der Möglichkeiten sich auf die Fibunacci-Zahlen beläuft? Wenn ja, habe ich dafür schon fertigen Code.

[Zoidy]

Das sollte O(m^n) sein, wenn m die Zahl der Schrittgrößen und n das Ziel ist.

Mein Code ist folgender:

Code: Alles auswählen

#! python3

stepSizes = [1, 2, 3]
target = 15

total = 0

def steps(order):
    global total
    total += 1
    if sum(order) > 15:
        return []
    elif sum(order) == 15:
        return [order]
    else:
        solutions = []
        for x in stepSizes:
            nex = list(order)
            nex.append(x)
            new_solutions = steps(nex)
            solutions.extend(new_solutions)
        return solutions


sls = steps([])

print("{} total tries".format(total))
print("{} solutions found".format(len(sls)))
out = '\n'.join(map(str, sls))
print("They are: {}".format(out))

[Tobi]

das sieht gut aus :)

5768 Möglichkeiten. Wie lange hast du gebraucht, um das zu entwickeln?

[Zoidy]

So ne halbe stunde oder so. Python ist für sowas ja echt mega fix

[Zoidy]

Achso, ich dachte du meinst mit Zeitaufwand die Komplexität, deshalb das O(m^n) xD
Ja, irgendwas zwischen ner halben Stunde bis Stunde hats gedauert ^^

[lemar]

Ist das jetzt sicher richtig? Bin noch skeptisch


Gesendet von iPhone mit Tapatalk

[mieperDE]

*delete

[mieperDE]

Korrektur
32768=2^15

http://www.arndt-bruenner.de/mathe/Allg ... system.htm

[Zoidy]

Ne mieper, das is ja so nich richtig. Die Lösung über-vereinfacht das Problem, man nimmt ja nicht immer alle 15 Stufen. Nur in einem Fall nimmt man 15, der Fall in dem man immer nur eine Stufe gleichzeitig nimmt.
Wie kommst du auf 15^2?
Selbst wenn man immer 15 Stufen nhemen würde, wären es ja eher 3^15 Möglichkeiten, da man pro Stufe 3 Optionen hätte.