Vielecke mit einem Zollstock legen

Python :: Aufgabe #115

1 Lösung

Fortgeschrittener - Python von eulerscheZhl - 06.07.2016 um 15:34 Uhr

Mit einem Zollstock soll ein Vieleck gelegt werden. Es zählt dabei nur das Ergebnis, wenn man von oben auf das Vieleck schaut. Wenn der Zollstock mehr Knickstellen hat, als das Vieleck Ecken, gibt es hierfür eine Vielzahl von Möglichkeiten: man kann mehrere Zollsteckteile übereinander legen und die Richtung wechseln, in der man im Kreis läuft.

Um mit einem Zollstock aus vier Teilen ein Dreieck zu legen, gibt es 18 Möglichkeiten (die Zahlen entsprechen den Nummern der Ecken, symmetrische Lösungen sollen als verschieden angenommen werden):

1-2-3-1-2
1-2-3-1-3
1-2-1-3-2
1-3-1-2-3
1-3-2-1-2
1-3-2-1-3
2-3-1-2-3
2-3-1-2-1
2-3-2-1-3
2-1-2-3-1
2-1-3-2-3
2-1-3-2-1
3-1-2-3-1
3-1-2-3-2
3-1-3-2-1
3-2-3-1-2
3-2-1-3-1
3-2-1-3-2

Diese Möglichkeiten sind im Anhang nochmals als animated gif dargestellt.

Wie viele Segmente muss ein Zollstock mindestens haben, um auf mehr als 1000000 Arten ein Fünfeck darstellen zu können?

Bitte melden Sie sich an um zur Aufgabenbeschreibung eine Frage zu stellen.

Frage stellen

Bitte melden Sie sich an um eine Lösung einzureichen.

Lösung einreichen

Lösungen:

von satn1241 (3090 Punkte) - 21.04.2020 um 14:00 Uhr

Python-Code

figur_ecken = 5
knickstellen = 1  # Anfangswert
versuchs_obergrenze = 1  # Grenze jeweils einstelleb


def elemente_filtern(lft_rgt):
    global figur_ecken
    neue_liste = []
    for i in range(0, len(lft_rgt)):
        start = 1
        schritte = [1]
        for j in range(0, len(lft_rgt[i])):
            start += lft_rgt[i][j]
            schritte.append(start)
        if (max(schritte) - min(schritte)) >= figur_ecken:
            neue_liste.append(schritte)
    return neue_liste


def elemente_formatieren(liste):
    global figur_ecken
    for i in range(0, len(liste)):
        for j in range(0, len(liste[i])):
            liste[i][j] = int(liste[i][j]) % figur_ecken + 1
    return liste


def zaehlen(knickstellen):
    from itertools import product

    liste = list(product([-1, 1], repeat=knickstellen))  # zu Ecke links oder Ecke rechts gehen
    ergebnis = elemente_formatieren(elemente_filtern(liste))
    return ergebnis


while True:
    if (len(zaehlen(
            knickstellen) * figur_ecken)) > versuchs_obergrenze:  # *figur_ecken, da durch Umbeschriftung weitere Möglichkeiten entstehen
        False
        print(
            f"Man muss {knickstellen} Segmente haben, um auf mehr als {versuchs_obergrenze} Arten ein {figur_ecken}-Eck darzustellen")

        break
    else:
        knickstellen += 1

# Optional: Lösungen anzeigen lassen # verlängert jedoch die Laufzeit
#ergebnis1 = zaehlen(knickstellen)
# print(f"Dann gibt es bei {knickstellen} Segmenten die folgenden Lösungen:")

# for i in range(0, figur_ecken):
#    ergebnis1 = elemente_formatieren(ergebnis1)
#    print(ergebnis1)
# print(f"Dann sind es genau {len(ergebnis1)*figur_ecken} Möglichkeiten")

Bitte melden Sie sich an um eine Kommentar zu schreiben.

Kommentar schreiben