www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Englisch
  Status Grammatik
  Status Lektüre
  Status Korrekturlesen
  Status Übersetzung
  Status Sonstiges (Englisch)

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Matlab" - Euklidischer Algo
Euklidischer Algo < Matlab < Mathe-Software < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Matlab"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Euklidischer Algo: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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

        
Bezug
Euklidischer Algo: Antwort
Status: (Antwort) fertig Status 
Datum: 14:38 Fr 30.03.2007
Autor: Ankh

Probier's mal []hiermit.

Bezug
                
Bezug
Euklidischer Algo: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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


Bezug
                        
Bezug
Euklidischer Algo: Antwort
Status: (Antwort) fertig Status 
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.

Bezug
        
Bezug
Euklidischer Algo: andere frage
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Matlab"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.englischraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]