Erweiterter Euklidische Algorithmus Programmieren?
Obwohl ich den Algorithmus grob verstanden hab besser gesagt, das Schema dahinter habe ich massive Probleme, diese Aufgabe zu lösen. Könnte mir helfen oder entweder eine passende Lösung zu Verfügung stellen. Meistens verstehe ich es anhand der Lösung selber dann.
a) Seien x, y, ∈ ℕ mit x ≠ y, x ≠ 0, y ≠ 0. Der erweiterte Euklidische Algorithmus berechnet α, β ∈ Z, so
dass ggT(x, y) = α·x+β · y.
Beschreiben Sie den erweiterten Euklidischen Algorithmus mit Pseudocode.
Benutzen Sie dazu:
• die Operatoren div und mod,
• eine Laufvariable i,
• ai, bi ∈ N mit a0 = x und b0 = y,
• die Ergebnisse qi, ri ∈ Z von div bzw. mod,
• gewisse Faktoren αi, βi ∈ Z, mit welchen am Ende des Algorithmus α und β bestimmt werden.
Hinweis: Es bietet sich an, dass der Algorithmus bei ri = 0 abgebrochen wird, so dass ggT(x, y) = ri−1
ist. Dann können αi und βi so berechnet werden, dass α = αi−1 und β = βi−1. Zur Berechnung von αi
müssen αi−1 und αi−2 benutzt werden, zur Berechnung von βi müssen βi−1 und βi−2 benutzt werden. Die
initialen Werte müssen daher gesetzt werden: man kann α−2, α−1, β−2, β−1 geschickt wählen.
1 Antwort
das da sagt die WP...
in Pseudo Code:
function ggT(a,b):
r0=a,r1=b
s0=1,s1=0
t0=0,t1=1
for (;;) {
q(i) = trunc(r(i-1) / r(i))
r(i+1)=r(i-1)-q(i)·r(i)
if r(i+1)==0 then break
s(i+1)=s(i-1)-q(i)·s(i)
t(i+1)=t(i-1)-q(i)·t(i)
}
assert(r(i) == a·s(i)+b·t(i))
return ggT(a,b) = r(i)
Mich verwirren die variablen Name irgendwie. was wäre bei mir jetzt Alpha und Beta ?