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 » Juni 22, 2017, 6:09 pm

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 » Juni 22, 2017, 6:58 pm

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 » Juni 22, 2017, 9:04 pm

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 » Juni 22, 2017, 10:58 pm

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 » Juni 22, 2017, 11:48 pm

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 » Juni 22, 2017, 11:55 pm

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 » Juni 23, 2017, 7:32 pm

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 » August 12, 2017, 11:58 pm

*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 » September 19, 2017, 11:49 am

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 » September 19, 2017, 2:02 pm

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