Postmeister Peter Rätsel



  • Hallo,
    ich muss für mein Praktikum einen Alghoritmus schreiben in C++ um folgendes Rätsel zu lösen :

    Postmeister Peter hat von seinem König den Auftrag für die kleine Insel neue Briefmarken zu entwerfen.

    Das Postsystem ist ziemlich kompliziert, und um das richtige Porto auf jeden Brief zu bekommen sollen mit den Marken alle Summen von 1 bis ... na ja, soweit es eben geht erzielt werden können. Auf jedem Brief sollen höchsten vier Marken kleben damit die königlichen Stempler die Marken mit einem Arbeitsgang entwerten können.

    Der Postmeister stellt seinen ersten Entwurf seinem Post-Azubi Paul vor: "Hier, die 1er Marke. Damit kann ich 1, 2, 3 und 4 bilden. Dann ist hier die 5er, damit haben wir dann 5, 6, 7 und 8. Erst 9 kann ich nicht erreichen, denn dafür bräuchte ich eine 5er und vier 1er, aber das ist nicht erlaubt. 10, 11, 12 wäre alles kein Problem, aber 9 geht nicht und damit ist dann eben schon bei 8 Schluss."
    Paul stutzt, kritzelt etwas auf ein Papier und hält es ihm unter die Nase: "Hier, eine 4er Marke. Damit kann ich genau wie du alle Zahlen bis 8 bilden, aber auch noch 9 (4+4+1) und 10 (4+4+1+1) machen. Erst 11 geht dann nicht mehr.
    Oder ich könnte auch eine 3er Marke machen, dann kommen wir bis... ja, auch bis 10 (3+3+3+1)!"

    Der Postmeister war verwirrt: "Der Kleine hat Recht. 1er und 3er oder 1er und 4er Marken sind wirklich besser als 1er und 5er... erstaunlich! Wie würden wir denn mit drei Marken die Werte auswählen?" fragte er. "1er, 3er und ...?"
    "8er" antwortete Paul. "Aber das ist nicht die beste Lösung. 1er, 3er und 8er bringen uns nur bis 20."
    "Dann muß es ja die 4er als zweite sein, 1er, 4er und ..." "9er" unterbrach der Azubi erneut. "Das bringt uns aber auch nur bis 23".
    "Nur? Warum nur? Was soll denn dann noch besser sein?" wollte Postmeister Peter wissen. "Die 5er als zweiten Wert wollten wir doch nicht?"
    Paul mußte lachen "Ja, bei zwei Werten nicht, aber bei dreien schon. 1er, 5er und 8er bringen uns von 1 bis 26 ohne Lücken!"

    Postmeister Peter konnte es nicht glauben und hat dann Abends zuhause nachgeprüft, aber es stimmte alles genau wie Azubi ihm vorgerechnet hat.

    Für euch ist jetzt die Aufgabe: Wie geht die Serie weiter? Bestimmt die optimalen Markenwerte für 6, 7 und 8 Marken sowie die maximal erreichbare Zahl mit diesen Werten um die für die Lösungsformel nötigen Zahlen zu bekommen.

    Jedoch stehe ich hier völlig auf dem Schlauch und weiß nicht wo ich da anfangen soll... hat da jemand ein paar Tipps die er mir mit auf den Weg geben kann ?
    Danke schonmal. 😕



  • Dieser Thread wurde von Moderator/in SeppJ aus dem Forum MFC (Visual C++) in das Forum Rund um die Programmierung verschoben.

    Im Zweifelsfall bitte auch folgende Hinweise beachten:
    C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

    Dieses Posting wurde automatisch erzeugt.


  • Mod

    Wenn man keinen Plan von der Mathematik hat, kann man immer noch Brute Force benutzen.



  • SeppJ schrieb:

    Wenn man keinen Plan von der Mathematik hat, kann man immer noch Brute Force benutzen.

    Und wie genau würde man diese Methode hier anwenden ? Könnte ein wenig banal gefragt sein ich bin relativ neu auf dem Gebiet und musste mich gerade über Wikipedia über Brute Force informieren... Auf jeden Fall danke für eine schnelle Antwort.



  • Sascha1711 schrieb:

    SeppJ schrieb:

    Wenn man keinen Plan von der Mathematik hat, kann man immer noch Brute Force benutzen.

    Und wie genau würde man diese Methode hier anwenden ? Könnte ein wenig banal gefragt sein ich bin relativ neu auf dem Gebiet und musste mich gerade über Wikipedia über Brute Force informieren... Auf jeden Fall danke für eine schnelle Antwort.

    Bruteforce wäre alle möglichen Kombinationen durchprobieren, bis du eine hast mit der du von 1 bis n (wobei n die größtmöglichste Summe ist) alle Zahlen mittels 6 / 7 / 8 Zahlen abbilden kannst.



  • So etwas löst man über die Preisgestaltung. ;):D

    Ansonsten ist das halt eine typische Optimierungsaufgabe im Bereich der Kombinatorik. Brute force würde man wohl alle möglichen Kombinationen von x Marken durchprobieren. Als Fitness-Funktion schaut man, ob alle vorgegebenen Preise in der Lösungsmenge (vorher sortieren) vorhanden sind. Zur weiteren Selektion kann man dann noch die Häufigkeit der Möglichkeiten pro festgesetztem Preis verwenden, je nachdem was man hier möchte, möglichst viele Varianten oder nur die notwendigen, um alle erwünschten Preise abzudecken.

    C++ bietet in der STL einiges. std::next_permutation etc.


Log in to reply