Liczenie po chińsku ...okiem programisty

17.08.2009 - Agata Murawska
TrudnośćTrudność

Co dalej? Do implementacji konieczna jest znajomość rozszerzonego algorytmu Euklidesa. Zwykły algorytm Euklidesa pozwala sprawdzić, jaki jest największy wspólny dzielnik dwóch liczb. Rozszerzona wersja daje nam znacznie więcej - dla danych $ a $ i $ b $ takich, że $ \mathrm{NWD}(a,b) = n $ znajduje on $ x $ i $ y $ takie, ze $ a*x + b*y = n $. Szczegółowe dowody poprawności i własności algorytmu nie są nam w tej chwili potrzebne, wystarczy jedynie wiedzieć, że jest to idealny sposób na znalezienie wszystkich $ x_i $ z naszych wcześniejszych rozważań.

1
2
3
4
5
6
7
8
9
10
int ext_Euclid(int a, int b, long long &l, long long &k){
    if (!a){
        l = 0;
        k = 1;
        return b;
    }
    int d = ext_Euclid(b%a, a, k ,l);
    l -= (b/a)*k;
    return d;
}



Zastanówmy się na koniec, o ile udało nam się przyspieszyć znajdowanie rozwiązania. Musimy uwierzyć na słowo, że procedura ext_Euclid działa w czasie $ \log n $. Wykonujemy ją k razy, zatem ostateczny koszt czasowy to $ \mathrm{O}(k*\log (n)) $.

Zadania sprawdzające

  1. W przytoczonej na wstępie zagadce nie wszystkie dane są nam potrzebne do rozwiązania. Które z nich można pominąć i dlaczego?
  2. Powiedzieliśmy, że jeśli $ \mathrm{NWD}(a,b) = 1 $, to istnieją takie liczby $ x $ i $ y $, że $ ax+by = 1 $. Czy potrafisz udowodnić ten fakt?

    Wskazówka

3.5
Twoja ocena: Brak Ocena: 3.5 (2 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com