renephoenix.de

Wieviele Dreiecke

Und wieder so ein typisches 9live-Spiel: wie viele Dreiecke befinden sich auf dem Bild? Ich kenne die offizielle Auflösung nicht! Ich tippe 31. Bietet jemand mehr?

Bisherige Kommentare (19)

Kommentar von Marika

Naja, da müsste er ja alle aufzählen, um nen Unterschied festmachen zu können, und nicht bloss »seinen« 32. Du weisst ja nicht nach welchem Schema er gezählt hat.

Kommentar von Friedel

Also man könnt ja jetzt ein kleines Progrämmchen schreiben, was anhand der Eckpunkte das ganze innerhalb kürzester Zeit löst, aber das ist ja langweilig ;)

Bin beim durchzählen auf 30 gekommen, vermutlich ein paar übersehen, also ein paar mehr halt :)

Kommentar von Pablo

Hmm... Mir viele gerade eigentlich kein Programm ein, um so etwas zu berechnen... Soll heißen, ich hätte keine Idee, wie man so etwas programmieren sollte....

Kommentar von Friedel

Keine Idee für so ein Programm?

Ist doch ganz einfach...
Alle Knotenpunkte als Datenbasis speichern, alle direkten Strecken (Nachbarschaftsbeziehungen) speichern und dann kann man daraus die Dreiecke errechnen...

Sicherlich nicht ganz trivial, aber durchaus ein lösbares Problem!

Kommentar von Leila

ich tippe auch auf mehr wie 31 bin alleine auch schon auf 32 gekommen. Vielleicht habt ihr ja einfach vergessen das sich alles auch in einem Dreieck abspielt.

Kommentar von René

Ich weiß trotzdem nicht, woher ihr alle mehr als 31 habt. Mein Versuch:

Anzahl der EinzeldreieckeAnzahl
110
27
34
41
56 8
101
Summe31 33

Vielleicht sehr ihr ja noch irgendwas, was fehlt...

Hinweis: Tabelle nachträglich aktualisiert!

Kommentar von Christian

also ich hab 33...
Renés Tabelle find ich ne sehr gute Idee, bei 5 Einzeldreiecken hab ich aber 8 gefunden.
Es gibt ja fünf Geraden, die durch den Mittelpunkt laufen. Drei davon schneiden das große Dreieck in zwei kleinere und die anderen beiden in je ein Drei- und ein Viereck. Also insgesamt acht 5-teilige Dreiecke.
Aber 37? Wo nehmen sie die letzten vier Dreiecke her?

Kommentar von Arne

Komisch, wenn ich 10, 7, 4, 1, 8 und 1 addiere, komme ich auf 31 und nicht 33. 31 ist auch die Antwort meines Haskellprogrämmchens, zumindest ohne degenerierte Dreiecke, von denen es nach Zählweise meines Programms 23 gibt.

-- ANFANG
import Control.Monad (liftM2)

-- Teillisten einer Liste
-- Nicht in allen Haskell-Implementierungen vorhanden
subsequences :: [a] -> [[a]]
subsequences [] = [[]]
subsequences (x:l) =
  let s = subsequences l in map (x:) s ++ s

-- Knoten: 0 = links unten, dann gegen den Uhrzeigersinn bis 9. 10 = Mittelpunkt
vertices = [0..10]

-- Listen von jeweils mehr als 2 Punkten, die auf einer Geraden liegen
-- (Listen von je 2 Punkten würden nicht schaden, sind aber nicht notwendig)
colinear = [[0,1,2,3,4],[0,5,10],[0,7,8,9],[1,6,10],[2,7,10],[3,8,10],[4,5,6,7],[4,9,10]]

-- Alle Verbindungen zwischen je zwei Punkten, könnte man theoretisch auch aus \»colinear\« berechnen
edges = [(0,1),(0,2),(0,3),(0,4),(0,5),(0,7),(0,8),(0,9),(0,10),(1,2),(1,3),(1,4),(1,6),(1,10),(2,3),(2,4),(2,7),(2,10),(3,4),(3,8),(3,10),(4,5),(4,6),(4,7),(4,9),(4,10),(5,6),(5,7),(5,10),(6,7),(6,10),(7,8),(7,9),(7,10),(8,9),(8,10),(9,10)]

-- Kartesisches Produkt zweier Listen
cartesian :: [a] -> [b] -> [(a,b)]
cartesian = liftM2 (,)

-- Alle Dreiecke als aufsteigende Tripel, einschließlich degenerierter
-- Ein degeneriertes Dreieck ist eines mit Flächeninhalt 0, hier z.B. [0,2,4].
triangles_degen :: [(Int,Int,Int)]
triangles_degen =
  [ (a,b,c) | ((a,b),c) <- vertices `cartesian` vertices `cartesian` vertices,
              (a,b) `elem` edges, (b,c) `elem` edges, (a,c) `elem` edges ]

-- Alle nicht degenerierten Dreiecke
triangles =
  filter (\\(a,b,c) -> all (not . (\\l -> [a,b,c] `elem` subsequences l)) colinear)
         triangles_degen
-- ENDE

Ausgabe:
*Main> (length triangles, triangles)
(31,[(0,1,10),(0,2,7),(0,2,10),(0,3,8),(0,3,10),(0,4,5),(0,4,7),(0,4,9),(0,4,10),(0,5,7),(0,7,10),(0,8,10),(0,9,10),(1,2,10),(1,3,10),(1,4,6),(1,4,10),(2,3,10),(2,4,7),(2,4,10),(3,4,10),(4,5,10),(4,6,10),(4,7,9),(4,7,10),(5,6,10),(5,7,10),(6,7,10),(7,8,10),(7,9,10),(8,9,10)])

Kommentar verfassen

Freiwillige Angabe
Freiwillige Angabe
Der Text kann mit Textile formatiert werden, z.B. *fett* _kursiv_ "link":url. Wie das geht?
Wieviel ist 40 plus 2?

Bisherige Trackbacks (0)

Es wurde noch kein Trackback empfangen!