Gra w życie

Gra w życie to przykład automatu komórkowego wymyślonego przez matematyka Johna Conwaya. Gra jest prowadzona w macierzy elementów, komórek. Każda z komórek może być żywa lub martwa. O stanie komórki w kolejnym etapie gry decyduje kilka zasad.

Projekt Euler - Problem numer 1

Projekt Euler (http://projecteuler.net) to strona internetowa zawierająca pokaźny zbiór (ponad 300) problemów obliczeniowych, do rozwiązania których potrzebny jest (w większości przypadków) komputer oraz dowolny język programowania. Rozwiązaniem każdego zadania jest wynik, który podajemy, aby sprawdzić czy nasz sposób obliczeń jest poprawny. Oczywiście sednem zabawy jest opracowanie odpowiedniego dla danego problemu algorytmu. Przyjrzyjmy się zatem pierwszemu zadaniu.

Odległość Levenshteina - podobieństwo łańcuchów

Do obliczania podobieństwa łańcuchów tekstowych wykorzystuje się algorytm Levenshteina (Vladimir Levenshtein - rosyjski uczony), znany również jako odległość edycyjna, albo odległość Levenshteina. Otrzymana w wyniku działania algorytmu liczba symbolizuje ile działań prostych musimy wykonać, aby dokonać konwersji/zamiany jednego łańcucha na drugi. Działania proste to wstawienie znaku, usunięcie znaku oraz zamiana znaku na inny. Dla łańcucha "kot" i "kod" odległość edycyjna wynosi 1. Musimy dokonać tylko jednej zamiany znaku. Im większa odległość tym bardziej różne są łańcuchy znaków.

Algorytm Luhna

Algorytm Luhna (autor: Hans Peter Luhn - naukowiec z IBM) jest najczęściej wykorzystywanym sposobem sprawdzenia poprawności ciągu liczb. Jego zastosowanie to sprawdzanie numerów kart kredytowych i innych np. lojalnościowych, numerów IMEI, numerów ubezpieczeń itd. Algorytm działa na pojedynczych cyfrach od prawej do lewej strony sprawdzanej liczby. Sam schemat jest bardzo prosty i sprowadza się do kilku kroków:

1. sumujemy cyfry nieparzyste (pierwszą, trzecią, piąta itd.),
2. podwajamy cyfry parzyste (drugą, czwartą, szóstą itd.), jeśli podwojona wartość jest większa od 9, sumujemy cyfry (np. podwajamy 8, dostajemy 16, wartość większa od 9, sumujemy cyfry 1+6, dostajemy wynik 7),
3. sumujemy otrzymane cyfry z kroku drugiego,
4. dodajemy dwie sumy (dla cyfr parzystych i nieparzystych), jeśli wynik modulo 10 daje 0 to liczba jest poprawna, w przeciwnym przypadku niepoprawna.

Wyświetlanie drzewa na konsoli

W poprzednich postach utworzyliśmy strukturę drzewa (Ogólna implementacja) oraz poznaliśmy metody umożliwiające przejście przez wszystkie jego węzły w określonej kolejności (Trawersowanie drzewa). Kolejnym krokiem będzie przedstawienie struktury drzewa w jakiejś czytelnej formie na ekranie komputera. Wykorzystamy do tego celu konsolę. Jest kilka sposobów prezentacji drzewa, najczęściej wykorzystuje się zapis, gdzie poszczególne elementy są w odpowiednich kolumnach lub zapis z nawiasami, które symbolizują dzieci danego elementu. Przyjrzyjmy się naszemu drzewu jeszcze raz w formie graficznej.

Klasa Arrays - przykłady zastosowań

Dość często korzystamy z tablic jedno i wielowymiarowych. Klasa java.util.Arrays dostarcza wielu ciekawych metod ułatwiających pracę z tymi strukturami danych. Większość z nich jest przeciążona obsługując wiele typów danych (metoda przeciążona - metoda o takiej samej nazwie, ale różnej ilości lub rodzaju argumentów). Poniżej kilka przykładów wykorzystania tych metod (pamietaj o imporcie odpowiedniego pakietu - import java.util.*).

Trawersowanie drzewa - metody preorder, postoder i inorder

W poprzednim poście (Drzewo ogólna implementacja) przedstawiłem podstawy tworzenia struktury drzewa. Dziś zajmiemy się sposobami trawersowanie drzewa czyli odwiedzenia wszystkich jego węzłów w ściśle określonej kolejności. Dla drzew ogólnych mamy dwie metody odwiedzania preorder oraz postorder, w przypadku drzew binarnych (gdzie węzeł może posiadać maksymalnie dwóch potomków) istnieje jeszcze metoda inorder.