0 Daumen
1,1k Aufrufe

wie funktioniert diese Aufgabe?

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.


b) Überprüfen Sie den Algorithmus anhand des Beispiels x = 23 und y = 13

Avatar von

Vom Duplikat:

Titel: Seien x, y, ∈ ℕ mit x ≠ y, x ≠ 0, y ≠ 0. ... Beschreiben Sie den erweiterten Euklidischen Algorithmus mit Pseudocode.

Stichworte: euklidischer,algorithmus,ggt,code

Wie funktioniert diese Aufgabe?

Seien x, y, ∈ ℕ mit x ≠ y, x ≠ 0, y ≠ 0. Der erweiterte Euklidische Algorithmus berechnet α, β ∈ ℤ, so dass ggT(x,y) = α*x + β*y. Beschreiben Sie den erweiterten Euklidischen Algorithmus mit Pseudocode. Benutzen Sie dazu die Operatoren div und mod.


Dankeschön

Vom Duplikat:

Titel: Seien x, y, ∈ ℕ mit x ≠ y, x ≠ 0, y ≠ 0.

Stichworte: euklidischer,algorithmus,ggt,code

Wie funktioniert diese Aufgabe?

Seien x, y, ∈ ℕ mit x ≠ y, x ≠ 0, y ≠ 0. Der erweiterte Euklidische Algorithmus berechnet α, β ∈ ℤ, so dass ggT(x,y) = α*x + β*y. Beschreiben Sie den erweiterten Euklidischen Algorithmus mit Pseudocode. Benutzen Sie dazu die Operatoren div und mod.


Dankeschön

Studiere mal die Rechnung hier: https://www.mathelounge.de/420132/verstandnisprobleme-erweiterten-euklidischen-algorithmus Vielleicht habt ihr da so behandelt.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community