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.

Zamiana liczb rzymskich na arabskie i na odwrót

Konwersja między różnymi formatami zapisu liczb zawsze jest dobrą wprawką programistyczną. Przyjrzyjmy się dwóm systemom zapisu. System arabski wykorzystuje cyfry od 0 do 9 i jest stosowany powszechnie na całym świecie. System rzymski opiera się na 7 znakach literowych (I - 1, V - 5, X - 10, L - 50, C - 100, D - 500, M - 1000). Poszczególne wartości są tworzone za pomocą odpowiednich zestawień znaków. Np. MCMXCIV odpowiada liczbie 1994. W jaki sposób prawidłowo odczytać wartość, znaki jednakowe są dodawane (np. XX - 10+10 = 20), znaki mniejsze stojące przed większymi są od nich odejmowane (np. IV - 5-1 = 4), znaki mniejsze stojące za większymi są do nich dodawane (np. VI - 5+1 = 6).

Drzewo - ogólna implementacja

Struktury drzewiaste są dość często wykorzystywane w informatyce. Java nie posiada żadnej gotowej klasy do obsługi drzew. Dzisiaj prosta implementacja dowolnego drzewa ogólnego (każdy element drzewa może posiadać nieograniczoną liczbę potomków). Samo drzewo to struktura elementów, węzłów (ang. node) pozostających w zależności hierarchicznej tak jak na poniższym diagramie.

Metody o zmiennej liczbie argumentów

Po poprzednich wpisach dzisiaj coś lekkiego :) Poznamy metody, które mogą mieć zmienną liczbę argumentów (ang. varargs). Przed Javą 1.5 (inaczej zwaną 5.0) jedyną możliwością przesłania do metody zmiennej liczby argumentów było wykorzystanie tablic, w Javie 5.0 wprowadzono nowy sposób zapisu argumentu: Typ... Przykładowy nagłówek metody o zmiennej liczbie argumentów:

public static void metoda(String napis, String... napisy);

Przeglądamy kolekcję - interfejs Iterable<T>

Od Javy 5.0 wprowadzono pętlę iteracyjną (znaną w innych językach programowania jako pętla foreach) umożliwiającą przeglądnięcie wszystkich elementów należących do danej kolekcji. Pętla ta może być stosowana z tablicami oraz wszystkim klasami, które implementują interfejs Iterable<T>.
Ogólny format pętli iteracyjnej:

for (T wartosc : kolekcja) {
 // dla każdego elementu z kolekcji dostępnego 
 // pod zmienną wartosc typu T
 // gdzie T jest typem generycznym
}

Porównujemy obiekty - interfejs Comparable<T>

Często chcemy porównać ze sobą dwa obiekty jakiejś klasy. Oczywiście możemy porównać odpowiednie pola klasy i zwrócić wynik, ale.... rozwiązanie idealne polega na zaimplementowaniu w naszej klasie interfejsu Comparable<T>. Dzięki implementacji interfejsu, obiekty powstałe na bazie naszej klasy będą mogły być porównywane ze sobą. Taki sposób porównywania (mówiąc inaczej uporządkowania obiektów) jest wykorzystywany przez Javę np. w kolekcjach. Standardowe klasy np. klasa String również implementują ten interfejs. Dzięki temu porównując dwa łańcuchy tekstowe wiemy który jest "mniejszy", a który "większy" (w tym przypadku wykorzystywane jest uporządkowanie alfabetyczne). Wróćmy do interfejsu Comparable<T>, ma on tylko jedną metodę: