Chotkos's Blog

Programowanie i informatyka

Zlecenia

Coraz częściej widzę że poszukujecie na moim blogu informacji dotyczących różnych dziedzin programowania lub odpowiedzi do zadań z informatyki. Jeżeli masz jakąś pracę domową z zakresu programowania C++/Pascal/html/php to napisz do mnie na chotkos[małpa]gmail.com ustalimy cenę za jaką je wykonam 😉 Nie bójcie Się nie gryzę.

Pozdrawiam Chotkos

Październik 2, 2010 Posted by | Algorytmy, Dla zielonych, Doświadczenia, Informatyka ogólniej, Konkursy, Perełki, Programowanie, Uncategorized | , , , , , , , , | Dodaj komentarz

Algorytmy sortowania

Może kilka osób uzna że to niepotrzebne bo sortowanie to fundamentalna podstawa, ale jeśli ktoś jeszcze nie zna tych metod, albo chce się nauczyć znalazłem odpowiedni artykuł:

ALGORYTMY SORTUJĄCE
Algorytmy sortowania są jednymi z najbardziej znanych algorytmów. Ponieważ proces sortowania jest bardzo ważny w dzisiejszym oprogramowaniu tak więc powstało wiele algorytmów, które lepiej lub gorzej rozwiązują ten problem. Sortować można nie tylko tablice, ale także inne struktury danych, chociażby na przykład listy.
Cechą charakteryzującą niektóre algorytmy sortowania jest to, że działają one w miejscu. Znaczy to, że w czasie procesu sortowania tylko stała liczba elementów tablicy wejściowej jest przechowywana poza nią. Tak więc algorytmy, które nie działają w miejscu wymagają dodatkowej pamięci.
Najważniejszym chyba parametrem, który określa algorytmy sortowania jest ich złożoność. Można udowodnić, że dolna granica złożoności algorytmów, które porównują elementy tablicy wejściowej wynosi n*lg n. Granica ta może być przekroczona przez algorytmy, które nie wykonują porównań. Takimi są na przykład: sortowanie poprzez zliczanie, pozycyjne, kubełkowe. Najbardziej uniwersalnym i w większości przypadków najszybszym jest algorytm QuickSort. Inną jego zaletą jest jego prostota i zwięzłość.

Sortowanie kubełkowe, sortowanie koszykowe(angielskie bucket sort) Jest to sortowanie, w którym przedział sortowanych liczb (o rozkładzie jednostajnym, co jest założeniem) dzieli się na n podprzedziałów jednakowej długości (kubełki), sortuje zawartość kubełków, a następnie przegląda się po kolei kubełki i wypisuje uporządkowany ciąg liczb.

Sortowanie kubełkowe (bucket sort) to algorytm, działający w czasie liniowym (O(n)). Liczby przeznaczone do tego sortowania powinny być liczbami z przedziału [0;1) i powinny być dosyć równo rozłożone w tymże przedziale. Cały algorytm opiera się na podziale przedziału [0;1) na pewną ilość równych podprzedziałów, tzw. kubełków. Następnie każda z liczb przeznaczona do sortowania jest „wrzucana” do odpowiedniego kubełka. Aby otrzymać posortowane liczby najpierw sortuje się liczby w każdym z kubełków, a następnie łączy się je wszystkie po kolei.Do reprezentacji kubełków najlepiej jest użyć struktur danych zwanych listami. Jako algorytmu do sortowania kubełków można użyć sortowania przez wstawianie. Mimo, że ma on złożoność O(n2) to ogólnie sortowanie kubełkowe ma złożoność O(n). Wynika to z tego, że dane wejściowe są równomiernie rozłożone w przedziale [0;1).W przypadku, gdy mamy do posortowania liczby spoza przedziału [0;1) to należy każdą z nich podzielić przez sumę największej liczby w danych ciągu i liczby 1. W ten sposób wszystkie liczby będą w zadanym przedziale. Należy dodać w tym przypadku 1 do największej liczby, bo gdy będziemy dzielić właśnie ją to otrzymamy liczbę 1, a ta liczba do przedziału podanego wyżej nie należy.

