Berechnung ggT(x,y) |
| 19.02.2023, 18:47 | Romaxx | Auf diesen Beitrag antworten » |
| Berechnung ggT(x,y) der für natürliche Zahlen kann mit Hilfe des eukl. Algorithmus berechnet werden Auf der deutschen Wiki-Seite hierzu findet man für die Laufzeit das folgende Bild: [attach]56830[/attach] Warum ist dieses Bild nicht symmetrisch um die Diagonale? Danke. |
||
| 19.02.2023, 20:14 | HAL 9000 | Auf diesen Beitrag antworten » |
Hast du die Legende dieses Bildes gelesen? Dargestellt ist NICHT der ggT-Wert, sondern die Anzahl der Algorithmenschleifen, bis der ggT fest steht. Und für (x,y) mit x<y ist das genau ein Schleife mehr als für (y,x): Und zwar ist das die erste Zeile . |
||
| 19.02.2023, 20:26 | Romaxx | Auf diesen Beitrag antworten » |
Danke. Mir war schon klar, dass nicht der ggT dargestellt wird, sondern die Laufzeit. Wenn also der Algo wüsste, welche Zahl die Größere ist, wäre das Bild symmetrisch. |
||
| 19.02.2023, 21:59 | HAL 9000 | Auf diesen Beitrag antworten » |
Ja. Aber der dargestellte Algorithmus macht eben nicht eine solche Vorab-Überprüfung. M.E. ist das Bild mit Graustufen aussagekräftiger: [attach]56832[/attach] Je heller, desto mehr Schritte benötigt der Algorithmus. Am hellsten ist es dann entlang der Linie mit Steigung des Goldenen Schnittes, d.h. . 
|
||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
|
| Die Neuesten » |
