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

Programowanie Dynamiczne

Być może nie powinno się to znaleźć w kategorii algorytmy, ale jest to jedna z podstawowych strategii w programowaniu, o której bardzo źle byłoby zapomnieć.

Programowanie dynamiczne da się streścić krótkim zdaniem – rozwiązywanie dużego problemu za pomocą wyników dla problemów mniejszych. Najlogiczniej będzie przedstawić to na jakimś przykładzie: wyobraź sobie, że musisz zaplanować trasę dla samochodu od twojego domu do stolicy Maroka – Rabatu. Oczywiście wziąć ogromną mapę i zacząć na niej zaznaczać ścieżkę jest prostym rozwiązaniem, ale niekoniecznie ścieżka którą w ten sposób wybierzesz będzie najszybsza, a poza tym cała ta ogromna mapa byłaby potrzebna w trakcie podróży – i powiedzmy szczerze – dosyć niewygodna. Rozwiązaniem tego programu jest właśnie programowanie dynamiczne. Zacznijmy od wyjechania z naszego miasta – określmy najkrótszą ścieżkę do opuszczenia miasta i ominięcia korków 😉 trasę zaznaczmy na planie miasta, następnie wyznaczmy sobie inny cel, który nie będzie zbyt daleko – powiedzmy naszą zachodnią granicę, wyznaczamy ścieżkę, zapisujemy na małej mapce Polski i przechodzimy do mapy Niemiec, gdzie będziemy udawali się do Francji…

W ten oto sposób mamy w podręcznym bagażu kilka niewielkich, poręcznych mapek z których każda prezentuje najkrótszą ścieżkę – rozwiązanie jest szybkie, wygodne i co najważniejsze – optymalne.

Jak to przełożyć na programowanie? Miałem ostatnio na kółku Mazowieckich Talentów takie zadanie:

http://chomikuj.pl/chotkos/Programowanie/materia*c5*82y/sci.pdf

z tym że robiliśmy je tak aby bezwzględnie zawsze zaczynać od pola [1,1]

Jak to zrobić? Ano właśnie tutaj również mamy programowanie dynamiczne. Nasz program powinien sprawdzać który ruch bardziej mu się opłaca – w prawo, w lewo, czy w dół.

Zaczynamy od pola 1,1 i stajemy w następnym polu które się bardziej opłaca. Trzeba tylko pamiętać, żeby na krawędziach ustawić naprawdę małe liczby typu -1000001; abyśmy nigdy nie wyszli poza naszą pamięć przeznaczoną na tablicę 😉

W tym rozwiązaniu cały czas korzystamy z poprzednich obliczeń i to właśnie jest dynamika.

oczywiście mam rozwiązanie tego zadania, ale prosiłbym go nie czytać bo będzie ono zadaniem do tego tematu 😉

Tak więc zapraszam do sprawdzarki.

Luty 4, 2010 Posted by | Algorytmy, Programowanie | | Dodaj komentarz

Sito Erastotenesa

Dzisiaj omówię bardzo cwany algorytm dot. liczb pierwszych – Sito Erastotenesa. Pozwala on szybko wygenerować tablicę liczb pierwszych w przejrzysty i zrozumiały sposób:

Nasz program polegać będzie na tym iż jeżeli spotka liczbę „nieoznaczoną” to uzna ją za liczbę pierwszą i oznaczy wszystkie jej wielokrotności., jeżeli spotka oznaczoną, to po prostu przejdzie dalej. Może zaprezentuję to na n=10.

kolor czerwony – oznaczona , kolor niebieski – nieoznaczona, kolor zielony uznana za pierwszą.

PS – zawsze zaczynamy od dwójki, bo jedynka zaznaczyłaby nam wszystkie liczby do n 😉

1.

2 3 4 5 6 7 8 9 10 //pusta tablica

2

2 3 4 5 6 7 8 9 10 // wybranie dwójki jako nieoznaczonej

3

2 3 4 5 6 7 8 9 10 //oznaczanie wielokrotności

4

2 3 4 5 6 7 8 9 10 // wybranie trójki jako nieoznaczonej

5

2 3 4 5 6 7 8 9 10  //wykreślamy wielokrotności trójki

(…)

10

2 3 4 5 6 7 8 9 10 //LP z tego ciągu to 2,3,5,7


Wydaje mi się że już wiecie o co chodzi, więc teraz opublikuję kod:

Dla C++ Dla Pascala

Zadanie do wykonania


Luty 3, 2010 Posted by | Algorytmy, Programowanie | , | 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

Rekurencja

„Aby zrozumieć rekurencję, trzeba najpierw zrozumieć rekurencję”

Słowa, które napisałem wyżej, mogą się wydać bezsensowne, ale na tym właśnie polega rekurencja. Zazwyczaj występuje w funkcjach, w których musimy robić coś wgłąb np. jakiegoś grafu, jest to eleganckie i nowoczesne rozwiązanie, chociaż dla niektórych trudne do zrozumienia.

Najprościej rzecz ujmując rekurencja jest wtedy, kiedy funkcja f(x) uruchamia funkcję f(x). Najlepiej zobrazuje to przykład.