Sortowanie bąbelkowe(angielskie bubble sort),
Jest to sortowanie polegające na przeglądaniu po kolei elementów porządkowanego ciągu i zamienianiu miejscami sąsiadujących elementów tak, aby spełniały relację porządkującą; w ten sposób elementy mniejsze (“lżejsze”) przesuwają się na początek ciągu.Dla n elementów ciągu złożoność sortowania bąbelkowego wynosi O(n2). Sortowanie bąbelkowe jest sortowaniem stabilnym.
Bardzo często, pisząc program, mamy do czynienia z problemem nieposortowanych liczb. Mamy tablicę pełną liczb, ułożonych w różnej (np. losowej) kolejności i chcemy posortować ją, tak, że najmniejsze elementy będą na początku, największe zaś – na końcu tablicy. Możemy to zastosować najprostszy chyba sposób sortowania – sortowanie bąbelkowe. Nazwa wzięła się stąd, że algorytm przesuwa „cięższe” (czyli większe) „bąbelki” (liczby) na koniec. Tak jakby spadały.
Napisanie programu sortującego dziesięcioelementową tablicę jest bardzo proste. Potrzebne są (oprócz tablicy) trzy dodatkowe zmienne: dwie liczbowe (licznik dla pętli i tymczasowe przechowywanie liczby) i jedna logiczna (boolean – jeśli algorytm „zauważy”, że dwie stojące obok siebie liczby są w złej kolejności ustawia wartość „false” dla tej zmiennej). Na początku trzeba napisać pętlę repeat, którą ma zostać zakończona, kiedy zmienna logiczna (nazwijmy ją posort) przyjmie wartość true. Następnie, po kolei, od pierwszego do przedostatniego elementu „przechodzimy” tablicę. Jeśli napotkamy sytuację, w której następna (względem aktualnie ustalonej) liczba jest mniejsza od aktualnej, ustawiamy posort na false (tablica nie jest jeszcze posortowana) i zamieniamy te dwie liczby miejscami. Przed całą pętlą „przechodzenia” tablicy, na samym początku pętli głównej ustawiamy (koniecznie!) posort na true i dopiero kiedy okaże się, że tablica jest nieposortowana, zmienna ta zostanie ustawiona na false. Jeśli tablica będzie posortowana, wartość zmiennej pozostanie true i pętla się zakończy.

Sortowanie bąbelkowe z kresem górnym
Może się zdarzyć sytuacja, gdy tablica będzie już uporządkowana, zanim zrobimy n-1 przebiegów lub po k przebiegach więcej niż k liczb od końca będzie na swoim miejscu. Ten problem także da się ominąć. Wystarczy do naszego programu wprowadzić zmienną, która będzie reprezentować w której pozycji nastąpiła ostatnia zamiana elementów tablicy. Ta zmienna to jakby kres następnego przebiegu. Ten wariant sortowania nazywa się sortowaniem bąbelkowym z kresem górnym.

Sortowanie przez wybór(angielskie selectsort)
Jest to sortowanie, w którym w każdym kroku algorytmu znajduje się najmniejszy element w sortowanym ciągu, po czym przenosi się ten element na kolejną pozycję do ciągu wynikowego (przez zamianę elementów miejscami).

Sortowanie przez wstawianie(insertion sort)
Sortowanie przez wstawienie to algorytm, którego czas działania wynosi O(n2). Jest on skuteczny dla małej ilości danych. Jest to jeden z prostszych i jeden z bardziej znanych algorytmów sortowania. Jest on stabilny i nie wymaga dodatkowej pamięci (działa w miejscu). Często stosujemy go podczas gry w karty, biorąc je ze stołu. Biorąc po jednej karcie ze stołu wstawiamy ją w odpowiednie miejsce do kart, które mamy w ręce.

