Cześć [Muzyka] witam was bardzo serdecznie w moim kolejnym filmiku dzisiaj powiem wam o algorytm euklidesa jego wersji rozszerzonej do czego nam ona dlaczego to działa Co to nam daje Jak napisać program zapraszam Zacznijmy od algorytmu euklidesa wersji podstawowej oczywiście daje nam największy wspólny dzielnik dwóch liczb naturalnych czyli dla dwóch liczb naturalnych a i b znajdzie taki całkowity dzielni który jest wspólnym największym i robi to w sposób optymalny szybciutko dzieląc jedną liczbę przez drugą zapisując resztę na dole Martyny slajdy macie taką definicję rekurencyjną nwd dla dwóch liczb a i b jest tym samym z czym nwd dla b i reszty z dzielenia przez b Kiedy b jest większe od zera a kiedy b jest równa 0 jest po prostu liczby A i z tej definicji wywodzi się rekurencyjną wersja tego algorytmu którą zaraz zobaczycie przykładowo dla 23 i 13 czyli i 23/13 reszta z dzielenia jest 10 23/13 jest jeden reszta 10 i nwd dla a i b jest na samym co nwd dla b i reszta czyli przesuwamy 13-ta a resztę nowe i wywołujemy rekurencyjnie zostaną funkcję wejście 13/10 jest jeden reszta 3 znowu 10/3 jest 3 reszta 1 i znowu przesuwamy wywołujemy kolejną rekurencyjną nwd 2313 i przed 1/3 reszta zero i przesuwamy ostatni raz jeden staje się a reszta staje się bez I w tym momencie kończymy bo system funkcje rekurencyjne wynika że kiedy B jest zero to a jestem nwd Czyli już teraz widzimy że jedynka będzie ten nwd z punktu widzenia algorytm euklidesa wersji rozszerzonej nie jest potrzebne nam ten ostatni wiersz więc sobie teraz tak to pozostawimy Co to jest algorytm euklidesa wersji podstawowej ja bym chciała żebyśmy dzisiaj znajduje się ogródek widzę wersji rozszerzonej ten algorytm pozwala nam rozwiązać równanie to tak zwane równanie diofantyczne Równanie x razy a plus y razy b równa się nwd ab dla xy całkowitych Czyli co to jest dane dane jest oczywiście a i b jak poprzednio w podstawowej wersji algorytmu euklidesa oczywiście jesteśmy w stanie obliczyć nwd a przy okazji za pomocą algorytmu euklidesa będziemy mogli wyznaczyć takie x i y g x przedłożone przez a a y przedłożone przez b i suma tych dwóch liczb dana BMW de sable i oczywiście Takie xy które są całkowite na pewno nie ma rozwiązanie dziesiętne liczb całkowitych czyli ten problem To sprowadza się też czasami do problemu przelewania wody to znaczy właśnie Jednym z przykładów zastosowania tego algorytmu jest problem przelewania wody Czyli mamy dane jakieś wiaderko o pojemności a na przykład 24 litry mamy dane drugie wiaderko pojemności B na przykład 13 litrów i chcielibyśmy i mamy studnie bez dna z której możemy czerpać nie chcemy ale tylko pełne wiaderka bo jak widzicie wiaderka nie mają jednym podziałki jakieś skali Nie wiemy ile by było litrów gdybyśmy normalnie do pełna Ale wiemy że klejem do pełna mamy 2314 litrów Tak więc możemy nalać tylko pełne wiaderka i chcemy z tego uzbierać w jakimś zbiorniku mamy jakieś do dyspozycji zbiornik nie przejmujemy się jego pojemność Może na przykład Najpierw trzeba będzie dużo wiaderek 23 litrowych tam nalać a potem odjąć na przykład 13 litrowe nieważne chcemy uzbierać koniec końców tam jeden litr wody i okazuje się że to się da dlatego że jedynka jest nwd z pojemności tych Darek tak Czyli 2313 nie Każdą liczbę siada oczywiście dla dla liczb względnie pierwszych Każdą liczbę się da bo wielokrotność a nwd również się da problem wystarczy lewą i prawą stronę przemnożyć Przez tą samą liczbę natomiast na przykład dla wiaderek 2012 Gdzie nwd jest równe 4 nie da się na przykład uzbierać pojemności 5 litrów tak Czyli po prawej stronie musi stać nwd lub wielokrotność tego nwd wtedy polewę jesteśmy w stanie takie xy i znaleźć to jest problem przelewania wody czyli zajmiemy się dzisiaj rozwiązywaniem takiego równania x razy x plus y razy b równa się nwd ab dla z danych a i b czyli rozwiązujemy to również szukamy x i y a e będziemy wykorzystywać do tego algorytmu euklidesa więc algorytm euklidesa Wróćmy do niego pierwszym kroku widzieliśmy 23/13 zyskaliśmy resztę 10 moglibyśmy to zapisać w ten sposób 23 to się równa 1 razy 13 plus 10 w drugim kroku dzieliliśmy 13/10 otrzymaliśmy resztę Czy moglibyśmy to zapisać 13 równa się 1 razy 10 plus 3 i w trzecim kroku 10 równa się 3 razy 1 plus 1 z o.o z inaczej moglibyśmy wyjść od reszty i wyciągnąć z tych równań reszta i zapisać G10 jest trudne 23 minus 1 razy 13 czy jest równe 13 minus 1 razy 10 a1 jest równe 10 minus 3 razy 3 dlaczego tak wychodzimy Od reszty dlatego że w trzeciej linii od góry czyli w tym momencie kiedy już widzimy to nasze młode to uzyskaliśmy informację o tym właśnie Zobaczcie mamy to równanie prawda częściowo to znaczy jest po jednej stronie jedynka to nwd po drugiej stronie coś tam jeszcze nie jest to x razy nasze pierwotne a y razy nasze pierwotne b ale jakaś taka postać jest prawda od niej moglibyśmy zacząć to napisać sobie że jeden jest równy 10 minut 3 razy 3 i próbować się pozyskać taką sytuację żeby po prawej stronie nie było nic podwielokrotności 23 wieki trzynastek z tych trzech wzorków jesteśmy w stanie to zrobić z tych trzech worków które Zapisaliśmy krok po kroku w naszym nwd co możemy najpierw zrobić zauważyć że Trójka już wyszłam wzorku środkowym i zapisać zamiast 3 razy 3 3 razy 13 minus 1 razy 10 powiem mnożeniu nawiasów mamy 10 minut trzynastki i plus 3 dziesiątki co dalej możemy zrobić już mamy tutaj jakieś wielokrotności 13 na razie jeszcze się pamiętają wielokrotności dziesiątek chcielibyśmy mieć wielokrotności 20 trójek i trzynastek dlatego to co możemy zrobić oczywiście zauważyć że dziesiątkę możemy jej się pozbyć używając w kolei pierwszego wzoru czas na pierwszy wzór Zobaczcie te wzory bierzemy w kolejności konkretnej od dołu i coraz to nam się przydaje kolejny licząc od dołu aż na końcu przydają nam się ten pierwszy z góry więc Napiszmy zamiast dziesiątki 23 minus 1 razy 13 i teraz już mamy Zobaczcie same wielokrotności 24 jak i same wielokrotności trzynastek to Policzmy Ile jest 20 trójek to jedna O.S.T.R są to 3 razy 4 20 drugi Policzmy Ile jest trzynastek No to minus jedna No to minus 3 to już to minus 4 i to minus jedna przenoszona przez 3 czyli jeszcze minus 3 minus 7 trzynastek Czyli to co nam wyszło babcię 4 jest liczbą x minus siedem jest liczbą y czyli dla problemu przelewanie wody wyszło nam że należy 4 lat razy wlać do pojemnika wodę wiaderkiem pojemności 23 litry i potem 7 razy ująć trzynastką i uzyskamy z tego jeden litr wyszło nam rozwiązanie tego równania prawda że proste prawda że piękne więc teraz spróbujmy podejść do tego nie całego rytmicznie jakby napisać program jakby napisać algorytm jak działoby algorytm który by to za nas robił No bo takie równania sobie wykorzystywanie kolejnych równań i pisanie na kartę tez jednak troszeczkę co innego niż algorytm prawda a Więc zacznijmy od dołu tak jak nam powstawały te A jak tam były potrzebne te równania przy obliczaniu tych tego równania z faktycznego i dojdziemy do w takiej sytuacji że będziemy wiedzieć już jasno i wyraźnie że 24/4 A13 jest minus 7 czyli będziemy chcieli na każdym kroku kompletować sobie jakieś xy tak żeby na każdym kroku takiego typu równanie uzyskiwać takie jak jest trzecie teraz od góry że jeden to jest jedna dziesiąta i odjąć 3 trójki na każdym kroku możemy zapisać że 1 równa się pewne x dla naszego bieżącego a lub pewne y do naszego bieżącego b i A z tych x-ów i Greków takich cząstkowych na końcu wyjdą na mixy yit docelowe które teraz Widzicie na ekranie czyli 4e minus 1 którego możemy zacząć czyli rekurencyjne musimy zacząć od tego że to wykorzystamy tą rekurencję czyli moment kiedy nam się a i b zamieniają oblicza nam się wodę dopiero na końcu kiedy wyjdzie nam nwd możemy zacząć liczyć xy czyli przy wyjściu z tych referencji będziemy tej chwili gratis wracać do funkcji która nas wywołała i tak dalej i tak dalej na końcu funkcja która wywołała wszystko otrzyma gotowe x i y No to do dzieła na końcu mamy br232 równa 1 i nasza reszta jest zero Czyli co wiemy wiemy że B jest naszym budę tak Czyli b przenoszone przez jeden plus klips jeśli po drugiej stronie równania mogą stać nasze nude prawda Czyli jest 0 trójek No nie ma innego wyjścia cokolwiek to będzie wa będzie tego zero i będzie dokładnie jedno b bo to będzie znacznym lub nwd po to żeby po lewej stronie wyszło nam jednym prawda No i równanie dla danej linii dla danego wywołania musi działać więc działa i mamy idziemy dalej w drugim równaniu też jest sytuacja dosyć prosta bo ono już wygląda dobrze teraz punktu widzenia tego co chcemy uzyskać czyli tym razem naszej jeden to się równa jedna dziesiątka i minus 3 trójki prawda i to już było tam napisane i nadal jedno razy 10 jest 10 min 91 czyli nasze równanie diofantyczne nadal działa dla danych naszych a i b No to teraz idziemy do kolejnego wiersza i chcemy zobaczyć ile 13 jest potrzebne i ile jest dziesiątek potrzebne żeby to wyszło jeden domek i tu mamy trzynastek tak naprawdę mamy jedną przydawkę tak ale zobaczcie Ona jest przecież przenoszona przez 3 bo u dołu mamy trójkę mil przez minus 3 nawet minus 3 razy 3 i my tą 13 minus 1 razy 10 będziemy chcieli chcieliśmy przed chwilą jakby prowadziliśmy sobie to równanie 13 minus 1/10 wdrożyliśmy przez minus 3 tak przed nawiasem stało minus 3 a w nawiasie było 13 minus 1/10 więc mamy tak naprawdę minus 3 trzynastki prawda nigdzie więcej narazie w naszym równaniu na tą chwile kiedy wykorzystaliśmy Te dolne i to drugie nie było żadnej innej klatki minus trzynastki ile mamy tu dziesiątek na pewno jedna bo na dole w tym pierwszym równaniu już się pojawiła ale dalej to jest jeszcze minus jedna dziesiątka jest na przenoszona przez minus 3 więc jeden plus minus 1 razy minus 3 to jest na plusie 4 na plusie 3 1/3 to jest 4 czyli cztery dziesiątki czy to się zgadza 4 razy 10 40 minus 3 razy 1339 jest jeden Czyli znowu nasze równanie dla danej linii wszystko jest w porządku przejdźmy do kolejnej ostatni A ile tu mamy 20 trójek i ile tu mamy trzynastek więc 20 trójek normy wygląda że jedną tak ale zwróćcie uwagę że to jest 10 równa się 23 minus 1 teraz 13 a ile mamy w naszym stałym równaniu gdybym to na dole znajduje było ile mamy tych dziesiątek to jest informacja ile mamy dziesiątek prawda yu4 Mamy dziesiątki do tej pory więc naszych dwudziestek trójek będzie 4 nie mniej nie więcej Zauważcie że w każdym kroku w ilość a jest równe ilości b z poprzedniego kroku Czy to jest dziwne czy to jest czy to jest reguła tak to jest reguła ponieważ nasze a się to dopiero pojawia tak I ono tyle ile go tu mamy 323 X1 tak na pewno jest teraz 1-23 X1 tyle ile go tu mamy nie ma innej opcji żeby to było ileś pracy 23 to jest zawsze 20/1 prawda bo to jest 10 równa się 23 minus No tutaj jest a przez b razy coś tam Tak ale tutaj zawsze mamy 23 na zawsze nasze a więc nasze A i teraz jak to jest być całe w nawiasie wcale 23 minus 113 całe w nawiasie podstawione gdzieś do wzoru razy coś no to my musimy wiedzieć tylko i wyłącznie razy co A teraz co jest opisane teraz w poprzednim jednej ręku prawda nie ma siły to tak musi być No dobrze więc ile mamy teraz przejdźmy do odpowiedzi ile mamy trzynastek więc wygląda na to że tak 213 jest wzorze do tej pory No jest prawda jedna 13 minus 1 razy 10 ale to wszystko jest naszą trójką jest przenoszone przez minus 3 czyli mamy minus 3 trzynastki minus 4 trzynastki Dlaczego Dlatego że jest też w naszej dziesiątce minus 1 razy 13 i wiemy że mamy 4 dziesiątki dotąd tak Czyli minus 4 i jeszcze czyli razem minus 7 13 i uzyskaliśmy to co chcieliśmy czyli nasze równo rozwiązanie równania diofantycznego nasze a jest czwórką nasze B1 nasze x jest twórcą nasze y jest minus minus siódemką to teraz przejdźmy do wzorków Bo w programie w naszej rekurencji będziemy potrzebowali wzorów tak jak już powiedzieliśmy x y są brane bezpośrednio z poprzedniego y a czyli każdy ich jest poprzednimi grekiem czyli nasza rekurencja będzie musiała wrócić y żeby nowe ich powstało było tego x też będzie musiała zwrócić jak się domyślacie czyli zwracać będzie parę liczb tak czy ewentualnie możemy też nie zwracać tylko na przykład działać na globalnych tak żeby czyli tylko musimy po prostu pracować na tych samych xy Ach co poprzednia rekurencja tak mamy je wykorzystujemy więc x nasze bieżących bieżącej linię spoko my2 Czym jest poprzedni Czym jest bieżący y Zobaczcie bieżącej y to jest poprzedni x a minus nasze a podzielone przez by to jest na czerwono teraz ta jedynka Spójrzcie na ostatnią linią lecz na tą pierwszą od góry Jak liczyliśmy to jeszcze pamiętamy Mam nadzieję że będzie nam łatwo dojść do tego dlaczego ten wzór działa więc nasze y to jest przedmiejskiej minus 3 w tym momencie tak bo najpierw jak pytaliśmy ilość 13 kto zauważyliśmy że są minus 3 trzynastki do tej pory bo to mamy winni poniżej obliczone tak na tamtą chwilę były minut czy trzynastki więc nasze x poprzednia jest to potrzebne to oglądam przechowuje informacje o tym ile jest poprzednio 13 bo to co teraz jest b proszę nie było a prawda No i teraz co potrzebujemy co potrzebujemy nasze to pa przez b razy poprzedni y czyli oprócz tego nasza cała dziesiątka Która teraz jest tutaj jest minus 1 razy 13 to jest nasze a przez b prawda i ono jest minusem bo przecież od 23 Musimy odjąć 1 razy 13 prawda No więc Potrzebujemy wiedzieć ile jest tych 13 ile to się tych trzynastek zmieściło w [Muzyka] a w naszej 23C tym razem jedna więc minus to jeden razy i teraz y poprzednie przechowuje Ile było z życia podstawiamy za taką trzynastkę prawda Czyli tak to robiliśmy prawna na każdym kroku tak to robiliśmy czyli podejmowali się od poprzedniego iksa nasze tak de facto a przez b przenoszone przez poprzednie y jest to trudne prawda jest to trudne do wyprowadzenia do zrozumienia dlaczego ale na maturze dotąd raz się pojawił ten algorytm roku 2015 w rozszerzonej wersji euklides a z pojawiło się zadanie arkuszu pierwszym teoretycznym i ten algorytm był tam opisany te wzory były tam przedstawione oczywiście twórcy podstawy programowej umieścili go w podstawie programowej wiedząc że on jest trudny ja próbowałam go spróbowałam starałam się tej próby przedstawić wam go dlaczego on działa ale wy musicie tak dokładnie wiedzieć dlaczego on działa tylko wiedzieć jaką działa tak że tutaj No to regulacyjne wywołania powodują że znajdujemy największy wspólny dzielnik a wyjścia z tych rekurencyjnych powołań ze zwracaniem jednoczesnym wartości x i y dla każdego kroku posłużą nam do kolejnych obliczeń kolejny chipsów i Greków i na końcu z tego wszystkiego uzyskamy docelowy x i y czyli to jest cały algorytm w pełnej krasie i on również zostało w zadaniu maturalnym przedstawione w całości także nie stresuje się że to jest coś trudnego Zobaczcie jeszcze do program ten program rzeczywiście nie zwraca pary to jest funkcja nwd która jest rekurencyjna tak ale ona z nie zwraca nic to jest funkcja tych właściwie procedura Void tak Masz parametry nasze a i b dopóki B jest różne od zera wywołuje Nutella b i reszty z dzielenia i x i y oraz też poprzedni y są zmiennymi globalnymi załatwienia zapisu i teraz poprzedni y jest wykorzystywany do tego żeby obliczyć nowe y No i na końcu zapytaliśmy zapamiętaną wcześniej zmianą w poprzednim roku wstawiamy do ich za bo to wszystko ładnie przechodzi prosta funkcja cztery linijki w Gwarantujemy że działa Hej Mam nadzieję że on dbał się spodobał Dziękuję bardzo za udział w kolejnym moim filmiku i do usłyszenia Polecam się na przyszłość i zachęcam do oglądania kolejnych innych materiałów