funkcja(X)

{

  • powiększ a o 1
  • wypisz a
  • czy a>5 ?
  1. jeśli nie to uruchom funkcja(X)
  2. jeśli tak, to wypisz „nareszcie a=”  a.
  • napisz „costam”

}

kiedy już to przetłumaczycie na jakiś język programowania otrzymacie w konsoli:

1
2
3
4
5
nareszcie a=5
costam
costam
costam
costam
costam

Mogło was zastanowić dlaczego mamy tutaj 5x napisane „costam” i jest to na końcu a nie na początku. Pamiętaj że funkcja po zakończeniu serii rekurencji zacznie zamykać te funkcje które zaczęła wcześniej – myślę, że lepiej zobrazuje to rysunek:

wykres

kolory z wykresu odpowiadają kolorom w kodzie, czerwona kreska pionowa oznacza rekurencyjne uruchomienie funkcji. Kolorem niebieskim zaznaczyłem, gdzie kończy się dana funkcja. Wykres należy śledzić od dolnej czarnej kreski na której ustawiłem tą „piramidę”.

Warto poćwiczyć rekurencję na jakichś zadaniach np. na mainie, u mnie powinno się coś takiego niedługo pojawić w sprawdzarce – jak tylko wpadnę na dobry pomysł 😉

Styczeń 24, 2010 Posted by | Algorytmy, Programowanie | | Dodaj komentarz

Zadanie do bisekcji