Sortowanie przez zliczanie(counting sort)
Sortowanie przez zliczanie jest jednym z najszybszych algorytmów sortowania danych, a przy tym bardzo prostym do wytłumaczenia. Algorytm ten działa w czasie O(n), tak więc jest to sortowanie w czasie liniowym. Mimo swoich zalet, sortowanie przez zliczanie ma swoje dwie poważne wady. Po pierwsze – do tego sortowania potrzebna jest dodatkowa pamięć(czyli nie jest to sortowanie w miejscu), a po drugie – tym sposobem można sortować tylko liczby całkowite z określonego przedziału. Niewiadomo dlaczego, ale algorytm ten mimo swojej prostoty nie jest powszechnie znany, a tym bardziej używany.
Sortowanie pozycyjne(radix sort)
Stosowane jest do sortowania elementów, które składają się z szeregu pozycji (mogą to być liczby, gdzie pozycjami są poszczególne cyfry; wyrazy – w tym przypadku są to poszczególne litery; mogą to także być inne dane, np. daty). Algorytm ten wymaga użycia innego algorytmu sortowania podczas swego działania, co ważne sortowanie to musi być stabilne. Gdy jako dodatkowego algorytmu sortowania użyjemy sortowania przez zliczanie to algorytm sortowania pozycyjnego działa w czasie O(n). Sortowanie pozycyjne stosuje się nie tylko do sortowania liczb, czy wyrazów. W ten sposób możemy także sortować np. daty. Musimy jednak pamiętać, aby sortować od pozycji najmniej znaczących. W przypadku dat – najpierw sortujemy je według dni, potem według miesięcy, a na końcu według lat. Sortowanie pozycyjne możemy także zastosować do sortowania rekordów baz danych. Na przykład chcemy posortować książkę telefoniczną według nazwisk, a w razie gdyby się one powtarzały to według imion, a w przypadku identyczności imion i nazwisk według numeru telefonu. Aby otrzymać taki wynik powinniśmy tą książkę telefoniczną posortować najpierw według numeru telefonu, potem według imion, a na końcu według nazwisk. Złożoność obliczeniowa takiego sortowania pozycyjnego na pewno nie będzie O(n). Wynika to z tego, że do posortowania np. nazwisk trudno jest użyć sortowania przez zliczanie.

Sortowanie wyrazów
Z sortowaniem wyrazów jest podobnie jak z sortowaniem liczb. W tym przypadku pozycjami są poszczególne litery danego wyrazu. Jednakże jest pewna różnica jeśli chodzi o sortowanie wyrazów różnej długości. W tym przypadku odpowiednią ilość znaków dopisujemy za wyrazem, a nie jak to było w przypadku liczb – przed. Znak ten musi być traktowany jako wyżej w alfabecie, niż wszystkie inne – może to być na przykład spacja.

Sortowanie QuickSort
Jest to jeden z najpopularniejszych algorytmów sortowania. Wpłynęły na to dwie rzeczy. Po pierwsze jest ono bardzo szybkie (jak sama nazwa wskazuje), a po drugie – proste do wytłumaczenia i implementacji. Pesymistyczny czas jego działania wynosi O(n2), a średni O(n*lg(n)). Mimo tego w praktyce jest to najszybszy algorytm sortowania dużych tablic danych.
Sortowanie szybkie opiera się na technice „dziel i zwyciężaj”. Wejściowa tablica jest dzielona (po przestawieniu niektórych z jej elementów) na dwie mniejsze. Każdy element pierwszej tablicy nie jest większy niż każdy element drugiej tablicy. Liczbę, według której wykonuje się podziału to najczęściej pierwszy element tablicy. Następnie dla tych dwóch podtablic wywoływany jest rekurencyjnie ten sam algorytm. Wywołania rekurencyjne kończą się aż któraś z kolejnych podtablic będzie zawierała tylko jeden element. QuickSort działa w miejscu.
Inna odmiana QuickSort
Wyżej wspomniane jest, że algorytm szybkiego sortowania ma pesymistyczny czas działania O(n2). Występuje to w przypadku, gdy tablica wejściowa jest posortowana odwrotnie, tzn. jej wyrazy stanowią ciąg nierosnący.

