Einzelnen Beitrag anzeigen

Michael II

Registriert seit: 1. Dez 2012
Ort: CH BE Eriswil
734 Beiträge
 
Delphi 11 Alexandria
 
#2

AW: Wie viel Dreiecke siehst du?

  Alt 24. Sep 2020, 10:13
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
Michael Gasser

Geändert von Michael II (24. Sep 2020 um 12:28 Uhr)
  Mit Zitat antworten Zitat