Dyskusja:Algorytm Euklidesa

Z Wikipedii

Masz nowe wiadomości (różnica z poprzednią wersją).

kod do Pythona podany na stronie przy wartosciach ujemnych zawiesza program moj kod tego nie robi

def lala(a,b):

   while 1:
       if a==b:
           return a
       elif a > b:
           a, b=b, a-b
       elif a < b:
           a, b=b, b-a

i źle nie robi że sie dla ujemnych zawiesza ;) albowiem jest napisane: (...) liczb naturalnych (...) :] jak kto chce stosowac do liczb mniej naturalnych niech sobie "zmodułuje" ;) rownie dobrze ktoś by mógł zgłosic watpliwość, że nie dziala dla ułamków :) --severson 12:27, 28 paź 2004 (CEST)

Spis treści

1 nie rozumiem
2 Inny przykład w Pascalu
3 Implementacja w SQL
4 liczby calkowite, nie naturalne
5 Javascript i zaokrąglanie w dół.
6 Rozszerzony Algorytm Euklidesa w Turbo Pascalu z opisem
7 dowód twierdzenia

[edytuj] nie rozumiem

nie mam pojecia o co chodzi!!

Z algorytmem na stronie jest jednak pewien problem:

dane są dwie liczby naturalne a i b
jeśli b jest równe zeru, to NWD jest równe a...

Jeśli np. a=0 b=1 to ... podobnie problem jeśli b=0, bo jaki to ma sens, ze NWD (5,0)=5 Coś więc trzeba poprawić.

Pzdr WtK (witek@oeiizk.waw.pl)

Twoja poprawka była dobra, ale ponieważ nie chciało nam się rozważać przypadku, gdy b=0, zażądałyśmy a, b>0; za to nie trzeba zakładać, że a>b - algorytm działa i tutaj. Dzięki za zwrócenie uwagi i przepraszamy, żeśmy nie dostrzegły od razu. Sprawdź, czy teraz działa. 4C^uwagi 15:12, 25 maj 2005 (CEST)

BŁĄD!!! Musi byc zalozenie, ze a>b. Bo w koncu 5 mod 3 to nie jest to samo, co 3 mod 5!!!

NWD(x,0)=x i jest to zgodne z definicją (bo $\forall\ x\in \mathbb{N}\ x|0$ ), jedyny problem jest przy NWD(0,0) ale zazwyczaj przyjmuje się NWD(0,0)=0 więc też się zgadza ...

co do a>b w pierwszym kroku algorytm poprostu zamieni a z b, i już będzie a<b

[edytuj] Inny przykład w Pascalu

W "innym przykładzie w Pascalu" brakuje pętli! Mik 06:56, 20 sty 2006 (CET)

[edytuj] Implementacja w SQL

Jakoś specjlanie nie miałem nigdy potrzeby, więc się nie wyznaję na funkcjach w SQL, ale o ile wiem, to w oficjalnym standardzie nie ma czegoś takiego jak funkcje. Czyżby chodziło tam o coś używanego w PostgreSQL - to znaczy PLSQL? --Nux ^{zostaw notkę} 19:00, 4 cze 2006 (CEST)

[edytuj] liczby calkowite, nie naturalne

co prawda nie ma za wiele czasu i dlatego sam tego nie poprawie, ale w rozszerzonym algorytmie euklidesa rozwiazaniem sa liczby calkowite, nie naturalne, poniewaz NWD(a,b) jest jednoczesnie mniejszy od a i mniejszy od b, a co za tym idzie od dowolnej sumy xa+yb, gdy x,y naleza do liczb naturalnych (oczywiscie zakladajac ze a i b sa nieujemne - tak jak jest w komentarzu do kodu w javascript)

dodatkowo zapraszam na

http://www.algorytm.org/index.php?option=com_content&task=view&id=166&Itemid=28

[edytuj] Javascript i zaokrąglanie w dół.

Można skorzystać z podwójnego przeczenia bitowego zamiast Math.floor

Przykładowo ~~6.8 ~~3.345

[edytuj] Rozszerzony Algorytm Euklidesa w Turbo Pascalu z opisem

