piątek, 30 września 2011

Kombinatoryka okiem programisty cz. I


Witam!
Dziś i nie tylko dziś opowiemy sobie o kombinatoryce. Czym jest więc ta kombinatoryka?

Kombinatoryka to teoria obliczania liczby elementów zbiorów skończonych. Powstała dzięki grom hazardowym, a swój rozwój zawdzięcza rachunkowi prawdopodobieństwa, teorii grafów, teorii informacji i innym działom matematyki stosowanej. Stanowi jeden z działów matematyki dyskretnej.

Dla programistów stanowi rzecz równie ważną co algorytmika czy teoria grafów.
Mówiąc w skrócie kombinatoryka zajmuję się zbiorem wyrażeń uporządkowanym. Przykładów zastosowania kombinatoryki jest sporo zwłaszcza w wymienionych powyżej dziedzinach. Opłaca się znać choć jej podstawy by móc powiedzieć ile np. jest możliwych kombinacji liczb w Dużym Lotku. A więc zaczynajmy!
Przykłady będę podawał w 2 językach: Pythonie oraz Haskell'u.
0. Silnia
Ten rozdział jest niejako przypomnieniem czym jest podstawowa funkcja kombinatoryki czyli silna.
Silnią n! liczby naturalnej n nazywamy iloczyn 1 * 2 * 3 * ... * n, gdzie zakłada się, że 1! =1 i 0! = 1.
Czyli na przykład silnią n równemu 4 jest 24, bo:
4! = 1 * 2 * 3 * 4 = 24
1. Rozmieszczenia(wariacje)
Rozmieszczeniami z n elementów po k nazywamy ciągi k-wyrazowe, w których każdej z liczb 1, 2, ..., k odpowiada jeden z n danych przedmiotów. Rozmieszczenia te mogą się różnić bądź elementami, bądź przypadkiem elementów.
Na przykład rozmieszczenia z trzech elementów a, b ,c po 2: ab, ac, bc, ba, ca, cb.
Ilość wszystkich rozmieszczeń z n różnych elementów po k wyraża się wzorem:


Np:

Kod w Haskell'u:
-- Funkcja Silnia
silnia::Int ->Int
silnia 0 = 1
silnia n = n * silina (n-1)
-- Funkcja V
v::Int -> Int -> Int
v k n = silnia(n) / silnia(n-k)
Kod w Python'ie:
def silnia(n):
 return init(reduce(lambda x,y: x*y, range(2, n+1) or [1]))
def v(k,n):
 return silnia(n) / silnia(n-k)
Wiemy jak obliczać ilość możliwych kombinacji, ale bardziej interesujące wydaję się jak je tworzyć.
C.D.N.
2. Permutacje
Permutacjami z n elementów nazywamy ciągi n-wyrazowe, w których każdej z liczb 1,2,...,n odpowiada jeden z n danych przedmiotów. Permutacje różnią się tylko porządkiem elementów. Na przykład permutacje z trzech elementów a, b, c: abc, bca, cab, cba, bac, acb. Ilość wszystkich permutacji z n różnych elementów wyznacza się wzorem:
Jeżeli wśród n elementów a, b, c, ... znajdują się jednakowe elementy:
a występuje α, b występuje  β razy, c występuje γ razy itd., to:


poniedziałek, 26 września 2011

Trudne programowanie w C++

Witam!

Jako że ostatni przepisuję dosyć długaśśnyy kod z C# na C++ natknąłem się, a raczej spostrzegłem pewną hm... jak by to nazwać...odstępstwo(?). Chodzi mi tutaj o język C++ i programowanie obiektowe. W każdym chyba dziś bardziej poważanym języku mamy możliwość projektowania obiektowego. Wd. mnie w C++ jest ono NAJBARDZIEJ SKOPANE. Dlaczego? Ponieważ brak mi tutaj jakiegoś uporządkowania, wygody... Gdy piszę jakiś projekt zazwyczaj rzadko zaglądam do manuali języka ponieważ no nie muszę. Jako że dosyć często piszę w C i Python nie jest mi obcy, raczej w tych językach się skupiam. W C do manuli nie zaglądam w sumie w ogóle(ew. jeżeli potrzebuję korzystać z bibliotek typu string etc.), w Pythonie coraz rzadziej...Natomiast w C++ przy manualu spędzam więcej czasu niż zajmuje mi pisanie! Problemy sprawiane przez dziwną dosyć składnię i niepełną obiektowość są poprostu przybijające! Dziwne wypełnianie   metod, wirtualny(!) destruktor, pliki nagłówkowe ze strażnikami, bezsensowne RTTI zwiększające wagę binarek...Można wymieniać latami. Szkoda że mam trochę zbyt dużo roboty bo całkiem rozbudowany jest mój system obiektowości oraz klasa string którą przy jej pomocy w C napisałem. Efekt przedstawię w miarę wolnej chwili :)

czwartek, 8 września 2011

Clojure-Lisp na JVM?

Hai All!

Otóż niedawno zainteresowałem się przepięknym językiem jakim jest Lisp :). Szukając implementacji odpowiedniej dla mojego systemu oraz upodobań trafiłem najpierw na Scheme(bardzo fajnie sie piszę zwłaszcza pod schemik'iem :D). Wczoraj znalazłem Clojure. Znalazłem w sumie przez przypadek ponieważ szukałem jakiejś biblioteki graficznej pod Scheme. Nie znalazłem, za to pooglądałem sobie src kilku gierek napisanych w Clojure z wykorzystaniem JOGL oraz AWT i Swing'a. Ogólnie muszę jeszcze obczaić AWT i Swinga w szczególności operacje na obrazach, a więc czeka mnie długie debuggowanie .clj :) Myślę że nie potrwa to jakoś potwornie długo i niedługo pojawi się jakaś gierka sygnowana moim imieniem :)

Popularne posty