jeudi 30 avril 2015
euklidischer / naiver Algorithmus
Posted on 02:06 by verona
Aufgabe: Zeigen Sie: Der euklidische Algorithmus benötigt höchstens einen Schritt mehr (= eine Iteration der Schleife mehr) als der naive Algorithmus.
naiver Algorithmus:
1. Falls n = m, setze g auf m und beende die Rechnung. Andernfalls
führe Schritt (2) aus.
2. Falls n > m, ersetze n durch n - m und führe Schritt (1) aus.
Andernfalls führe Schritt (3) aus.
3. Ersetze m durch m - n und führe Schritt (1) aus.
eulidischer Algorithmus:
1. Falls m = 0, dann setze g auf n und beende die Rechnung.
Andernfalls führe Schritt (2) aus.
2. Setze a auf m,
setze b auf n mod m,
setze n auf a,
setze m auf b und
führe Schritt (1) aus.
Als erstes verstehe ich jetzt nicht so ganz, wann der eulidische Algorithmus einen Schritt mehr braucht, als der naive. Eigentlich ist doch der euklidische Algorithmus schneller?
Wie gehe ich weiter an die Aufgabe heran? Einen wirklichen Lösungsansatz habe ich noch nicht gefunden.
naiver Algorithmus:
1. Falls n = m, setze g auf m und beende die Rechnung. Andernfalls
führe Schritt (2) aus.
2. Falls n > m, ersetze n durch n - m und führe Schritt (1) aus.
Andernfalls führe Schritt (3) aus.
3. Ersetze m durch m - n und führe Schritt (1) aus.
eulidischer Algorithmus:
1. Falls m = 0, dann setze g auf n und beende die Rechnung.
Andernfalls führe Schritt (2) aus.
2. Setze a auf m,
setze b auf n mod m,
setze n auf a,
setze m auf b und
führe Schritt (1) aus.
Als erstes verstehe ich jetzt nicht so ganz, wann der eulidische Algorithmus einen Schritt mehr braucht, als der naive. Eigentlich ist doch der euklidische Algorithmus schneller?
Wie gehe ich weiter an die Aufgabe heran? Einen wirklichen Lösungsansatz habe ich noch nicht gefunden.
euklidischer / naiver Algorithmus
Categories: euklidischer / naiver Algorithmus
Inscription à :
Publier les commentaires (Atom)
0 commentaires:
Enregistrer un commentaire