Przykłady implementacji qsort w różnych językach

Źródło

Styczeń 26, 2010 Posted by | Algorytmy, Dla zielonych | | 3 komentarze

Prawdopodobnie…

W tym momencie kodzisz już pierwszy program, lub jeżeli ci nie idzie to szukasz pomocy na forach itd. Czasem opłaca się zakupić książkę co do Pascala to nie wiem co mogę polecić, widziałem kiedyś u kolegi podstawy Pascala wydawnictwa Helion ( chyba! ), natomiast jeżeli chodzi o C++ to jestem bardzo zadowolony z dwutomowej księgi „Symfonia C++” Jerzego Grzesiaka – naprawdę mądrze zainwestowane pieniądze.

Mam też dobrą informację dla Mazowszan ( czyli swoich ) oraz Ślązaków. Od chyba poprzedniego roku ruszyła akcja Mazowieckie Talenty – zajęcia ze studentami odbywające się co kilka tygodni w soboty w kilku większych miastach. Sam na nie chodzę i jestem bardzo zadowolony. Informacje Formularz http://mtalenty.wikidot.com/ warto obserwować stronę http://www.oi.edu.pl/ bo tam włąśnie pojawia się info o rekrutacji. Co do Ślązaków http://mokip.wikidot.com/ powinno wam pomóc. Poza tym zawsze służę pomocą (choć często z małymi opóźnieniami )

Styczeń 14, 2010 Posted by | Dla zielonych | | Dodaj komentarz

Kompilator

Teraz kiedy już wybrałeś jeden z poniższych języków i dobrałeś się do kursu zapewne zadałeś sobie pytanie: ” Ja mam to w notatniku pisać?!”

Spokojnie już odpowiadam – oczywiście że nie, podrzucam wam tutaj kilka linków do kompilatorów:

  • Pascal
  1. Free Pascal (FPC)
  2. Turbo Pascal
  • C++
  1. Dev C++
  2. Microsoft Visual C++ 2005

Zanim zaczniesz ich szukać w sieci poczekaj – jeżeli chodzi o Pascala to Turbo Pascala podałem tutaj w sumie tylko dla picu, absolutnie nie ściągaj tego – jest to przestarzały kompilator z mnóstwem wad i błędów. Free Pascal w najnowszych wersjach jest naprawdę dobry i daje duże możliwości. Co do C++ To w sumie możesz sobie wybrać z dużo szerszej gamy niż ta podana przeze mnie, z tym że na początku wybrałbym dev C++ bo jest jasny, przejrzysty, nie wymaga tworzenia jakichś cudów i ogólnie jest wygodne, poza wcięciami w kodzie które lubią poszaleć…

„Ale osssoo chossszi?”

Blondynka w jakimś kawale spytała „A po co mi tu jeszcze komplikator”, już rozjaśniam sprawę – kompilator, a raczej środowisko programowania którego kompilator jest elementem służy do pisania programów z różnymi ułatwieniami jak kolorowanie kodu, poszukiwanie błędów i inne przydatne opcje których nazw dzisiaj nie skojarzysz. Kompilator służy do przerobienia twojego kodu w danym języku na postać binarną .exe którą zrozumie komputer. Im lepszy wybierzesz tym wygodniej będzie ci się pisało i przyzwyczajało do gorszego też 😉

Styczeń 14, 2010 Posted by | Dla zielonych | | 2 komentarze

Podstawy

Dobra, jedziemy!

~ Fakty są jasne – z książek w swojej podstawówce (!?)*,gimnazjum czy nawet liceum nie nauczysz się niczego konkretnego – olej to dopóki się nie dałeś wkręcić. Fakty są jasne, naprawdę znajomość exela, worda, painta i powerpointa, oraz szósta na koniec roku za to że umiesz cokolwiek napisać w htmlu i wgrać na pierwszy lepszy darmowy serwer nie jest podstawą do nazywania się informatykiem. Tak naprawdę to wszystkie te rzeczy są poniżej chociaż normalnego poziomu. Pisząc tego bloga mam nadzieję że nie jesteś absolutnym kretynem i word czy exel nie stanowi dla ciebie problemu – jeżeli jednak stanowi, no cóż, jest prostsze rozwiązanie, naciśnij magiczną kombinację alt+f4 i tam gdzie trafisz ćwicz swoje umiejętności.

