Euklidischer Algo < Matlab < Mathe-Software < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:30 Fr 30.03.2007 | | Autor: | Riley |
Hallo,
ich würde gerne eine funktion schreiben um den erweiterten euklidischen algorithmus zu berechnen. Den ggT bekommt man ja schnell durch Rekursion, aber wie kann ich m und n finden, dass ggT(a,b)=m*a+n*b gilt?
wär super, wenn mir jemand weiterhelfen könnte...
Viele Grüße,
riley
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:38 Fr 30.03.2007 | | Autor: | Ankh |
Probier's mal ![[]](/images/popup.gif) hiermit.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:30 Fr 30.03.2007 | | Autor: | Riley |
HI,
danke für den link.
hm, hab das internet auch schon durchforstet, da findet man schon ein paar sachen, auch das bei wiki.
aber ich versteh folgendes nicht ganz:
extended_euclid(a,b)
1 wenn b = 0
2 dann return (a,1,0)
3 (d',s',t') extended_euclid(b, a mod b)
4 (d,s,t) (d',t',s' - floor(a/b)t')
5 return (d,s,t)
das problem ist, dass man die zahlen s,t für die zerlegung ggT(a,b) = s*a + t * b ja wenn man das per hand macht rückwärts berechnet.
und das weiß ich nicht wie ich das programmieren soll, weil sonst müsste ich ja alle zwischenwerte von a und b wie sie in der tabelle bei wiki aufgelistet sind zwischenspeichern...??
wie funktioniert das hier bei dem pseudo-code??'das müsste wohl die 4.zeile sein...???
Viele Grüße
riley
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 09:46 Mo 02.04.2007 | | Autor: | Ankh |
> aber ich versteh folgendes nicht ganz:
> extended_euclid(a,b)
> 1 wenn b = 0
> 2 dann return (a,1,0)
> 3 (d',s',t') extended_euclid(b, a mod b)
> 4 (d,s,t) (d',t',s' - floor(a/b)t')
> 5 return (d,s,t)
>
> das problem ist, dass man die zahlen s,t für die zerlegung
> ggT(a,b) = s*a + t * b ja wenn man das per hand macht
> rückwärts berechnet.
> und das weiß ich nicht wie ich das programmieren soll,
> weil sonst müsste ich ja alle zwischenwerte von a und b wie
> sie in der tabelle bei wiki aufgelistet sind
> zwischenspeichern...??
>
> wie funktioniert das hier bei dem pseudo-code??'das müsste
> wohl die 4.zeile sein...???
Ich weiß nicht, ob ich deine Frage richtig verstehe. Die Parameter a und b werden durch die Rekursion automatisch in einem Stack verwaltet, ebenso die anderen Variablen.
Wenn du dich darüber wunderst, dass du drei Rückgabewerte hast, dann fasse die drei Werte in einer Struktur zusammen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:54 Fr 30.03.2007 | | Autor: | Riley |
Hi again,
wie man die s und t findet hab ich inzwischen raus. hab nur noch ne allgemeine frage zum euklidischen erweiterten Algo. diese zerlegung ggT = s *a + t *b ist ja nicht eindeutig, d.h. es hängt vom jeweiligen programm ab welches s und t man rausbekommt?
viele grüße
riley
|
|
|
|