Program rozszerzonego algorytmu w Turbo Pascalu . Zmienną d mozna wykorzystac na przyklad do liczenia ilosci iteracji potrzebnych do wykoanania algorytmu . Jest NAPRAWDE szybki !!! - 3 lub 4 razy wystarczaja !!!

program Euklides ; { Program dziala na zasadzie rozszerzonego algorytmu Euklidesa } uses dos; var

   a,b,c,d,p,q,r,s,a0,b0,qout,new_r,new_s:        longint;

begin

 writeln ( ' Program rozszerzonego algorytmu Euklidesa ');
 writeln (' Program oblicza P takie ze P*A = 1 MOD B ');
 writeln ( ' podaj A ' );
 readln (a) ;
 writeln ( ' podaj B - ABY DZIALALO MUSI TO BYC LICZBA PIERWSZA  ');
 readln (b);
 a0 := a;
 b0 := b ;
 p := 1 ;
 q := 0 ;
 r := 0 ;
 s := 1 ;
 while b <> 0 do
  begin
   qout:=trunc( a/b );
   c := a - qout*b;
   a := b;
   b := c;
   new_r := p - qout * r ;
   new_s := q - qout * s ;
   p := r ;
   q := s ;
   r := new_r ;
   s := new_s ;
   d:=1;
  end;
  if p<0 then p:=p+b0;
  { Obliczenia prowadzimy w zakresie b0 - dlatego ta operacja }
  writeln ( ' Program wydaje dwie liczby takie ze ');
  writeln ( ' P * A = 1 MOD B ');
  writeln ( ' P=  ', p , '  dodatkowa zmienna q=' , q );
  writeln ( ' Aby zakonczyc nacisnij ENTER ' ) ;
  readln ;

end.

Rozpatrzmy jak to dziala : Prosty przyklad liczby 4 i 11 . Wynikiem jest oczywiscie 3 , poniewaz 3*4=12 a 12 mod 11 daje 1 . Mamy wiec liczbe 3 ktora spelnia warunek

  3*4 mod 11 = 1

Jak ja otrzymac ? Mamy rozszerzony algorytm Euklidesa .

   Czesc algorytmu dziala tak jak standardowy algorytm
   i - numer iteracji

i,,,,a,,,,b,,,,qout - dodatkowa zmienna potrzebna nizej 0,,,,4,,,,11,,,0 1,,,,11,,,4,,,,2 2,,,,4,,,,3,,,,1 3,,,,3,,,,1,,,,3 4,,,,1,,,,0,,,,- tu algorytm sie zatrzymuje poniewaz b=0 . W kolejnych iteracjach algorytmu Obliczamy czesc calkowita a/b otrzymujac qout. W miejsce a wpisujemy b. W miejsce b wpisujemy wynik a mod b .

   Aby uzyskac wynik czyli liczbe 3 opisana jako p obliczamy :

  r = p - qout * r{poprzednie}

  Czyli otrzymujemy ( {} - oznacza  numer iteracji ) :

  r{1} = 1{p startowe} - 0{qout} * 0{r startowe} = 1

        p = 0 - przeniesione z r w tym wypadku startowego

  r{2} = 0 - 2 * 1 = -2
        p=1 - przeniesione z poprzedniego r , dlatego w algorytmie
        sa dwie zmienne r i NEW_R
  r{3} = 1 -   1 * -2 = 3
        p = -2
  r{4} = -2    -3*3 = -11
        p = 3

Tu algorytm sie zatrymuje i wydaje wynik jako 3 . Jesli wynik wyjdzie ujemny po prosty dodajemy b do wyniku poniewaz wynik jest utrzymywany " w kolko " w granicach b .

[edytuj] dowód twierdzenia

Moim zdaniem dowód prawdziwości twierdzenia jest delikatnie mówiąc nieprzekonywujący. Proponuję dodać do niego (przerobioną wersję z angielskiej wiki):

Aby wykazać że $NWD (a,b) = NWD (b, a\ mod\ b)$ należy udowodnic, iż wspólny podzielnik liczb $a$ i $b$ jest również podzielnikiem liczby $a\ mod\ b$