Mateusz plus za sposób przedstawienia algorytmu Euklidesa Przedstawiłeś ten algorytm w sposób wg którego łatwo i efektywnie można go zapisać w ulubionym języku programowania Widziałem inny sposób przedstawienia tego algorytmu i aby zapisać tamten sposób trzeba było ilorazy zapamiętać na stosie Twój sposób przedstawienia tego algorytmu jest bardziej efektywny Jako ćwiczenie możecie zapisać algorytm Euklidesa w ulubionym języku programowania bazując na tym co nakręcił Mateusz Tutaj zależnie od danych wejściowych współczynniki są albo w xa oraz ya albo w xb oraz yb Pisząc program dobrze by było aby były w jednej parze zmiennych no ale to można zrealizować jedną instrukcją if oraz zamianą elementów
Czy można postąpić szybciej z tymi odwracalnymi, żeby nie szukać po kolei, tylko do pary dawać, np. jak już znaleźliśmy 1, to 59 też jest, jak 7, to 53 itp.? (suma ich wynosi 60)
Dobre pytanie, odpowiedź tak, dowód: Niech a będzie odwrotnością b, tzn. ab=1 przemnażając przez -1 dostaniemy -ab=-1. zachodzi 60a=0. te dwie kongruencje można dodać stronami wówczas 60a-ba = -1, czyli (60-b)a=-1 ponownie przemnóżmy przez -1 wówczas (60-b)(-a)=1. c.n.d Oczywiście zamiast 60 może być dowolnie m. przyjąłem 60 dla ustalenia uwagi.
Gratuluję błyskotliwego umysłu. Sprawnie zrobiony wykład. Lubię rozkminiać takie mądre algorytmy. Euklides to był błyskotliwy umysł. Szkoda, że Grecja nie ma obecnie tak znamienitych matematyków.
Łatwo i przyjemnie. Dlaczego tu jest tylko 7 komentarzy? Pewnie dla tego, że trafiają tu leniwi ludzie, którzy chcą szybko zrozumieć temat bez wysiłku. Dziękuję za wytłumaczenie.
Też lubię język C. Napisałem dwa algorytmy z wykorzystaniem biblioteki mpfr do obliczania liczby Pi. Jeden nazwałem FCPI, a drugi PILL. FCPI wykorzystuje złotą liczbę Phi i liczby Fibonacciego, a PILL, to rozszerzony algorytm Leibniza.
Mateusz plus za sposób przedstawienia algorytmu Euklidesa
Przedstawiłeś ten algorytm w sposób wg którego łatwo i efektywnie można go zapisać w ulubionym języku programowania
Widziałem inny sposób przedstawienia tego algorytmu i aby zapisać tamten sposób trzeba było ilorazy zapamiętać na stosie
Twój sposób przedstawienia tego algorytmu jest bardziej efektywny
Jako ćwiczenie możecie zapisać algorytm Euklidesa w ulubionym języku programowania bazując na tym co nakręcił Mateusz
Tutaj zależnie od danych wejściowych współczynniki są albo w xa oraz ya albo w xb oraz yb
Pisząc program dobrze by było aby były w jednej parze zmiennych
no ale to można zrealizować jedną instrukcją if oraz zamianą elementów
Czy można postąpić szybciej z tymi odwracalnymi, żeby nie szukać po kolei, tylko do pary dawać, np. jak już znaleźliśmy 1, to 59 też jest, jak 7, to 53 itp.? (suma ich wynosi 60)
Dobre pytanie, odpowiedź tak, dowód: Niech a będzie odwrotnością b, tzn. ab=1 przemnażając przez -1 dostaniemy -ab=-1. zachodzi 60a=0. te dwie kongruencje można dodać stronami wówczas 60a-ba = -1, czyli (60-b)a=-1 ponownie przemnóżmy przez -1 wówczas (60-b)(-a)=1. c.n.d Oczywiście zamiast 60 może być dowolnie m. przyjąłem 60 dla ustalenia uwagi.
Innym sposobem znajdowania odwrotności jest wykorzystanie twierdzenia Eulera uogólniającego Małe twierdzenie Fermata
chyba mały błąd w minucie 10.50. Rozpisując tabelę Z8 numerujemy chyba 0 do 7.
Gratuluję błyskotliwego umysłu. Sprawnie zrobiony wykład. Lubię rozkminiać takie mądre algorytmy. Euklides to był błyskotliwy umysł. Szkoda, że Grecja nie ma obecnie tak znamienitych matematyków.
Łatwo i przyjemnie. Dlaczego tu jest tylko 7 komentarzy? Pewnie dla tego, że trafiają tu leniwi ludzie, którzy chcą szybko zrozumieć temat bez wysiłku. Dziękuję za wytłumaczenie.
Ciekawe
Gdzie moznabyloby wykorzystać tą wiedzę w praktyce? Jak zwykle bardzo dobry film
Kodowanie metodą Rabina
na kolokwium
No to jak wyglądałby kod tej funkcji nwd ?
int gcdex(int a,int b, int &x,int &y){
int xa = 1, ya = 0, xb = 0, yb=1;
int a0 = a, b0 = b;
int q;
while(a0 != 0 && b0 != 0)
{
if(abs(a0) > abs(b0))
{
q = a0/b0;
a0 = a0 % b0;
xa -= q*xb;
ya -= q*yb;
}
else
{
q = b0/a0;
b0 = b0 % a0;
xb -= q*xa;
yb -= q*ya;
}
}
if(b0 == 0)
{
x = xa;
y = ya;
}
else
{
x = xb;
y = yb;
}
if(a*x+b*y < 0)
{
x = -x;
y = -y;
}
return a*x+b*y;
}
Teraz chyba funkcja będzie działać poprawnie
Też lubię język C. Napisałem dwa algorytmy z wykorzystaniem biblioteki mpfr do obliczania liczby Pi. Jeden nazwałem FCPI, a drugi PILL. FCPI wykorzystuje złotą liczbę Phi i liczby Fibonacciego, a PILL, to rozszerzony algorytm Leibniza.