http://adi.jogger.pl/Wpisy z dziennika internetowego Jogger, wspomaganego przez JabberaThu, 23 Feb 2012 14:04:17 +0100JoggerPLhttp://creativecommons.org/licenses/by-nc-sa/2.0/http://feedproxy.google.com/~r/JoggerAdiego/~3/WMIZBPftOB4/Problemem z klasycznego repertuaru podstawowych zadań w jakimś języku programowania jest np. szukanie liczb doskonałych w danym przedziale (od 1 do jakiejś liczby naturalnej). Kiedyś też to musiałem pisać na wprowadzeniu do programowania (to, co napisałem (metoda klasyczna) wlokło się jak mucha w smole). Nawet mnie się kiedyś o ten algorytm koleżanka pytała. Dzisiaj, na poczekaniu, z nudów wymyśliłem szybki algorytm realizujący to zadanie. Postanowiłem się nim podzielić. Klasycznym sposobem podchodzenia do zagadnienia jest szukanie liczb doskonałych z definicji, tj. dla każdej liczby z danego zakresu szuka się np. jej dzielników poza jedynką i sprawdza się, czy ich suma jest równa danej liczbie odjąć jeden. Niektórzy zauważają, że dzielniki wystarczy szukać dla części całkowitej pierwiastka z danej liczby (dlaczego?) i brać do sumy zarówno ten dzielnik, jak i wynik dzielenia liczby przez niego (jeżeli dzielnik jest równy temu pierwiastkowi, to bierze się tylko jego). Niektórzy jeszcze zauważają, że jako iż nie wiadomo, czy liczba doskonała nieparzysta istnieje, a nawet jeśli istnieje to przekracza 10300 (patrz OddPerfect.org), tak więc można z badanego zakresu wyrzucić wszystkie liczby nieparzyste. Mimo tych zabiegów czas szukania będzie bardzo duży i najprawdopodobniej prowadzącemu laborki się to nie spodoba ;) Algorytm, który przedstawiam opiera się na liczbach pierwszych Mersenne'a. Mianowicie każdą liczbę doskonałą parzystą (nieparzyste, jak wiemy, nawet jeśli istnieją, możemy odrzucić) można przedstawić w postaci 2**(p-1) * (2**p - 1) ("**" oznacza potęgowanie), gdzie drugi czynnik jest właśnie liczbą pierwszą Mersenne'a (żeby liczba tej postaci była doskonała, drugi czynnik musi być liczbą pierwszą). Wyznaczając p, znajdziemy, że wystarczy rozpatrywać zakres, którego maksymalną liczbą będzie int(round((log(n, 2) + 1) / 2)), gdzie "int" to część całkowita liczby (używane również do konwersji liczb zmiennoprzecinkowych typu 1.0 na całkowite), "round" to zaokrąglenie, "n" to maksymalna liczba badanego zakresu, a "log(n, 2)" to jej logarytm o podstawie 2 (binarny, zresztą najczęściej stosowany w informatyce). Tak więc zamiast sprawdzać np. milion liczb, sprawdza się dziesięć. Klasyczna metoda sprawdzania także jest nieefektywna (dla liczby rzędu miliona mamy liczbę operacji rzędu tysiąca). W przedstawionej prze ze mnie metodzie wystarczy sprawdzić, czy ta liczba Mersenne'a jest liczbą pierwszą. Dokonuje się tego za pomocą testu Lucasa-Lehmera (tak, to ten Lucas, co wymyślił wieże Hanoi). Polega on na tym, że najpierw definiuje się funkcję S(x) daną rekurencyjnie (w kodzie jest zrealizowana iteracyjnie; dlaczego, patrz: derekursywacja): S(1) = 4 S(n+1) = S(n)**2 - 2 Liczba M postaci (2**p - 1) jest pierwsza, jeżeli S(p-1) % M = 0. Symbol "%" (modulo) oznacza resztę z dzielenia. W kodzie zastosowano właśnie operowanie na resztach z dzielenia, zamiast na wartościach funkcji S(x), gdyż są dużo mniejsze. Test wykonuje się dla liczb nieparzystych p > 1, tak więc zredukowany zakres zaczyna się od 3 i usuwane są z niego wszystkie liczby parzyste. Ponieważ liczba 2**2 - 1, czyli 3 jest także pierwsza, do listy wynikowej dołączana jest liczba doskonała uzyskana z niej (6, ale nie jest zapisana wprost, gdyż prowadzący laborki mógłby się wkurzyć, a poza tym tak to można dołączyć ich bardzo dużo, a tu nie o to chodzi ;). Chyba starczy tego wstępu teoretycznego. Oto kod algorytmu w języku Python: from math import log # Liczba pierwsza Mersenne'a M = lambda x: 2**x - 1 # Liczba doskonala uzyskana # z liczby M f = lambda x: 2**(x-1) * M(x) # Test Lucasa-Lehmera def S(x): S = 4 for i in range(2, x): S = (S**2 - 2) % M(x) return S # Wlasciwa funkcja przyjmujaca # jako parametr maksymalna # liczbe z badanego zakresu def perfect(n): # Lista wynikowa perfect = [] # Ogranicz zakres poszukiwan p = int(round((log(n, 2) + 1) / 2)) r = range(3, p+1) # Usun wszystkie liczby # parzyste z zakresu i = 4 while i Mon, 25 Sep 2006 22:39:07 +0200http://adi.jogger.pl/2006/09/25/szukanie-liczb-doskonalych/AlgorytmyMatematykaPythonWszystkohttp://adi.jogger.pl/2006/09/25/szukanie-liczb-doskonalych/http://feedproxy.google.com/~r/JoggerAdiego/~3/rrM-vmLaeSU/Jak być może niektórzy zdążyli już zauważyć, w menu pojawiła się pozycja Kontakt. Po sugestii Michała Górnego dodałem to do tej notki. Po Piotrze Koniecznym i Łukaszu Więcku postanowiłem przetestować te cudo, jakim jest meebo. Umożliwia to Wam kontakt ze mną i vice versa (tak więc mogę zagadać do kogoś, kto odwiedza mojego joggera). Wymaga zainstalowanego Flash Playera, ale na czymś to musi śmigać, nie? ;) (na czystym HTML-u nie da się takich rzeczy w końcu zrobić... ;) Też chcesz mieć takie coś na swoim blogu/stronie? Po prostu wejdź na stronę widżetu meebo i postępuj zgodnie z instrukcjami. Można z tego korzystać zarówno przez ichni interfejs internetowy, jak i z Twojego ulubionego klienta Jabbera (JID: login_na _meebo@meebo.org; org, nie com!). A teraz, nie wstydzić się, tylko testować ;) Aha - i zmieńcie sobie domyślne nicki, na jakieś ludzkie ;) Najlepiej takie, żebym od razu wiedział z kim mam do czynienia. Update: Zapewne mnóstwo klientów się im zwaliło, bo są problemy z połączeniem się...Sun, 06 Aug 2006 16:52:38 +0200http://adi.jogger.pl/2006/08/06/porozmawiaj-ze-mna-przez-meebo/Jogger AdiegoWszystkohttp://adi.jogger.pl/2006/08/06/porozmawiaj-ze-mna-przez-meebo/http://feedproxy.google.com/~r/JoggerAdiego/~3/yFDvvpktEFw/Po dość długiej przerwie (studia, sprawy prywatne, zwykłe lenistwo ;) wracam (jako tako, bo pewnie znowu będzie na studiach dużo roboty...) do pisania. Zrobiłem parę zmian: Najbardziej widoczna - zmiana szablonu na Theme Wuhan. Przydałoby się tą grafikę zmienić i favikonkę zrobić... Dodałem kategorie wpisów (w końcu wyszedł Jogger 2.0 ;). Póki co są do grudnia, ale sądzę, że niedługo przypiszę kategorie wszystkim wpisom. Zrezygnowałem z wyszczególnienia w sidebarze kogo czytam. Trochę tego dużo jest i zrobił się lekki syf :P Sądzę, że lepiej będzie, jeśli przygotuję dodatkową stronę, gdzie do linków dodam krótki opis, co się za nimi kryje. Linki do stron na razie zostaną, ale pewnie to też zmienię. Zdecydowałem się skorzystać z FeedBurnera. Wszelkich korzystających z mojego kanału RSS (są tacy? ;) proszę o zmienienie ich adresów. Nowe adresy kanałów: kanał z wpisami, kanał z nagłówkami. Jutro postaram się przybyć na Jogger meeting. Postaram się, bo "nocleg" coś zaniemówił... ;) Ale sądzę, że to chwilowe.Fri, 05 May 2006 15:06:40 +0200http://adi.jogger.pl/2006/05/05/jogger-adiego-2.0/Jogger AdiegoJogger.plWszystkohttp://adi.jogger.pl/2006/05/05/jogger-adiego-2.0/http://feedproxy.google.com/~r/JoggerAdiego/~3/-9F7l7hUVLw/Jako remedium na te wszystkie walentynkowe blubry cytat z mojego ulubionego (sic!) filmu: - Can I hear something in your language? - What shall I say? - I don't know. How about... "I love you." - "I love you" is "Volim te". - ...That's nice. Prawda, że romantyczne i w ogóle? ;) Może ktoś wie z jakiego to filmu? I może jeszcze przypadkiem go oglądał? ;)Sat, 18 Feb 2006 23:55:24 +0100http://adi.jogger.pl/2006/02/18/wale-tynki/OgólneWszystkohttp://adi.jogger.pl/2006/02/18/wale-tynki/http://feedproxy.google.com/~r/JoggerAdiego/~3/tNWo0_gMiok/Naukowcy z ISA/München (Niemcy) opublikowali raport, który potwierdza, że Ziemia może zostać wytrącona ze swojej obecnej orbity przez połączoną siłę skaczących jednocześnie ludzi. Prof. Hans Niesward i jego współpracownicy w Department of Gravitationsphysik w przybliżeniu obliczyli, że potrzeba minimum 600 milionów ludzi na zachodniej półkuli skaczących w tym samym momencie. Oto, co znalazłem na stronie Wykop.pl. Niezłe jaja, zwłaszcza ta "zachodnia półkula" ;) Patrz: strona oficjalna projektu World Jump Day. Toż to reaktywacja kultowego pytania: "Czy gdyby wszyscy Chińczycy skoczyli w tym samym momencie, Ziemia zmieniłaby orbitę?"! Poza tym kłania się flash mob (fajnie byłoby zobaczyć, jak 600 milionów ludzi skacze w tym samym momencie ;). A co na to fizyka? Cóż, Jakub Perelman (radziecki popularyzator nauki) dawno temu (lata 40-te bodajże) w "Zajmującej fizyce" podał absurdalny przykład pokonania siły ciążenia Ziemi w ten sposób, że siedzimy w metalowym pojeździe i wyrzucamy w górę bardzo silny magnes, który przyciągnie pojazd, a wraz z nim nas. Spotkamy się z tym magnesem gdzieś w połowie drogi. Wtedy znowu wyrzucamy magnes w górę, który nas znowu przyciąga, wtedy go znowu wyrzucamy w górę, itd., i proszę, dolecimy tak do gwiazd! ;) Z tym skokiem jest taki sam numer. Trzecia zasada dynamiki Newtona się kłania.Thu, 09 Feb 2006 00:19:03 +0100http://adi.jogger.pl/2006/02/09/world-jump-day/FizykaHumorMiejskie legendyWszystkohttp://adi.jogger.pl/2006/02/09/world-jump-day/http://feedproxy.google.com/~r/JoggerAdiego/~3/G2lW0ah6zjo/Ja rozumiem, że ludzie zginęli na Międzynarodowych Targach Katowickich w Chorzowie, że to, prawda, tragedia i w ogóle, ale żeby zaraz z tego robić żałobę narodową? Panie Kaczyński. Panu i Pańskim szopkom Wszelkim szopkom pod publikę już podziękujemy... Disclaimer: Żeby było jasne. Nie jestem w żadnym wypadku przeciwko żałobie, tylko przeciwko robieniu medialnej szopki z ludzkiej tragedii, a za taką uważam m.in. ogłoszenie żałoby narodowej.Sun, 29 Jan 2006 17:30:15 +0100http://adi.jogger.pl/2006/01/29/zalosne/NarzekaniePolitykahttp://adi.jogger.pl/2006/01/29/zalosne/http://feedproxy.google.com/~r/JoggerAdiego/~3/JFCbrlwwKi4/Wczoraj współlokator (z którym się zresztą znamy już z technikum) stwierdził, że moi przodkowie nie mogą być z Jarocina, gdyż tam nie pasuję. To miasto ma swoje reguły, których ja nie przestrzegam. Nie wyglądam, prawda, jak punk, czy też nie chodzę na festiwale rockowe, czy takie tam rzeczy. Stwierdził, że moi przodkowie (od pradziadka wstecz) ze strony taty (a dlaczego ze strony mamy już nie?) musieli pochodzić tzw. Kresów Wschodnich (tych przedwojennych), np. z Litwy. Stwierdził, że ma jakąś cechę (ponoć pozytywną) charakterystyczną dla ówczesnych ludzi stamtąd i że jest ona tak oczywista i logiczna, że nie powie mi jaką. Tymczasem ja i drugi współlokator, bądź też koleżanka (i zapewne wykładowca od logiki ;), nie mamy pojęcia, o co chodzi. Ciekawe, skąd mu to przyszło do głowy, bo chociażby nazywam się Nowicki, a nie np. Kałakutas ;) Może ktoś z Was wie o jaką to cechę mogło chodzić mojemu koledze? Update: Dzisiaj kolega dał mi podpowiedź: "Katyń". Nie dość, że moich przodków od Litwinów jedzie, to jeszcze pewnie od komunistycznych morderców :PSun, 15 Jan 2006 21:20:25 +0100http://adi.jogger.pl/2006/01/15/litwo-ojczyzno-moja/AdiWszystkohttp://adi.jogger.pl/2006/01/15/litwo-ojczyzno-moja/http://feedproxy.google.com/~r/JoggerAdiego/~3/hYlX-8784-Y/Google Adsense wstawiło na mojego joga reklamę o treści: Rasztów Ośrodek Psychoterapii 40 lat tradycji www.rasztow.pl Ktoś tu coś insynuuje? ;)Sun, 08 Jan 2006 17:46:43 +0100http://adi.jogger.pl/2006/01/08/swir/AdiHumorWszystkohttp://adi.jogger.pl/2006/01/08/swir/http://feedproxy.google.com/~r/JoggerAdiego/~3/0gxoksqNtjc/Pobawiłem się w szukanie za pomocą Google Maps (czy może raczej Google Local) piramid egipskich (jednym z moich licznych zainteresowań jest starożytny Egipt), których jeszcze nie ma w serwisie Świat według Google. Oto, co znalazłem: Piramida Łamana Snofru (Sneferu, gr. Soris) w Dahszur. Nazwa pochodzi od faktu, że mniej więcej w połowie wysokości kąt nachylenia piramidy zmienia się z 54 stopni na 43, dając jej "złamany wygląd. Czwarta co do wielkości piramida egipska. Poniżej widać jej piramidę satelitarną. Czerwona Piramida Snofru (Sneferu, gr. Soris) w Dahszur. Pierwsza piramida w kształcie ostrosłupa. Trzecia co do wielkości piramida egipska - po piramidach Chufu (gr. Cheops) i Chafre (gr. Chefren). Jej nazwa pochodzi od rudo-czerwonej barwy bloków, z których została wzniesiona. Nekropolia w Abusir. Od góry do dołu (po skosie): piramida Sahure, mastaba Ptahszepsesa, piramida Neferirkare, piramida Neferefre. Pomiędzy dwoma ostatnimi piramida królowej Chentikaus II, poniżej piramidy nr 24 i 25 ;) Znaleziska oczywiście zgłosiłem do wspomnianego serwisu. Tytuł to cytat z pewnej bardzo znanej (?) książki.Sun, 08 Jan 2006 15:25:56 +0100http://adi.jogger.pl/2006/01/08/quot-rety-bert-patrzaj-co-upolowalem-quot/EgiptGoogleWszystkohttp://adi.jogger.pl/2006/01/08/quot-rety-bert-patrzaj-co-upolowalem-quot/http://feedproxy.google.com/~r/JoggerAdiego/~3/b0RdtWgt2ck/Nie, nie chodzi tu o muszle klozetowe, a o zespoły trakcyjne EN57 zwane pogardliwie "kiblami". Nowy rozkład jazdy PKP zakłada, że jeden zespół trakcyjny w zupełności wystarczy na trasę Łódź Kaliska - Poznań Główny. Oczywiście nie wystarcza. Tak więc, gdy ostatnio czekałem w Jarocinie na pociąg, najpierw rozdziawiłem paszczę, gdy zobaczyłem, że jedzie "kibel" (dla ciekawych: EN57-1727 ;). Potem, gdy zobaczyłem, że już jest pełen z moich ust wydarło się szczere "O k..wa!". Oczywiście ludzi na peronie było multum... Tak więc najpierw łaziłem wzdłuż jednostki patrząc jak ludzie upychali jedni drugich (dosłownie!) do pociągu. Udało mi się jakoś do niego wepchnąć, korzystając z faktu, że najmniej ludzi wchodzi na samym przodzie i tyle pociągu. Wybrałem tył, bo był bliżej. Nawet tam czuliśmy się jak sardynki w puszce. Tak ciasno nie było nawet, gdy jeździłem "kiblem" z Ostrowa Wlkp. do Jarocina. A wierzcie mi, że wtedy było ciasno... Najbardziej się martwiłem, co będzie jak dojedziemy do Środy Wlkp., która jest dość dużym miastem. Ale nie było tak źle, bo dużo ludzi wysiadało, a ci, co wsiadali, tradycyjnie pchali się w środek. W końcu stwierdziłem, że się dłużej cisnąc nie będę i wysiadłem na stacji Poznań Starołęka (normalnie bym jechał do stacji Poznań Główny), a stamtąd już tramwajem na Rataje i kolejnym do celu podróży. Najgorsze jest to, że w nowym rozkładzie jeżdżą chyba same "kible"... Okropne... :/ No ale nie ma tego złego, co by na dobre nie wyszło i moje czułe ucho mogło usłyszeć nieznajomość praw fizyki wśród ludu ;) Tak więc jedna pani dyskutowała ze swoim facetem, co będzie, gdy pociąg zahamuje. Stwierdziła, że wtedy zadziała na nas siła grawitacji (sic!). Facet oczywiście na to, że ta siła działa na nas cały czas. No to panienka zaczęła strzelać: "siła odśrodkowa", "siła dośrodkowa" (przypominam, że chodzi tu o hamowanie pociągu poruszającego się po linii prostej), oraz najlepsze: "siła doprzodowa" ;) Podobnie zresztą niezbyt się zna na tym nasz instruktor jazdy na nartach (na zajęciach z wychowania fizycznego jeżdżę na nartach w ośrodku Malta-Ski) - tłumaczył nam siły działające na narciarza podczas skrętu (tak poza tym, to z fizyki jest całkiem niezły). Tak więc wg niego są to: siła spychająca (czyli grawitacji), odśrodkowa, oraz wynikająca z dotychczasowego ruchu (zjeżdża się właściwie poprzecznie do kierunku spadku stoku). Swoją drogą, to ciekawie moje skręty wyglądają, bo czasem żeby wyrobić na zakręcie, mam jedną nartę w powietrzu ;) No i na zakończenie pytania do czytających joga ;) Czy przy hamowaniu pociągu działają ba pasażerów jakieś siły, a jeśli tak, to jakie? Gdy już w końcu zahamuje, nagle coś nas pcha w kierunku odwrotnym do kierunku jazdy pociągu. Wyjaśnić to zjawisko. No i oczywiście: jakie siły działają na narciarza w czasie skrętu? Zobaczymy, jak stoicie z fizyki ;)Sun, 08 Jan 2006 14:33:41 +0100http://adi.jogger.pl/2006/01/08/zapchane-kible-oraz-znajomosc-praw-fizyki-wsrod-ludu/FizykaKolejNartyWszystkohttp://adi.jogger.pl/2006/01/08/zapchane-kible-oraz-znajomosc-praw-fizyki-wsrod-ludu/