Kleines Programmierrätsel

"Ich würde niemals in einen Club wollen, der Leute wie mich als Mitglied aufnimmt."
Benutzeravatar
Tobi
Beiträge: 2217
Registriert: April 10, 2014, 9:15 am
Kontaktdaten:

Kleines Programmierrätsel

Beitrag von 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
Schiffe: RSI Orion, AEGIS Vulcan, Banu Merchantman, DRAKE Dragonfly und TUMBRIL Cyclone :]
Bild
Benutzeravatar
lemar
Chancellor
Beiträge: 1815
Registriert: März 15, 2014, 4:09 pm
Wohnort: Oberbayern

Re: Kleines Programmierrätsel

Beitrag von 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.
Bild

Kurze Frage: Wie oft darf ich bei Notwehr nachladen?
Benutzeravatar
Zoidy
Beiträge: 760
Registriert: April 20, 2014, 9:35 am
Wohnort: Bremen Stadt

Re: Kleines Programmierrätsel

Beitrag von 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))
Bild
Benutzeravatar
Tobi
Beiträge: 2217
Registriert: April 10, 2014, 9:15 am
Kontaktdaten:

Re: Kleines Programmierrätsel

Beitrag von Tobi »

das sieht gut aus :)

5768 Möglichkeiten. Wie lange hast du gebraucht, um das zu entwickeln?
Schiffe: RSI Orion, AEGIS Vulcan, Banu Merchantman, DRAKE Dragonfly und TUMBRIL Cyclone :]
Bild
Benutzeravatar
Zoidy
Beiträge: 760
Registriert: April 20, 2014, 9:35 am
Wohnort: Bremen Stadt

Re: Kleines Programmierrätsel

Beitrag von Zoidy »

So ne halbe stunde oder so. Python ist für sowas ja echt mega fix
Bild
Benutzeravatar
Zoidy
Beiträge: 760
Registriert: April 20, 2014, 9:35 am
Wohnort: Bremen Stadt

Re: Kleines Programmierrätsel

Beitrag von 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 ^^
Bild
Benutzeravatar
lemar
Chancellor
Beiträge: 1815
Registriert: März 15, 2014, 4:09 pm
Wohnort: Oberbayern

Re: Kleines Programmierrätsel

Beitrag von lemar »

Ist das jetzt sicher richtig? Bin noch skeptisch


Gesendet von iPhone mit Tapatalk
Bild

Kurze Frage: Wie oft darf ich bei Notwehr nachladen?
Benutzeravatar
mieperDE
Beiträge: 1597
Registriert: April 26, 2014, 7:20 pm
Wohnort: NRW

Kleines Programmierrätsel

Beitrag von mieperDE »

*delete
Zuletzt geändert von mieperDE am September 19, 2017, 11:50 am, insgesamt 1-mal geändert.
Bild
COIS world domination tour since 2014.
Handelsrouten DPS Calculator Components Database
Benutzeravatar
mieperDE
Beiträge: 1597
Registriert: April 26, 2014, 7:20 pm
Wohnort: NRW

Re: Kleines Programmierrätsel

Beitrag von mieperDE »

Bild
COIS world domination tour since 2014.
Handelsrouten DPS Calculator Components Database
Benutzeravatar
Zoidy
Beiträge: 760
Registriert: April 20, 2014, 9:35 am
Wohnort: Bremen Stadt

Re: Kleines Programmierrätsel

Beitrag von 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.
Bild
Antworten