Forums » 36. BwInf

Aufgabe 1 - Laufzeit

    • 8 Beiträge
    30. Januar 2018 20:02:46 CET
    Kann es sein, dass es einen ziemlich drastischen Unterschied zwischen dem Aufwand von n=9 und n=10 gibt? Mein Programm schafft n=9 mittlerweile in wenigen Sekunden. Bei n=10 ist es aber gnadenlos überfordert...
    • 3 Beiträge
    10. Februar 2018 14:56:44 CET
    Es ist wichtig zu bemerken, dass das Programm für gerades n (z.B. 10) länger benötigt als für ungerades n (z.B. 9), da bei geradem n alle möglichen Lückenpositionen belegt werden müssen, wohingegen bei ungeradem n an einigen Positionen keine Lücken seien müssen.
    Dies kann man zeigen indem man die Formeln für die Anzahl der "genutzten" Lücken pro Reihe (n-1) und der insgesamt möglichen Lücken in Abhängigkeit von n herleitet und dann betrachtet, wie viele Reihen für gegebenes n gebildet werden können.
    • 31 Beiträge
    12. Februar 2018 16:55:54 CET
    Ohne jetzt über die Lösung zu reden, würde ich folgendes sagen: Wenn dein Programm nicht in der Lage ist, für n=10 eine Mauer der Höhe 6 auszugeben, wirst du auf jeden Fall einen kräftigen Punktabzug bekommen. Wie aber die Punktevergabe bei einem größeren n bzw. bei der von deinem Programm ermittelten Höhe abhängig von einem n aussieht, kann ich nicht sagen (wobei mich dies natürlich interessieren würde ;)). Wahrscheinlich wirst du auch von den Verantwortlichen des Wettbewerbs keine Antwort darauf erhalten.

    MfG Gabriel
    Dieser Beitrag wurde am 12. Februar 2018 16:58:46 CET von Gabriel Dengler bearbeitet