~Skoro już pozbyliśmy się dzieci neo i innych pokemonów z bloga zacznijmy zajmować się innymi sprawami. Musisz się liczyć z tym, że od tego momentu tak prozaiczne rzeczy jak program obliczający kwadrat liczby czy inne pierdoły tego typu naprawdę będą cię cieszyć, szczególnie dlatego, że będzie to twoje dzieło. Po pewnym czasie jednak dotrzesz do gorszych sytuacji jak np. sześć godzin myślenia i kodzenia i brak wyników, hektolitry wypitej kawy, przekrwione oczy, problemy ze snem i inne równe przyjemne i radosne sprawy ;] Ostrzegam! Do programowania potrzeba uporu, uporu i jeszcze raz uporu!

~ Początki są dosyć banalne – należy dokonać wyboru języka programowania i skołować odpowiednie materiały do jego nauki, oraz kompilator ( o którym powiem za chwilę)

~ Język to podstawa – musisz dokonać wyboru, w chwili obecnej masz do wyboru dwa znaczące cokolwiek języki od których można spokojnie zacząć. Zaczniemy od tego prostszego – Pascala. Pascal to język dosyć stary i niezbyt już na topie, jest o tyle wygodny że angielska w dużej mierze składnia pozwala szybko się połapać. Jeżeli nie czujesz się za mocno i boisz rzucić na głęboką wodę wybierz Pascala. Jednak prędzej czy później musisz przerzucić się na C++ który może wydawać się nieco bardziej skomplikowany, ale szybko okaże się że jest dosyć czytelny i nawet przyjemny w użyciu, a już na pewno bardziej funkcjonalny. Ponieważ niczego nie narzucam – wybierz sam:

Kurs Pascala

Kurs C++

* jeżeli jesteś w podstawówce, to weź sobie puki co daruj, no chyba, że naprawdę ci zależy – ale ostrzegam to nie takie proste jak myślisz.

Styczeń 14, 2010 Posted by | Dla zielonych | | Dodaj komentarz

Witam

Tak też się stało – po długiej batalii z samym sobą postanowiłem założyć (kolejnego) bloga, tym razem sprawa o programowaniu i informatyce, mam nadzieję że nie wyjadę poza temat.  Tymczasem mam jasny plan wyborczy na następne kilka miesięcy prowadzenia tego bloga:

1. Dla Zielonych – pisanie porad dla zielonych w programowaniu jak i tych nieco lepszych, polecanie zadań i materiałów.

2. Programowanie – Tutaj właściwie szerzej o problemach trochę bardziej zaawansowanych, oraz związanych z programowaniem sprawach takich jak porównania języków, kompilatorów, znane i nieznane chocki z tym wszystkim.

3. Algorytmy – Wyjaśnienia wybranych zagadnień algorytmicznych.

4. Doświadczenia – Zapewne pojawią się tu serie mindfu*ków z serii „myślałem pół dnia i następnego dnia rano okazałao się że przecież…”

5. Informatyka ogólniej – Newsy z branży.

6. Konkursy – Olimpiady i zmagania związane z programowaniem i informatyką. Ich opisy, rozwiązania, terminarze.

7. Perełki – Czyli śmieszne bonusy na rozluźnienie.

8. Uncategorized – wszystko co nie zmieści się wyżej.

To może być coś? Może się przydać? No to zapraszam do śledzenia bloga.

Styczeń 14, 2010 Posted by | Algorytmy, Dla zielonych, Doświadczenia, Informatyka ogólniej, Konkursy, Perełki, Programowanie, Uncategorized | | Dodaj komentarz