Artykuł o bisekcji był nieco wcześniej ale dzisiaj wrzuciłem zadanie – Kolejka. Ogólnie to nie mam niestety dostępu do ograniczeń czasowych ( bo wilibyście się z bólu próbując się w nich wyrobić (-:[ ) dlatego też rozwiązania „na pałę” przechodzą, natomiast dla własnej uczciwości proszę o napisanie ich za pomocą bisekcji – w końcu robimy to żeby się czegoś nauczyć a nie szpanować miejscem w rankingu 😉

Styczeń 22, 2010 Posted by | Algorytmy, Programowanie | | Dodaj komentarz

Reklama?

Szczerze mówiąc nie spodziewałem się, ale moja strona została zareklamowana na http://www.contest.pl dokładniej tutaj.

Ponieważ głupio mi zostawić sprawdzarkę właściwie pustą postanowiłem dorzucić nowe zadanko, do którego macie dostęp tutaj, jeżeli nie dajecie sobie rady to warto przeczytać jeden z wcześniejszych wpisów.

Dziękuję za promowanie bloga, umieszczam Was w blogrollu.

Styczeń 22, 2010 Posted by | Algorytmy, Doświadczenia, Programowanie | | Dodaj komentarz

Wyszukiwanie Binarne – Bisekcja

Dzisiaj poruszę temat wyszukiwania binarnego – o co chodzi?

Problem polega na tym, że mamy jakiś tam ciąg wartości w odpowiedniej kolejności – rosnącej lub malejącej – np. kolejkę w sklepie, w której mamy wózki w zależności od ilości zakupów w środku ustawione rosnąco, tak aby najpierw kupowali klienci którzy mają mało przedmiotów a więc szybciej przejdą w kolejce ( kto czekał kiedyś w markecie na przerwie chcąc kupić jedną bułkę i colę a przed nim jakaś starsza pani z toną przeróżnego śmiecia w koszyku ten wie, że jest to mocno wyidealizowana wizja). W każdym razie wchodzimy do takiego sklepu i pytamy „Gdzie stoi pani z zakupami za 100 złotych” Tutaj właśnie pojawia się problem szybkiego wyszukiwania.

Pierwszym sposobem jaki wpada do głowy jest oczywiście przejrzeć wszystkie wózki i w ten sposób znaleźć właściwy. Oczywiście świat zadań z programowania jest światem czarnych koszmarów więc możecie być pewni że kolejka ma ponad milion klientów, a ten właściwy wózek stoi gdzieś bardzo blisko końca. W tym wypadku złożoność n jest niedopuszczalna bo zależy nam bardzo na każdej setnej sekundy. Szukamy innej metody!

Zacznę trochę z innej beczki. Na początku państwa Rzymskiego Roma nie była wcale potęgą, dopiero mądra polityka umocniła ją w walce o supremację. Wtedy najważniejszą ideą była fraza „Divide at impera!” „Dziel i rządź” O ile starożytni wykorzystywali tą frazę do skłócania przeróżnych ludów i państw na własną korzyść, to w programowaniu wyrażenie to oznacza coś zdeka innego.

Pomyśl że naszą kolejkę dzielimy na dwa sektory od początku do połowy (środka) i od połowy (środka) do końca. Pytamy więc klienta stojącego w samym środku za ile zrobił zakupy

– jeżeli powie że za więcej niż 100 zł wtedy :

  1. koniec staje się środkiem // k:=s;
  2. Środek staje się środkiem między początkiem(p) a końcem // s:= (k-p) div 2 +1;

– Jeżeli powie że za mniej niż 100 zł wtedy:

  1. Początek staje się środkiem // p:=s;
  2. rodek staje się środkiem między początkiem(p) a końcem // s:= (k-p) div 2 +1;

-Jeżeli powie że za 100 zł wtedy

  1. p:=k;
  2. Koniec pętli. //break;

Właściwie to napisałem już cały program, wystarczy go tylko teraz przełożyć na jakiś język programowania a w nim zapętlić to co wypunktowałem.

Oczywiście możecie mi nie wierzyć, dlatego podam przykład, który mam nadzieję pomoże:

Szukamy klienta z zakupami za 2 złote. Oto lista wartości zakupów.

1 2 3 4 5 6 7 8 9 10 11 12 13

Pytamy (13-1) div 2 +1 = 6 klienta o to za ile zł ma zakupy. Okazuje się że za 6 złotych, więc idziemy w lewo.

1 2 3 4 5 6

Pytamy (6-1) div 2 +1 = 3 klienta o wartość zakupów, okazuje się że za 3 złote, więc znów idziemy w lewo.

1 2 3

Pytamy (3-1) div 2 +1 = 2 klienta o wartość zakupów , okazuje się że to ten który kupuje za 2 złote! Był drugi w kolejce!

Oczywiście mam kod, a nawet graficzne wytłumaczenie, wszystko w moim chomiku.

Styczeń 17, 2010 Posted by | Algorytmy, Programowanie | , | 6 komentarzy

Bignumy

Postanowiłem zacząć od dosyć banalnego problemu – od bardzo dużych liczb.

Pomyślicie sobie zapewne „Gdzie leży problem?” A sprawa jest dosyć jasna, pozwolę ją sobie przedstawić na przykładzie.

Pewien bardzo wpływowy szejk, posiadacz roponośnych pól w Arabii Saudyjskiej uzbierał po tym jak drastycznie podrożała ropa na całym świecie naprawdę niebagatelną sumę pieniędzy. Zatrudnił bankierów aby zliczyli jak potężny jest jego kapitał. Bankierzy po długich wyliczeniach ustalili jego łączny majątek na 92233720368547758070 euro. Szejk umarł ze szczęścia. Jedynym spadkobiercą okazał się jego kuzyn z Polski , który uznał, że na potrzeby własnych interesów zamieni tą kwotę na polskie złote.

Napisz program, który przeliczy majątek szejka na złotówki, po podanym przez użytkownika kursie. ( Dla ułatwienia liczby całkowitej)

Zadanie wydaje się banalne – wystarczy tylko 92233720368547758070 pomnożyć przez kurs który poda użytkownik i wypisać. Życzę powodzenia.

Naprawdę zacząłeś to pisać?!  Nie żartuj sobie ;]

Zauważ: INT64 typ zmiennej znany tak w C++ jak i w Pascalu jest ograniczony (w obie strony zera) do:

9223372036854775807

dla porównania liczba z treści zadania to:

92233720368547758070

Ta liczba jest za duża, żeby coś z nią zrobić! Nie zmieści się w pamięci a ostatecznie nasz program wysypie się w trakcie kompilacji – innymi słowy kicha!

Co z tym zrobić?

Mam nadzieję że już na to wpadłeś, jeżeli nie, to zaproponuję ci teraz coś co może wydać Ci się trochę głupie – ile to jest 19824 + 1198 . NIE! Nie odpalaj kalkulatora, ani nie licz w pamięci. Weź do ręki ołówek i oblicz na kartce.

Jak widać liczba, której nie mogłeś łatwo wyliczyć od razu w głowie da się bezproblemowo dodać „pod kreską”. Czemu więc nie przenieść tej reguły na grunt naszego programu!

O czym powinniśmy pamiętać pisząc ten program:

– Tak naprawdę to będzie dodanie do siebie majątku n razy;

– Aby dodawać musimy wiedzieć jak

– W dodawaniu należy zacząć od prawej w lewo aby przenosić wartości wykraczające poza 9

– A, no i najważniejsze – na czym to robić!?

Stringi – ciągi znaków, mają właściwie nieograniczoną pamięć ( jeżeli nie wierzysz to spróbuj je zapełnić, szybko Ci się znudzi) dlatego możemy na nich swobodnie operować dużymi liczbami. Jednak dodawanie do siebie stringów ‚1’+’2′ nie da na upragnionego ‚3’ ale ’12’ bo ciągi się skontaktują.

Tutaj z pomocą przychodzi ascII gdzie cyfry zaczynają się od wartości 48 ( 48 to zero), o tym też należy pamiętać.

Postanowiłem napisać kod dodawania bignumów w pascalu bo jest tam mały chocek z funkcją ord(a[i]):

kod umieściłem pod tamtym linkiem bo niestety zapisywanie kodu na wordpressie leży i kwiczy

http://wklej.org/id/262987/

jest tam funkcja ord(a[i]) – oznacza ona wartość liczbową i-tego znaku ciągu a. Cyfry mają kody od 48 w górę co możecie sobie zobaczyć na wiki, w tabeli ascII

Mając gotowe dodawanie spróbujcie z odejmowaniem, no i oczywiście rozwiążcie problem polskiego szejka ;]

Styczeń 14, 2010 Posted by | Algorytmy, Programowanie | | 4 komentarze

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