Euklidischer Algorithmus < Maple < Mathe-Software < Mathe < Vorhilfe
|
| Aufgabe | | Nutzen Sie den umgekehrten euklidischen algorithmus um zu zeigen, dass zwei aufeinanderfolgende Fibonacci-Zahlen die meisten Schritte benoetigen um den groessten gemeinsamen Teiler zu finden. |
Hi,
also ich habe den euklidischen algorithmus programmiert und ihn auch fuer zwei relativ grosse aufeinanderfolgende fibonacci-zahlen ausprobiert (6765, 4181). Daraus wurde ersichtlich, dass erheblich mehr schritte noetig waren um den ggT der beiden zu finden als bei zwei anderen Zahlen (z.B.97663, 66167).
Jetzt soll man den Algorithmus umkehren um zu beweisen, dass zwei aufeinanderfolgende Fibonacci-Zahlen immer die meisten Schritte (fuer Zahlen ihrer groesse) brauchen!
Mein euklidische algorithmus sieht so aus:
r[1] := 97663;
97663
r[2] := 66167;
66167
i := 2;
2
while r[i] <> 0 do
r[i+1] := r[i-1]-r[i]*trunc(r[i-1]/r[i]);
i := i+1
end do;
print(r[i-1]);
Wie kann ich diesen Algorithmus jetzt umkehren ? Ich bin nicht besonders gut in Maple, daher die bloede frage. Ich kann auf dem papier beweisen, dass zwei aufeinanderfolgende Fibonacci-Zahlen teilerfremd sind, daraus folgt ja, dass sie sehr viele Schritte brauchen.
lg,
exeqter
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:20 Mo 16.11.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
