Einzelnen Beitrag anzeigen

Amateurprofi
Online

Registriert seit: 17. Nov 2005
Ort: Hamburg
1.041 Beiträge
 
Delphi XE2 Professional
 
#8

AW: Wie viel Dreiecke siehst du?

  Alt 24. Sep 2020, 16:27
Ich habe dein Programm geladen aber noch nicht gross gecheckt.

Zwei Lösungswege fallen mir für Dreiecke spontan ein:
1. Du nummerierst die Punkte und zählst nun alle möglichen Punktetripel P auf. Das sind in deinem Fall 11 tief 3. Sei G die Menge aller Geraden g, in deinem Fall sind das sieben. Du prüfst für jedes Tripel p=(a,b,c) in P, ob die drei Tupel (a,b), (b,c), (a,c) in drei Geraden g1,g2,g3 liegen. Immer wenn dies der Fall ist, hast du ein Dreieck gefunden.

2. "Schöner" und sehr direkt geht's via Adjanzenzmatrix. In deinem Fall notierst du in einer 11x11 Matrix A, welcher Punkt mit welchem verbunden ist. Wenn du wissen willst über wie viele Wege du von einem Punkt a über zwei Punkte x, y wieder zu a zurück gelangst (Dreieck), dann kannst du dies direkt berechnen; du berechnest einfach A^3.
In der Diagonalen von A^3 kannst du für jeden der 11 Punkte ablesen auf wie viele Arten du von p über zwei Punkte nach p zurück gelangst.
a) Du zählst dabei jedes Dreieck abc mehrfach; in A^3 an den drei Positionen (a,a) [2 Wege abca, acba], (b,b), (c,c) je doppelt.
b) Du willst sicher die Dreiecke ohne Inhalt nicht mitzählen. Wie viele solche Dreiecke gibt es? Liegen auf einer Geraden drei Punkte, dann gibt es ein Dreieck. Liegen auf deiner Geraden vier Punkte, dann gibt es 4 tief 3=4 Dreiecke, bei n Punkten n tief 3. Diese "Dreiecke" zählst du natürlich in der Diagonalen von A^3 mit und musst sie entsprechend subtrahieren.
(Diese Methode funktioniert natürlich nicht nur für dein Beispiel sondern allgemein. Und nebenbei: Wenn in Zeile a, Spalte b von A^3 n steht, dann weisst du, dass du über n Wege von a nach b gelangen kannst.)

https://de.wikipedia.org/wiki/Adjazenzmatrix
Danke.
So ähnlich wie unter (2) mache ich das.
Gruß, Klaus
Die Titanic wurde von Profis gebaut,
die Arche Noah von einem Amateur.
... Und dieser Beitrag vom Amateurprofi....
  Mit Zitat antworten Zitat