Odwrotna Notacja Polska - część 2

W poprzedniej części (Odwrotna Notacja Polska - część 1) dokonaliśmy zamiany wyrażenia w formie infiksowej na postać postfiksową (czyli formę w Odwrotnej Notacji Polskiej). W tym wpisie spróbujemy dokonać sprawdzenia poprawności nawiasów występujących w wyrażeniu infiksowym oraz obliczymy wartość wyrażenia postfiksowego. Do sprawdzenia poprawności nawiasów w wyrażeniu infiksowym użyjemy stosu (więcej na ten temat - Sprawdzanie poprawności nawiasów). Jeśli wyrażenie nie będzie poprawne pod wartość wyrażenia postfiksowego podstawimy odpowiedni napis (klasa String - "Niepoprawne nawiasy w wyrażeniu infiksowym"). Nasza metoda sprawdzająca poprawność nawiasów będzie metodą prywatną:

Piszemy gadżet do Bloggera - część 2

W poprzedniej części (Piszemy gadżet do Bloggera - część 1) poznaliśmy podstawy pisania gadżetu oraz jego strukturę. Dzisiaj poznamy sposoby jego konfigurowania przez użytkownika. Pozwolimy użytkownikowi na podanie dodatkowych informacji podczas dodawania gadżetu do bloga. Dzięki temu użytkownik będzie mógł zdecydować np. o kolorach, napisach czy innych opcjach związanych z konkretnym gadżetem. Sekcją odpowiedzialną za preferencje jest <UserPref>. Opisuje ona pola, które będzie mógł modyfikować użytkownik podczas konfiguracji gadżetu. Pola mogą mieć następujące atrybuty:

Odwrotna Notacja Polska - część 1

Odwrotna Notacja Polska to sposób zapisu wyrażeń arytmetycznych za pomocą notacji postfiksowej. Standardowa notacja, z której korzystamy na codzień to notacja infiksowa, argument operator argument (np. 3 + 4). Notacja postfiksowa nie zmienia kolejności argumentów, natomiast zmienia położenie operatorów (występują one po argumentach, których dotyczą). Przykładowy zapis w notacji postfiksowej wyglada tak: 3 4 +. Taki sposób zapisu jest o wiele łatwiejszy do analizy poprawności wyrażenia jak i do jego obliczenia. Wykorzystując stos w prosty sposób możemy dokonać zamiany wyrażenia z postaci infiksowej na postać postfiksową. Algorytm zamiany jest następujący:

Klasa LinkedList - przykład zastosowania

Klasa LinkedList jest jedną z klas bibliotecznych dostępnych w standardowej Javie. Jest to prosta implementacja listy powiązanej z wykorzystaniem typów generycznych (pisałem o nich tutaj Typy generyczne). Na jej bazie możemy napisać implementację w pełni dynamicznego stosu (inne sposoby tworzenia stosu to Stos - implementacja tablicowa oraz Lista powiązana - własna implementacja). Nasze rozwiązanie dzięki zastosowaniu typów generycznych umożliwi obsługę dowolnych obiektów.

Typy generyczne

Java od wersji 1.5 obsługuje typy generyczne. Pozwalają one sparametryzować klasę, przez co nie ma konieczności dokonywania później kłopotliwego rzutowania. Sam zapis typu generycznego to duża litera/litery ujęta w nawiasy ostre. Utwórzmy prostą klasę Pudelko przechowującą elementy dowolnego typu.
/**
 * Wykorzystanie typów generycznych 
 * @author kodatnik.blogspot.com
 */
class Pudelko <T> {
 // referencja do obiektu typu T
 private T element; 

 // konstruktor klasy
 public Pudelko(T element) {
  this.element = element;
 } 

 // metoda zwraca referencję do przechowywanego elementu
 public T pobierzElement() {
  return element;
 }
}
Tworząc obiekt klasy Pudelko musimy określić jakiego typu dane będą w nim przechowywane. Przykładowe wykorzystanie klasy Pudelko.
public class TestPudelka {
 public static void main(String args[]) {
    
  // tworzymy trzy pudełka dla różnych typów danych (String, Integer oraz Double)
  Pudelko<String>  p1 = new Pudelko<String>("Ala ma kota");
  Pudelko<Integer> p2 = new Pudelko<Integer>(12);     
  Pudelko<Double>  p3 = new Pudelko<Double>(24.76);   
  
  // sprawdzamy zawartość każdego pudełka
  System.out.println (p1.pobierzElement());
  
  int wartosc = p2.pobierzElement() + 3;
  System.out.println (wartosc);
  
  System.out.println (p3.pobierzElement());    
 }
}
Wynik działania aplikacji (pudełko pierwsze przechowuje łańcuchy tekstowe, drugie liczby całkowite, a trzecie liczby rzeczywiste).
Ala ma kota
15
24.76
Większość klas dostarczanych z Javą wykorzystuje typy generyczne. Są to zazwyczaj klasy będące "pojemnikami" dla innych obiektów (tzw. kolekcje). Na przykład klasy LinkedList, Array, Stack, Vector, TreeMap itp.
Typy generyczne przeznaczone są tylko do typów obiektowych, nie można ich użyć do typów prymitywnych.

Piszemy gadżet do Bloggera - część 1

Gadżety rozszerzają funkcjonalność naszych blogów. Dla platformy Blogger istnieje już kilkaset gotowych rozwiązań. Nic nie stoi na przeszkodzie, aby napisać samodzielnie taki gadżet. W kilku postach postaram się przybliżyć tematykę pisania gadżetów. Co będzie nam potrzebne:
  • edytor tekstu (z możliwością zapisu w formacie UTF-8, np. Windowsowy notatnik, Notepad++, czy PSPad),
  • serwer na którym zamieścimy nasz gadżet (np. Witryny Google, lub inny dowolny serwer z możliwością wgrywania plików),
  • podstawową znajomość HTML'a i JavaScriptu.
Struktura gadżetu

Gadżety do Bloggera tak samo jak pozostałe gadżety Googli składają się z plików XML (kod gadżetu, pliki językowe itd.). Podstawowa struktura gadżetu została przedstawiona poniżej.
<module>
 <moduleprefs title="Przykładowy gadżet"> 
  // pozostałe ustawienia
 <content type="html">
  <![CDATA[ 
   // zawartość HTML, JavaScript
  ]]>
 </content>
 </moduleprefs>
</module>
Pierwsza linia jest obowiązkowa i informuje o rozpoczęciu pliku w formacie XML. Pozostałe to tagi związane z gadżetami i tak:
  • tag <module> to oznaczenie, że plik będzie zawierał dane gadżetu,
  • tag <moduleprefs> zawiera dodatkowe informacje o gadżecie (autor, tytuł, lokalizacje, używane rozszerzenia itp.)
  • tag <content type="html"> informuje, że zawartością gadżetu będą polecenia HTML'a,
  • sekcja <![CDATA[ rozpoczyna właściwy kod HTML'a (czy JavaScript'u), który będzie wyświetlany przez gadżet,
  • ]]> zamknięcie sekcji CDATA,
  • </content> - tag zamykający,
  • </module> - tag zamykający.
Utwórzmy prosty gadżet wyświetlający napis "Nasz pierwszy gadżet!". Dodatkowo w sekcji <moduleprefs> zamieścimy informacje o autorze. Po wpisaniu kodu do edytora zapiszmy go pod nazwą PierwszyGadzet.xml
<module>
 <moduleprefs author="Devon" title="Przykładowy gadżet"> 
 <content type="html">
  <![CDATA[ 
   Nasz pierwszy gadżet!
  ]]>
 </content>
 </moduleprefs>
</module>
Pozostaje opublikowanie go w sieci. Możemy wykorzystać do tego celu Witryny Googli (więcej informacji o zakładaniu witryny znajdziesz tutaj). Po opublikowaniu (adres mojego gadżetu to: http://sites.google.com/site/kodatnikfiles/xml/PierwszyGadzet.xml), możemy sprawdzić jego działanie. Logujemy się do Bloggera, przechodzimy na Układ/Elementy strony, klikamy Dodaj gadżet, wybieramy Dodaj swoje własne i wpisujemy adres URL naszego gadżetu.



Klikamy Dodaj wg adresów URL i jeśli wszystko przebiegło poprawnie powinniśmy otrzymać takie okienko:



Dajemy Zapisz i nasz gadżet pojawi się na blogu.



W następnych odcinkach pokaże jak skorzystać z dodatkowych opcji, zmienić kolory gadżetu (zgodnie z szablonem bloga), dostać się do danych bloga oraz utworzyć lokalizacje językowe.

Wszystkie gadżety, które utworzymy i dodamy do Bloggera są "cache'owane". Oznacza to, że zmiany które wprowadzimy w kodzie nie będą widoczne od razu w gadżecie (Google "trzyma" wersję zbuforowaną mniej więcej 2 godziny). Jeżeli chcemy sprawdzić od razu zmiany to możemy, albo wyłączyć buforowanie (trochę pracy - modyfikacja szablonu), albo zapisać gadżet pod inną nazwą na serwerze (np. DrugiGadzet.xml) i dodać go od nowa do naszego bloga.

Lista powiązana - własna implementacja

Lista powiązana (ang. linked list) to struktura dynamiczna, której każdy element tak zwany węzeł (ang. node) posiada określoną wartość (lub wartości) oraz referencję do kolejnego węzła. Chcemy napisać prostą listę przechowującą wartości typu String (łańcuchy tekstowe). Pierwszą czynnością jest napisanie odpowiedniej klasy, na podstawie której będziemy tworzyć węzły.

Wieże Hanoi

Wieże Hanoi to problem polegający na przełożeniu z jednego słupka, na drugi, dysków o różnej średnicy. Przy przekładaniu można posługiwać się dodatkowym słupkiem stanowiącym bufor. Nie można kłaść dysku o większej średnicy na dysk o mniejszej średnicy, ani przekładać więcej niż jednego dysku jednocześnie. Chcemy napisać aplikację, która zasymuluje nam kolejne kroki potrzebne do przełożenia dysków. Zastosujemy algorytm rekurencyjny.
// wykorzystujemy klasę Scanner z pakietu java.util
import java.util.*;

/**
 * Wieże Hanoi - rozwiązanie rekurencyjne
 * @author kodatnik.blogspot.com
 */
public class WiezeHanoi {
 
 // Rekurencyjna metoda przekładająca dyski o parametrach
 // dyski - liczba dysków
 // skad - oznaczenie słupka początkowego
 // dokad - oznaczenie słupka docelowego
 // bufor - oznaczenie słupka pomocniczego
 public static void hanoi(int dyski, char skad, char dokad, char bufor) {
  // jeśli są dyski
  if (dyski > 0 ) {
   // przenieś (rekurencyjnie) n-1 dysków ze słupka A na słupek B posługując się słupkiem C
   hanoi(dyski - 1, skad, bufor, dokad);
   // wyświetl przeniesienie dysku
   System.out.println(skad + " > " + dokad);
   // przenieś (rekurencyjnie) n-1 dysków ze słupka B na słupek C posługując się słupkiem A
   hanoi(dyski - 1, bufor, dokad, skad);
  }
 } 

 public static void main(String args[]) {
  
  Scanner sc = new Scanner(System.in);
  System.out.print ("Ile dysków chcesz przełożyć: " );

  // pobieramy od użytkownika liczbę dysków
  int n = sc.nextInt();     
     
  // wywołujemy metodę wyświetlającą kolejne przełożenia dysków
  // ze słupka A na słupek C korzystając ze słupka B
  hanoi(n , 'A', 'C', 'B');     
 }
}
Uruchomiona aplikacja:
Ile dysków chcesz przełożyć: 4
A > B
A > C
B > C
A > B
C > A
C > B
A > B
A > C
B > C
B > A
C > A
B > C
A > B
A > C
B > C

Problem Józefa Flawiusza

Józef Flawiusz podczas wojny żydowsko-rzymskiej wraz 40 towarzyszami został otoczony przez Rzymian. Nie chcąc się poddać postanowili popełnić samobójstwo. Ustawili się w kręgu i co trzecia osoba odbierała sobie życie. Na końcu pozostał przy życiu przyjaciel Flawiusza oraz on sam. Oddali się w ręce wroga. Chcemy napisać aplikację, która zasymuluje nam, w jakiej kolejności ginęli żołnierze oraz, na której pozycji w kręgu ustawił się Flawiusz wraz ze swoim przyjacielem. Do rozwiązania tego problemu wykorzystamy przedstawioną wcześniej klasę Kolejka (Kolejka - implementacja tablicowa).
/**
 * Problem Józefa Flawiusza
 * @author kodatnik.blogspot.com
 */
public class JozefFlawiusz {
    
 public static void main(String[] args) {
  // zmienna przechowuje liczbę żołnierzy (Flawiusz + 40)
  int zolnierze = 41;
  // zmienna określa co który będzie ginął
  int coKtory = 3;

  // tworzymy kolejkę o rozmiarze równych liczbie żołnierzy
  Kolejka k = new Kolejka(zolnierze);
  
  // dodajemy żołnierzy do kolejki (od 1 do 41)
  for (int i = 1; i <= zolnierze; i++)
   k.dodaj(i);
            
  // w pętli dopóki kolejka nie jest pusta
  while ( !k.czyPusta() ) {
   // przestawiamy dwóch żołnierzy z początku na koniec kolejki
   for (int i = 0; i < coKtory - 1; i++)
    k.dodaj(k.usun());

   // eliminujemy trzeciego (usuwamy go z kolejki)
   // i wyświetlamy jego numer ekranie
   System.out.print(k.usun() + " ");
  } 
  System.out.println();
 }
}
Uruchomiona aplikacja:
3 6 9 12 15 18 21 24 27 30 33 36 39 1 5 10 14 19 23 28 32 37 41
7 13 20 26 34 40 8 17 29 38 11 25 2 22 4 35 16 31
Jak widać na wynikach generowanych przez program, Józef Flawiusz wraz z przyjacielem ustawili się na pozycji 16 i 31.

Kolejka - implementacja tablicowa

Kolejka to struktura danych działająca w oparciu o zasadę FIFO (ang. First In First Out), pierwszy wchodzi, pierwszy wychodzi. Dostęp do kolejki jest możliwy z dwóch stron (początek i koniec). Podstawowe metody związane z kolejką to dodanie elementu do kolejki, na jej koniec (ang. enqueue), usunięcie elementu z kolejki, z jej początku (ang. dequeue), podgląd elementu znajdujacego się na początku (ang. peek). Dodatkowo w większości implementacji istnieje możliwość wyświetlenia zawartości kolejki jak i sprawdzenia czy kolejka jest pusta. Chcemy napisać w oparciu o tablicę prostą klasę Kolejka przechowującą liczby całkowite (dane typu int). Efektywne wykorzystanie tablicy jest możliwe poprzez zawijanie kolejki (dane trafiają na odpowiednie miejsce) . Uzyskanie odpowiednich indeksów w kolejce zawijanej osiągnięmy wykonując operacje modulo rozmiar tablicy dla zmiennych poczatek oraz koniec. Poniżej klasa wraz z przykładowym jej wykorzystaniem.
/**
 * Kolejka liczb całkowitych - implementacja tablicowa
 * @author kodatnik.blogspot.com
 */
public class Kolejka {
 // tablica przechowująca elementy kolejki
 private int[] wektor;
 // początek kolejki (indeks elementu znajdującego się na początku)
 private int poczatek;
 // koniec kolejki (indeks elementu znajdującego się na końcu)
 private int koniec;
 // liczba elementów kolejki (pole pomocnicze)
 private int rozmiarKolejki;
 
 // konstruktor domyślny (tworzy kolejkę 10 elementową)
 public Kolejka() {
  // wywołujemy konstruktor z parametrem int (czyli ten poniżej)
  this(10);
 }
                 
 // konstruktor jednoparametrowy
 public Kolejka(int rozmiar) {
  // tworzymy tablicę o rozmiarze przekazanym jako parametr wywołania
  wektor = new int[rozmiar];
  // ustawiamy początkowe wartości pól (można to pominąć, domyślnie pola będą miały wartość zero)
  poczatek = 0;
  koniec = 0;
  rozmiarKolejki = 0;
 }
 
 // metoda dodaje element do kolejki
 public void dodaj(int liczba) {
  // wpisujemy na koniec kolejki element 
  // (operacja modulo da nam odpowiedni indeks tablicy)
  wektor[koniec % wektor.length] = liczba;
  // zwiększamy indeks końca oraz rozmiar kolejki
  koniec++;
  rozmiarKolejki++;
 }
 
 // metoda usuwa element z kolejki
 public int usun() {
  // pobieramy element z początku kolejki
  // (operacja modulo da nam odpowiedni indeks tablicy)  
  int temp  = wektor[ poczatek % wektor.length];
  // zwiększamy indeks początku kolejki
  poczatek++;
  // zmniejszamy rozmiar kolejki
  rozmiarKolejki--;
  // zwracamy usunięty element
  return temp;
 } 

 // metoda sprawdza czy kolejka jest pusta
 public boolean czyPusta() {
  // zwracamy prawdę lub fałsz
  return (rozmiarKolejki == 0);
 }

 // metoda sprawdza czy kolejka jest pełna
 public boolean czyPelna() {
  // zwracamy prawdę lub fałsz
  return (rozmiarKolejki == wektor.length);
 } 

 // metoda "podgląda" co jest na początku kolejki
 public int zobacz() {
  // zwracamy element z początku (nie modyfikujemy pozostałych zmiennych)
  return wektor[poczatek % wektor.length];
 } 

 // metoda zwraca rozmiar kolejki (liczbę elementów w kolejce) 
 public int rozmiar() {
  return rozmiarKolejki;
 } 
 
 // metoda wyświetla wszystkie elementy w kolejce 
 public void wyswietl(){
  // w pętli od początku do rozmiaru kolejki
  // (również wykorzystujemy modulo)
  for (int i = poczatek % wektor.length; i < poczatek % wektor.length + rozmiarKolejki; i++) 
   // wyświetlamy poszczególne elementy
   System.out.print (wektor[ i % wektor.length] + " ");
  System.out.println ();
 }
}
/**
 * Test kolejki liczb całkowitych
 * @author kodatnik.blogspot.com
 */
public class TestKolejki {

 public static void main(String args[]) {
    
  // zakładamy nową kolejkę o rozmiarze 20
  Kolejka k = new Kolejka(20);
     
  // dodajemy elementy do kolejki
  k.dodaj(12);
  k.dodaj(8);
  k.dodaj(39);
     
  // wyświetlamy zawartość kolejki
  k.wyswietl();
 
  // wyświetlamy element znajdujący się na początku (bez jego usuwania)
  System.out.println(k.zobacz());
     
  // usuwamy element z kolejki
  k.usun();     
      
  // wyświetlamy zawartość kolejki
  k.wyswietl();     
 }
}
Uruchomiona aplikacja:
12 8 39 
12
8 39 
Przedstawiona kolejka jest statyczna, jej rozmiar ustalamy podczas tworzenia obiektu (nie mamy możliwości jego zmiany w trakcie działania). Przechowujemy dane tylko jednego typu (int), co w większości zastosowań może okazać się niewystarczające. Lepszym rozwiązaniem jest zastosowanie do implementacji kolejki list powiązanych (struktura dynamiczna) oraz wykorzystanie typów generycznych (możliwość tworzenia kolejek przechowujących dowolny typ danych).
Kolejki wykorzystywane są w algorytmice, w programach komputerowych (np. kolejka plików w Winampie), systemach operacyjnych (np. kolejka wydruku).

Sprawdzanie poprawności nawiasów

Do sprawdzenia poprawności umiejscowienia nawiasów w wyrażeniu posłużymy się przedstawioną wcześniej klasą Stos (Stos - implementacja tablicowa). Sam algorytm jest stosunkowo prosty. Bierzemy element wyrażenia, jeśli jest to nawias otwierający odkładamy go na stos, jeśli nawias zamykający ściągamy ze stosu element i porównujemy czy razem stanowią parę, jeśli tak idziemy dalej, jeśli nie kończymy działanie algorytmu. Znaki nie będące nawiasami ignorujemy. Wyrażenie jest poprawne pod względem nawiasów, jeśli po przejściu przez wszystkie elementy stos będzie pusty. Poniżej krótka aplikacja sprawdzająca pobrane od użytkownika wyrażenie. Obsługiwane są nawiasy okrągłe, kwadratowe oraz klamrowe.
// wykorzystujemy klasę Scanner z pakietu java.util
import java.util.*;

/**
 * Sprawdzanie poprawności nawiasów 
 * Wykorzystujemy utworzoną wcześniej klasę Stos
 *
 * @author kodatnik.blogspot.com
 */
public class PoprawnoscNawiasow {
 
 // metoda sprawdza czy nawiasy w przekazanym jako parametr wyrażeniu są poprawne
 // obsługiwane są nawiasy okrągłe, kwadratowe i klamrowe
 // zwraca true dla poprawnych i false dla niepoprawnych
 public static boolean czyPoprawne(String wyrazenie) {
   
  // dwie tablice przechowujące nawiasy otwierające i zamykające
  char[] otwierajace  = {'(', '[', '{'};
  char[] zamykajace   = {')', ']', '}'};
     
  // tworzymy stos o rozmiarze naszego wyrażenia
  Stos stos = new Stos(wyrazenie.length());
        
  // pętla dla każdego znaku znajdującego się w wyrażeniu    
  for (int i = 0; i < wyrazenie.length(); i++) {
   
   // jeżeli znak jest nawiasem otwierającym odkładamy go na stos
   for (int j = 0; j < otwierajace.length; j++ ){
    if ( wyrazenie.charAt(i) == otwierajace[j]) stos.push((int) otwierajace[j]);
   }
         
   // jeżeli znak jest nawiasem zamykającym porównujemy go z wartością ze stosu
   for (int j = 0; j < zamykajace.length; j++ ){
    if ( wyrazenie.charAt(i) == zamykajace[j]) {
     // jeśli stos jest pusty zwracamy fałsz
     if (stos.czyPusty()) return false;
     // jeśli nawiasy nie są tego samego typu zwracamy fałsz
     if (((char) stos.pop()) != otwierajace[j]) return false;
    } 
   }         

   // ignorujemy znaki, które nie są nawiasami

   }
  // zwracamy true albo false (stos pusty - wszystkie nawiasy są poprawne)
  return stos.czyPusty();
 }
 
 public static void main(String[] args) {
        
  Scanner sc = new Scanner(System.in);
  System.out.print ("Podaj wyrażenie z nawiasami: ");
 
  // pobieramy od użytkownika wyrażenie z nawiasami
  String wyrazenie = sc.nextLine();
        
  // wyświetlamy informacje o poprawności wyrażenia z nawiasami
  System.out.println("Wyrażenie jest " + (czyPoprawne(wyrazenie) ? "poprawne." : "niepoprawne."));
 }
}
Przykładowe uruchomienia aplikacji:
Podaj wyrażenie z nawiasami: (a[b{c}d]e)
Wyrażenie jest poprawne.
Podaj wyrażenie z nawiasami: [a(b{c})
Wyrażenie jest niepoprawne.
Podaj wyrażenie z nawiasami: (([a]b)}
Wyrażenie jest niepoprawne.
Modyfikując tablicę z nawiasami możemy sprawdzać poprawność wyrażeń z dowolnymi znakami otwierającymi i zamykającymi.

Podział łańcucha na części

Pisząc aplikacje spotykamy się z problemem podziału łańcucha tekstowego na części (np. import danych w formacie CSV, rozbicie zdania na wyrazy itd.). Idealną klasą, która pomoże nam podzielić łańcuch tekstowy jest klasa StringTokenizer z pakietu java.util. Jej zadaniem jest podział tekstu na części (tak zwane tokeny) na podstawie znaków rozdzielających (ang. delimiter). Klasa posiada trzy konstruktory, oraz kilka metod umożliwiających pobranie podzielonych już tokenów. Poniższy przykład wykorzystuje konstruktor StringTokenizer(String), dzielący łańcuchy tekstowe na podstawie znaku spacji, tabulacji, nowego wiersza i powrotu karetki. Znaki rozdzielające nie są traktowane jako tokeny.
// wykorzystujemy klasę Scanner oraz StringTokenizer z pakietu java.util
import java.util.*;

/**
 * Podział łańcucha tekstowego na części
 * @author kodatnik.blogspot.com 
 */ 
public class PodzialLancucha {
  
 public static void main (String[] args) {
   
  Scanner sc = new Scanner(System.in);
  System.out.print ("Podaj łańcuch: ");
   
  // pobieramy od użytkownika łańcuch tekstowy
  String lancuch = sc.nextLine();
   
  // tworzymy nowy obiekt klasy StringTokenizer
  StringTokenizer st = new StringTokenizer(lancuch);
   
  // metoda countTokens() zwróci nam liczbę tokenów (części)
  int liczbaTokenow = st.countTokens(); 
   
  // wyświetlamy na ekranie informacje o liczbie tokenów
  System.out.println("Liczba tokenów w łańcuchu: " + liczbaTokenow);
    
  // w pętli dopóki są jeszcze tokeny (metoda hasMoreTokens())
  while(st.hasMoreTokens()) {
   //wyświetlamy je na ekranie (metoda nextToken())
   System.out.println(st.nextToken());
  }
 }
}
Uruchomiona aplikacja:
Podaj łańcuch: Nie programuj w wigilię... bug się rodzi
Liczba tokenów w łańcuchu: 7
Nie
programuj
w
wigilię...
bug
się
rodzi
Drugi konstruktor StringTokenizer(String, String) umożliwia nam określenie własnych znaków rozdzielających. Możemy na przykład użyć przecinka czy też średnika do podziału linii z pliku CSV. Znaki rozdzielające również nie są traktowane jako tokeny.
StringTokenizer st = new StringTokenizer(lancuch, ";");
Wynik działania programu:
Podaj łańcuch: Kasia;Fikas;ul. Marsowa 12;Katowice
Liczba tokenów w łańcuchu: 4
Kasia
Fikas
ul. Marsowa 12
Katowice
Ostatnie wersja konstruktora StringTokenizer(String, String, boolean) pozwala nam określić czy znaki rozdzielające mają być traktowane jako tokeny. W poniższym przykładzie ustawiamy własne znaki rozdzielające # oraz %, które będą również tokenami.
StringTokenizer st = new StringTokenizer(lancuch, "#%", true);
Wynik działania programu:
Podaj łańcuch: 123#17.5#8%Marek%Kowalski
Liczba tokenów w łańcuchu: 9
123
#
17.5
#
8
%
Marek
%
Kowalski

Stos - implementacja tablicowa

Stos to struktura danych działająca w oparciu o zasadę LIFO (ang. Last In First Out), ostatni wchodzi pierwszy wychodzi. Dostęp do stosu możliwy jest tylko z jednego miejsca tzw. wierzchołka (ang. top). Podstawowe metody związane ze stosem to odłożenie elementu na stos (ang. push), ściągnięcie elementu ze stosu (ang. pop), podgląd elementu znajdującego się na szczycie stosu (ang. peek). Dodatkowo w większości implementacji istnieje możliwość wyświetlenia zawartości stosu jak i sprawdzenia czy stos jest pusty. Chcemy napisać, w oparciu o tablicę, prostą klasę Stos przechowującą liczby całkowite (dane typu int). Poniżej klasa wraz z jej przykładowym wykorzystaniem.
/**
 * Stos liczb całkowitych - implementacja tablicowa
 * @author kodatnik.blogspot.com 
 */ 
class Stos {
 // tablica przechowująca elementy stosu
 private int[] wektor;
 // wierzchołek stosu
 private int top;

 // konstruktor domyślny (tworzy stos 10 elementowy)
 public Stos() {
  // wywołujemy konstruktor z parametrem int (czyli ten poniżej)
  this(10);
 }
 
 // konstruktor jednoparametrowy
 public Stos(int rozmiar) {
  // tworzymy tablicę o rozmiarze przekazanym jako parametr wywołania
  wektor = new int[rozmiar];
  // ustawiamy wartość początkową wierzchołka stosu
  top = -1;
 }
 
 // metoda odkładająca na stosie elementy
 public void push(int element) {
  // wpisujemy na odpowiedniej pozycji element oraz zwiększamy wierzchołek
  wektor[++top] = element;
 }

 // metoda ściąga ze stosu element
 public int pop() {
  // zwracamy element z wierzchołka stosu oraz zmniejszamy wierzchołek
  return wektor[top--]; 
 }
 
 // metoda sprawdza czy stos jest pusty
 public boolean czyPusty() {
  // zwracamy prawdę lub fałsz
  return (top == -1);
 }
 
 // metoda sprawdza czy stos jest pełny
 public boolean czyPelny() {
  // zwracamy prawdę lub fałsz
  return (top == wektor.length);
 }
 
 // metoda "podgląda" co jest na wierzchołku stosu
 public int peek() {
  // zwracamy element z wierzchołka stosu (nie modyfikujemy zmiennej top)
  return wektor[top];
 }
 
 // metoda wyświetla wszystkie elementy stanowiące stos
 public void wyswietl() {
  // w pętli do wierzchołka stosu
  for(int i = 0; i <= top; i++) 
   // wyświetlamy poszczególne elementy
   System.out.print(wektor[i] + " ");

  System.out.println();
 }
 
 // metoda zwraca rozmiar stosu (liczbę jego elementów)
 public int rozmiar() {
  return top + 1; 
 }
}
/**
 * Test kolejki liczb całkowitych
 * @author kodatnik.blogspot.com 
 */ 
public class TestKolejki {

 public static void main(String args[]) {
    
  // zakładamy nowy stos o rozmiarze 20
  Stos s = new Stos(20);
     
  // odkładamy kolejne wartości na stos
  s.push(12);
  s.push(8);
  s.push(39);
     
  // wyświetlamy zawartość stosu
  s.wyswietl();
     
  // wyświetlamy element znajdujący się na szczycie (bez jego ściągania)
  System.out.println(s.peek());
     
  // ściągamy element ze stosu
  s.pop();     
      
  // wyświetlamy zawartość stosu
  s.wyswietl();     
 }
}
Uruchomiona aplikacja:
12 8 39 
39
12 8
Powyższy stos jest statyczny, jego rozmiar ustalamy podczas tworzenia obiektu (nie mamy możliwości jego zmiany w trakcie działania). Przechowujemy dane tylko jednego typu (int), co w większości zastosowań może okazać się niewystarczające. Lepszym rozwiązaniem jest zastosowanie do implementacji stosu list powiązanych (struktura dynamiczna) oraz wykorzystanie typów generycznych (możliwość tworzenia stosów przechowujących dowolny typ danych).
Stos jest często wykorzystywany w algorytmice jak również w większości aplikacji, z którymi pracujemy codziennie (np. operacja cofnij w edytorach tekstu czy grafiki).

Liczby pseudolosowe

Pisząc programy w Javie często potrzebujemy wylosować jakąś wartość. Standardowo mamy dwie możliwości wygenerowania liczby pseudolosowej. Pierwsza, to skorzystanie z klasy Random dostępnej w pakiecie java.util. Klasa ta zawiera szereg przydatnych metod generujących liczby losowe. Wadą tego rozwiązania jest konieczność utworzenia nowego obiektu.
// wykorzystujemy klasę Random z pakietu java.util
import java.util.*;

/**
 * Generowanie liczb pseudolosowych
 * @author kodatnik.blogspot.com 
 */ 
public class LiczbyPseudolosowe {
  
 public static void main (String[] args) {
   
  // tworzymy obiekt klasy Random
  Random rand = new Random();
   
  // metoda nextInt() zwraca liczbę całkowitą (pełny zakres)
  int liczbaCalkowita = rand.nextInt();
      
  // metoda nextInt(int n) zwraca liczbę z zakresu >= 0 do < n-1
  int liczbaCalkowitaZakres = rand.nextInt(10);
   
  // metoda nextDouble() zwraca liczbę rzeczywistą z zakresu >= 0.0 do < 1.0
  double liczbaRzeczywista = rand.nextDouble();   
   
  System.out.println ("Wylosowana liczba całkowita: " + liczbaCalkowita);
  System.out.println ("Wylosowana liczba całkowita z zakresu <0, 10): " + liczbaCalkowitaZakres);   
  System.out.println ("Wylosowana liczba rzeczywista z zakresu <0.0, 1.0): " + liczbaRzeczywista);       
 }
}
Uruchomiona aplikacja:
Wylosowana liczba całkowita: 1133804662
Wylosowana liczba całkowita z zakresu <0, 10): 0
Wylosowana liczba rzeczywista z zakresu <0.0, 1.0): 0.06242174947663559
Drugi sposób to wykorzystanie statycznej metody random() dostępnej w klasie Math. Generuje ona pseudolosową liczbę rzeczywistą z zakresu od 0.0 włącznie do 1.0 wyłącznie. Tak otrzymaną liczbę zazwyczaj musimy przemnożyć przez odpowiednią wartość oraz dokonać rzutowania do pożądanego typu. Na przykład, gdy chcemy uzyskać liczbę z zakresu od 1 do 10, musimy posłużyć się takim kodem:
int liczbaLosowa = (int) (Math.random() * 10 + 1);
Często potrzebujemy liczbę z zadanego zakresu. Poniższa metoda losuj(int, int) generuje liczby losowe całkowite z zakresu przekazanego jako parametry jej wywołania.
/**
 * Generowanie liczb pseudolosowych
 * @author kodatnik.blogspot.com 
 */ 
public class LiczbyPseudolosowe {
  
 // metoda zwraca liczbę całkowitą z zakresu >= min do < max
 public static int losuj(int min, int max) {
  return (int) (Math.random() * (max - min) + min);
 }

 public static void main (String[] args) {
   
  // Losujemy 10 liczb całkowitych z zakresu od 20 do 40
  for (int i = 0; i < 10; i++) 
   System.out.print(losuj(20, 40) + " ");
 }
}
Uruchomiona aplikacja:
25 34 20 22 23 22 36 26 30 34

Wyszukiwanie maksymalnego elementu tablicy

Znalezienie maksymalnego elementu tablicy polega na przypisaniu do zmiennej wartości pierwszego elementu i przejściu przez pozostałe elementy tablicy. W przypadku gdy znajdziemy większy element, staje się on elementem największym. Poniżej prosta metoda znajdzMax(), która dla przekazanej jako parametr tablicy liczb całkowitych zwraca wartość maksymalną.
/**
 * Wyszukiwanie maksymalnego elementu w tablicy
 * @author kodatnik.blogspot.com 
 */ 
public class WyszukiwanieMaksimum {
 
 // metoda zwraca największy element z tablicy przekazanej jako parametr
 public static int znajdzMax(int[] wejscie) {
  
  // przypisujemy zmiennej max wartość pierwszego elementu
  int max = wejscie[0];   
  
  // sprawdzamy pozostałe elementy tablicy
  for (int i = 1; i < wejscie.length; i++) {
   // jeżeli element jest większy od dotychczasowego maksimum to on staje się maksimum
   if (wejscie[i] > max) 
    max = wejscie[i];   
  }
  
  // zwracamy wartość maksymalną
  return max;
 }
 
 // metoda wyświetla zawartość tablicy przekazanej jako parametr na ekranie
 public static void pokazTablice(int[] wejscie) {
  // każdy element znajdujący się w tablicy wyświetlamy na ekranie
  for(int x : wejscie) System.out.print (x + " ");
  System.out.println ();
 }

 public static void main(String[] args) {
  // tworzymy tablicę wypełniając ją od razu danymi
  int[] tablica = {4, 6, 1, 2, 3, 8, 7, 9, 5};
  
  // wyświetlamy tablicę na ekranie
  pokazTablice(tablica);  
  
  System.out.println ("Największy element tablicy to: " + znajdzMax(tablica));
 }
}
Uruchomiona aplikacja:
4 6 1 2 3 8 7 9 5 
Największy element tablicy to: 9
Często zamiast wartości potrzebujemy znaleźć indeks największego elementu. W przykładowym kodzie metody znajdzMax() zamiast zapamiętywać wartość największego elementu musielibyśmy zapisać indeks, na którym on się znajduje. Zmodyfikowana wersja metody poniżej.
// metoda zwraca indeks największego element z tablicy przekazanej jako parametr
 public static int znajdzMax(int[] wejscie) {
  
  // przypisujemy zmiennej max indeks pierwszego elementu
  int max = 0;   
  
  // sprawdzamy pozostałe elementy tablicy
  for (int i = 1; i < wejscie.length; i++) {
   // jeżeli element jest większy od dotychczasowego maksimum to zapamiętujemy jego indeks
   if (wejscie[i] > wejscie[max]) 
    max = i;   
  }
  
  // zwracamy indeks elementu największego
  return max;
 } 
Uruchomiona aplikacja:
4 6 1 2 3 8 7 9 5 
Indeks największego elementu tablicy to: 7
Dokładnie tak samo można znaleźć element najmniejszy. Wystarczy zmodyfikować warunek porównujący elementy ze sobą.

Odwracanie elementów w tablicy

Odwrócenie elementów w tablicy to zamiana ich miejscami. Ostatni element staje się pierwszym, pierwszy ostatnim, przedostatni drugim, drugi przedostatnim itd. Chcemy napisać metodę, która odwróci nam wszystkie elementy w przekazanej jako parametr tablicy liczb całkowitych.
/**
 * Odwracanie elementów w tablicy
 * @author kodatnik.blogspot.com 
 */ 
public class OdwracanieElementow {
 
 // metoda odwraca elementy w przekazanej jako parametr tablicy
 public static void odwroc(int[] wejscie) {
  
  // indeks pierwszego elementu
  int poczatek  = 0;          
  // indeks ostatniego elementu
  int koniec = wejscie.length-1;
  
  // dopóki indeks początkowy jest mniejszy od indeksu końcowego
  while (poczatek < koniec) {
   // zamieniamy elementy
   int pomoc = wejscie[poczatek]; 
   wejscie[poczatek]  = wejscie[koniec]; 
   wejscie[koniec] = pomoc;
     
   // przesuwamy się w kierunku środka wektora zwiększając i zmniejszając odpowiednio indeksy
   poczatek++;
   koniec--;
  }
 }
 
 // metoda wyświetla zawartość tablicy przekazanej jako parametr na ekranie
 public static void pokazTablice(int[] wejscie) {
  // każdy element znajdujący się w tablicy wyświetlamy na ekranie
  for(int x : wejscie) System.out.print (x + " ");
  System.out.println ();
 }

 public static void main(String[] args) {
  // tworzymy tablicę wypełniając ją od razu danymi
  int[] tablica = {4, 6, 1, 2, 3, 8, 7, 9, 5};
  
  // wyświetlamy tablicę na ekranie
  pokazTablice(tablica);  
  
  // odwracamy tablicę
  odwroc(tablica);

  // wyświetlamy odwróconą tablicę na ekranie
  pokazTablice(tablica);  
 }
}
Uruchomiona aplikacja:
4 6 1 2 3 8 7 9 5 
5 9 7 8 3 2 1 6 4 
Powyższą metodę można przeciążyć, tworząc metodę odwracającą tylko fragment tablicy (elementy od indeksu początkowego do indeksu końcowego przekazanego jako parametr). Poniżej przeciążona wersja metody.
// metoda odwraca fragment tablicy (od indeksu poczatek do indeksu koniec
 // w przekazanej jako parametr tablicy)
 public static void odwroc(int[] wejscie, int poczatek, int koniec) {
  
  // dopóki indeks początkowy jest mniejszy od indeksu końcowego
  while (poczatek < koniec) {
   // zamieniamy elementy
   int pomoc = wejscie[poczatek]; 
   wejscie[poczatek]  = wejscie[koniec]; 
   wejscie[koniec] = pomoc;
     
   // przesuwamy się w kierunku środka wektora zwiększając i zmniejszając odpowiednio indeksy
   poczatek++;
   koniec--;
  }
 } 
Wywołanie odwroc(tablica, 3, 6) spowoduje odwrócenie elementów od indeksu trzeciego do szóstego.
4 6 1 2 3 8 7 9 5 
4 6 1 7 8 3 2 9 5 
Przeciążanie metod to tworzenie metod o takich samych nazwach ale o innej liście parametrów (pod uwagę brana jest ilość parametrów oraz ich typ).

Wyszukiwanie binarne

Wyszukiwanie binarne optymalizuje algorytm poszukiwań do kilku kroków. Opiera się ono na podziale tablicy na dwie części i sprawdzeniu czy szukana wartość znajduje się na środku czy też jest mniejsza lub też większa od elementu środkowego. W zależności od wyniku szukamy dalej w lewej bądź też prawej części tablicy. Taki sposób jest analogiczny do wyszukiwania danych w książce telefonicznej czy też słowniku. Oczywiście tablica, w której szukamy musi być posortowana (w przykładzie wykorzystamy sortowanie przez wybieranie). Chcemy napisać metodę która umożliwi nam w sposób rekurencyjny odnalezienie w tablicy konkretnej wartości.
// wykorzystujemy klasę Scanner z pakietu java.util
import java.util.*;

/**
 * Wyszukiwanie binarne
 * @author kodatnik.blogspot.com 
 */ 
public class WyszukiwanieBinarne {
 
 // metoda sortuje elementy tablicy przekazanej jako parametr
 public static void sortowaniePrzezWybieranie(int[] wejscie) {
  // zmienna przechowująca rozmiar tablicy
  int rozmiarTablicy = wejscie.length;
  
  // pętla przejścia przez wszystkie elementy tablicy
  for (int i = 0; i < rozmiarTablicy; i++){
   // zakladamy, ze element na pozycji i jest najmniejszy
   int min = wejscie[i];
   // zapisujemy indeks tego elementu
   int indeks = i;
   
   // szukamy w pozostałej części tablicy elementu mniejszego niz min
   for (int j = i; j < rozmiarTablicy; j++){
    // jesli jest taki, on staje się teraz elementam najmniejszym
    if(wejscie[j] < min) {
     min = wejscie[j];
     // zapisujemy jego indeks
     indeks=j;
    }
   }
   // zamieniamy miejscami elementy w tablicy 
   // najmniejszy z aktualnym wskazywanym przez zmienną i
   wejscie[indeks] = wejscie[i];
   wejscie[i] = min;
  }
 }

 // metoda rekurencyjna szukająca w podanej jako parametr tablicy (od indeksu poczatek do indeksu koniec) wartości
 // zwraca -1 jeśli szukana wartość nie występuje, lub indeks pierwszego wystąpienia szukanej wartości
 // przekazana jako parametr tablica musi być wcześniej posortowana
 public static int szukajBinarnie(int[] wejscie, int poczatek, int koniec, int szukana) {

  // sprawdzamy czy przekazana tablica nie jest jednoelementowa
  if( poczatek == koniec) {
   // jeśli tak sprawdzamy czy element nie jest tym, którego szukamy (zwracamy indeks elementu, lub -1)
   if (wejscie[poczatek] == szukana) return poczatek;
   else return -1;
  }

  if( poczatek > koniec)
   // jeśli poczatek jest większy od końca kończymy wyszukiwanie zwracając -1
   return -1;  
  
  // dzielimy tablicę na dwie części
  int srodek = (poczatek+koniec)/2;
 
  // sprawdzamy czy element środkowy nie jest szukanym (jeśli tak zwracamy jego indeks)
  if(wejscie[srodek] == szukana) return srodek;

  // jeśli nie, wywołujemy rekurencyjnie naszą metodę dla prawej bądź też lewej części tablicy
  if(wejscie[srodek] > szukana) return szukajBinarnie(wejscie, poczatek, srodek-1, szukana);
  else return szukajBinarnie(wejscie, srodek+1, koniec, szukana);
 }
 
 // metoda wyświetla zawartość tablicy przekazanej jako parametr na ekranie
 public static void pokazTablice(int[] wejscie) {
  // każdy element znajdujący się w tablicy wyświetlamy na ekranie
  for(int x : wejscie) System.out.print (x + " ");
  System.out.println ();
 }

 public static void main(String[] args) {
  // tworzymy tablicę wypełniając ją od razu danymi
  int[] tablica = {4, 6, 1, 2, 3, 8, 7, 9, 5};
  
  // wyświetlamy tablicę nieposortowaną na ekranie
  System.out.print ("Tablica nieposortowana: " );
  pokazTablice(tablica);  
  
  Scanner sc = new Scanner(System.in);
  System.out.print ("Jaką wartość chcesz znaleźć w tablicy: " );

  // pobieramy od użytkownika liczbę
  int liczba = sc.nextInt();    

  // sortujemy tablicę
  sortowaniePrzezWybieranie(tablica);  
  
  // wyświetlamy tablicę posortowaną na ekranie
  System.out.print ("Tablica posortowana: " );
  pokazTablice(tablica);
  
  // wywołujemy metodę oraz zapisujemy to co zwróci
  int wynik = szukajBinarnie(tablica, 0, tablica.length-1, liczba);
  
  // jeśli wynik jest różny od -1 wyświetlamy informacje o indeksie, na którym została znaleziona wartość
  if (wynik != -1) System.out.println ("Liczba " + liczba + " została znaleziona w tablicy na indeksie: " + wynik);
  else System.out.println ("Liczba " + liczba + " nie została znaleziona w tablicy.");
 }
}
Uruchomiona aplikacja (wartość znaleziona):
Tablica nieposortowana: 4 6 1 2 3 8 7 9 5 
Jaką wartość chcesz znaleźć w tablicy: 3
Tablica posortowana: 1 2 3 4 5 6 7 8 9 
Liczba 3 została znaleziona w tablicy na indeksie: 2
Uruchomiona aplikacja (wartość nie znaleziona):
Tablica nieposortowana: 4 6 1 2 3 8 7 9 5 
Jaką wartość chcesz znaleźć w tablicy: 17
Tablica posortowana: 1 2 3 4 5 6 7 8 9 
Liczba 17 nie została znaleziona w tablicy.

Wyszukiwanie liniowe - sekwencyjne

Wyszukiwanie liniowe polega na sprawdzaniu kolejnych elementów tablicy i porównywaniu ich z szukaną wartością. Liczba porównań w najgorszym przypadku może osiągnąć rozmiar tablicy. Chcemy napisać metodę, która w podanej jako parametr tablicy znajdzie określoną wartość. W przypadku sukcesu metoda ma zwrócić indeks znalezionego elementu, a w przypadku nie znalezienia wartość -1.
// wykorzystujemy klasę Scanner z pakietu java.util
import java.util.*;

/**
 * Wyszukiwanie liniowe - sekwencyjne
 * @author kodatnik.blogspot.com 
 */ 
public class WyszukiwanieLiniowe {
 
 // metoda szukająca w podanej jako parametr tablicy wartości
 // zwraca -1 jeśli szukana wartość nie występuje, lub indeks pierwszego wystąpienia szukanej wartości
 public static int szukajLiniowo(int[] wejscie, int szukana) {
    
  // sprawdzamy kolejne elementy tablicy
  for (int i = 0; i < wejscie.length; i++) {
   // jeśli wartość elementu jest równa szukanej zwracamy indeks tego elementu
   if ( wejscie[i] == szukana) return i; 
  }
  // jeśli po przejściu całej tablicy nie znaleźliśmy szukanej wartości zwracamy -1
  return -1; 
 }

 // metoda wyświetla zawartość tablicy przekazanej jako parametr na ekranie
 public static void pokazTablice(int[] wejscie) {
  // każdy element znajdujący się w tablicy wyświetlamy na ekranie
  for(int x : wejscie) System.out.print (x + " ");
  System.out.println ();
 }

 public static void main(String[] args) {
  // tworzymy tablicę wypełniając ją od razu danymi
  int[] tablica = {4, 6, 1, 2, 3, 8, 7, 9, 5};
  
  // wyświetlamy tablicę na ekranie
  System.out.print ("Nasza tablica: " );
  pokazTablice(tablica);  
  
  Scanner sc = new Scanner(System.in);
  System.out.print ("Jaką wartość chcesz znaleźć w tablicy: " );

  // pobieramy od użytkownika liczbę
  int liczba = sc.nextInt();    

  // wywołujemy metodę oraz zapisujemy to co zwróci do zmiennej wynik
  int wynik = szukajLiniowo(tablica, liczba);
  
  // jeśli wynik jest różny od -1 wyświetlamy informacje o indeksie, na którym została znaleziona wartość
  if (wynik != -1) System.out.println ("Liczba " + liczba + " została znaleziona w tablicy na indeksie: " + wynik);
  else System.out.println ("Liczba " + liczba + " nie została znaleziona w tablicy.");
 }
}
Uruchomiona aplikacja (wartość znaleziona):
Nasza tablica: 4 6 1 2 3 8 7 9 5 
Jaką wartość chcesz znaleźć w tablicy: 7
Liczba 7 została znaleziona w tablicy na indeksie: 6
Uruchomiona aplikacja (wartość nie znaleziona):
Nasza tablica: 4 6 1 2 3 8 7 9 5 
Jaką wartość chcesz znaleźć w tablicy: 12
Liczba 12 nie została znaleziona w tablicy.

Paradoks dnia urodzin

Paradoks dnia urodzin związany jest z odpowiedzią na pytanie ile osób jest potrzebnych do tego, żeby prawdopodobieństwo, iż przynajmniej dwie z nich mają urodziny tego samego dnia było większe od 0,5. Odpowiedź jest zaskakująca, wystarczy 23 osoby. Chcemy napisać metodę która wykona n prób i zwróci nam średnią liczbę osób, dla których spełniony jest nasz warunek (dwie z nich mają urodziny tego samego dnia). Dla uproszczenia daty urodzin będziemy zapisywać w 365 elementowym wektorze wartości logicznych.
// wykorzystujemy klasę Scanner z pakietu java.util
import java.util.*;

/**
 * Paradoks dnia urodzin
 * @author kodatnik.blogspot.com 
 */ 
public class ParadoksDniaUrodzin { 

 // metoda zwraca średnią liczbę osób dla n prób (parametr wywołania)
 // potrzebnych do tego aby dwie z nich miały tego samego dnia urodziny
 public static double paradoks(int liczbaProb) {
  
  // zmienne okreslające ilość dni w roku oraz licznik osób
  int n = 365;
  int licznik = 0;
  
  // wykonujemy tyle prób ile chce użytkownik
  for (int i =0; i< liczbaProb; i++) {
   // tworzymy wektor z poszczególnymi dniami roku (domyślnie false)
   boolean[] dzienUrodzin = new boolean[n];
     
   // w pętli działającej dotąd, aż nie znajdziemy dwóch osób z taką samą datą urodzin
   while (true) {
    // zwiększamy licznik osób o jeden
    licznik++;
    // losujemy liczbę z zakresu od 0 do 364 (indeksy tablicy)
    int los = (int) (n * Math.random());
    
    // jeśli jest już osoba o takim samym dniu urodzin kończymy pętlę
    if (dzienUrodzin[los]) break;
    // jeśli nie wpisujemy true w odpowiedni dzień
    dzienUrodzin[los] = true;
   }
  }
  // zwracamy średnią liczbę osób (wszystkie / liczba prób)
  return ((double) licznik) / liczbaProb;
 }

 public static void main(String[] args) { 

  Scanner sc = new Scanner(System.in);
  System.out.print ("Podaj liczbę prób: " );
  
  // pobieramy od użytkownika liczbę prób
  int liczba = sc.nextInt();
  
  // wyświetlamy na ekranie średnią liczbę osób dla wszystkich prób
  System.out.println("Średnia liczba osób: " + paradoks(liczba));
  
  
 }
}
Uruchomiona aplikacja:
Podaj liczbę prób: 100
Średnia liczba osób: 23.01

Sprawdzamy poprawność numeru PESEL

PESEL to Powszechny Elektroniczny System Ewidencji Ludności. Za pomocą sumy kontrolnej możemy sprawdzić czy numer PESEL jest poprawny. Budowa numeru PESEL jest następująca: 1-2 cyfra - ostatnie dwie cyfry roku urodzenia, 3-4 cyfra - dwie cyfry miesiąca urodzenia, 5-6 cyfra - dwie cyfry dnia urodzenia, 7-10 cyfra - liczba porządkowa z oznaczeniem płci (parzysta - kobieta, nieparzysta - mężczyzna), 11 cyfra - suma kontrolna. Sam algorytm sprawdzania sumy kontrolnej polega na obliczeniu sumy przemnożonych cyfr z numeru PESEL (od 1 do 10) przez odpowiednie wagi (1,3,7,9,1,3,7,9,1,3). Wynik jest dzielony modulo 10, odejmowany od 10 i jeszcze raz dzielony modulo 10. Cyfra którą dostaniemy powinna być zgodna z 11 cyfrą numeru PESEL.
// wykorzystujemy klasę Scanner z pakietu java.util
import java.util.*;

/**
 * Sprawdzenie sumy kontrolnej w numerze PESEL
 * @author kodatnik.blogspot.com 
 */ 
public class Pesel {
 
 // metoda sprawdza poprawność numeru PESEL na podstawie sumy kontrolnej
 // zwraca true dla poprawnych i false dla niepoprawnych numerów
 public static boolean sprawdz(String pesel){
  // zakładamy tablicę z wagami
  int[] wagi = {1, 3, 7, 9, 1, 3, 7 ,9 ,1 ,3};

  // sprawdzamy długość PESEL'a, jeśli nie jest to 11 zwracamy false
  if (pesel.length() != 11) return false;
  
  // zakładamy zmienną będącą sumą kontrolną
  int suma = 0;
  
  // liczymy w pętli sumę kontrolną przemnażając odpowiednie
  // cyfry z PESEL'a przez odpowiednie wagi
  for (int i = 0; i < 10; i++)
     suma += Integer.parseInt(pesel.substring(i, i+1)) * wagi[i];
  
  // pobieramy do zmiennej cyfraKontrolna wartość ostatniej cyfry z PESEL'a   
  int cyfraKontrolna = Integer.parseInt(pesel.substring(10, 11));

  // obliczamy cyfrę kontrolną z sumy (najpierw modulo 10 potem odejmujemy 10 i jeszcze raz modulo 10)
  suma %= 10;
  suma = 10 - suma;
  suma %= 10;
  
  // zwracamy wartość logiczną porównania obliczonej i pobranej cyfry kontrolnej
  return (suma == cyfraKontrolna);
  
 }
 
 public static void main(String[] args){
  
  Scanner sc = new Scanner(System.in);
  System.out.print ("Podaj numer PESEL: " );
  
  // pobieramy od użytkownika PESEL
  String pesel = sc.nextLine();
  
  // wyświetlamy na ekranie informacje o poprawności sumy kontrolnej PESEL
  System.out.println("Twój PESEL jest " + ((sprawdz(pesel)) ? "poprawny." : "niepoprawny"));

 }
}
Uruchomiona aplikacja:
Podaj numer PESEL: 85032208451
Twój PESEL jest poprawny.
Powyższy algorytm nie sprawdza numeru PESEL pod względem nieprawidłowych danych (niewłaściwe numery miesięcy, dni). Zauważ PESEL: 66666666666 jest traktowany jako poprawny!
Dla określenia różnych lat (wieków) urodzenia dodaje się do numeru miesiąca następujące wartości: lata 1800-1899 - 80, lata 1900-1999 - 0, lata 2000-2099 - 20 itd.

Sortowanie szybkie - QuickSort

Sortowanie szybkie działa na zasadzie podziału tablicy na dwie części. Jedna z nich zawiera elementy o wartościach mniejszych, a druga elementy o wartościach większych od wartości elementu dzielącego (ang. pivot). Jako element dzielący można wybrać element środkowy, element pierwszy lub element ostatni. Każda z części tak podzielonej tablicy jest poddawana od nowa algorytmowi sortowania szybkiego.
/**
 * Sortowanie szybkie - QuickSort
 * @author kodatnik.blogspot.com 
 */ 
public class SortowanieSzybkie {
 // metoda zamienia miejscami elementy o indeksach i oraz j
 // w tablicy przekazanej jako parametr
 private static void zamien(int[] wejscie, int i, int j) {
  int temp = wejscie[i];
  wejscie[i] = wejscie[j];
  wejscie[j] = temp;
 }  
 
 // metoda dzieli tablicę (od indeksu p do indeksu k) na dwie części
 // - elementy mniejsze od wybranego elementu
 // - elementy większe od wybranego elementu
 private static int podzial(int[] wejscie, int p, int k) {
 
  // wybieramy element wg którego będziemy dzielić
  // np. element ostatni
  int element = wejscie[k];
  
  // ustalamy zakres na którym będziemy operować
  int i = p; 
  int j = k - 1;
  
  // pętla wyszukuje kolejne elementy większe i mniejsze od 
  // elementu dzielącego (zmienna element)
  while(i <= j) {
   while (wejscie[i] <= element && i < k) i++;
   while (wejscie[j] > element && j > p) j--;
   
   // jeśli elementy są na niewłaściwych pozycjach zamieniamy je
   if (i < j) zamien(wejscie, i, j);
   // jeśli indeksy się zrównają kończymy pętlę
   if (i == j) break;
  }
   
  // na końcu wstawiamy element dzielący na właściwą pozycję
  zamien(wejscie, i, k);
    
  // i zwracamy tę pozycję
  return i;
 } 
 
 // metoda sortuje elementy tablicy przekazanej jako parametr
 // dodatkowo w jej wywołaniu podajemy indeks pierwszego i ostatniego elementu
 public static void sortowanieSzybkie(int[] wejscie, int i, int j) {

  // jeśli indeksy są równe lub niepoprawne zakończ działanie
  if ( j <= i ) return;

  // dzielimy tablicę na części, indeks miejsca podziału zapisujemy w zmiennej os (oś)
  int os = podzial(wejscie, i, j);
  
  // rekurencyjnie dokonujemy posortowania lewej i prawej części naszej tablicy
  sortowanieSzybkie(wejscie, i, os-1);
  sortowanieSzybkie(wejscie, os+1, j);  
 }   
 
 // metoda wyświetla zawartość tablicy przekazanej jako parametr na ekranie
 public static void pokazTablice(int[] wejscie) {
  // każdy element znajdujący się w tablicy wyświetlamy na ekranie
  for(int x : wejscie) System.out.print (x + " ");
  System.out.println ();
 }

 public static void main(String[] args) {
  // tworzymy tablicę wypełniając ją od razu danymi
  int[] tablica = {4, 6, 1, 2, 3, 8, 7, 9, 5};
  
  // wyświetlamy tablicę na ekranie
  pokazTablice(tablica);
  // sortujemy tablicę
  sortowanieSzybkie(tablica, 0, tablica.length-1);
  // wyświetlamy posortowaną tablicę na ekranie
  pokazTablice(tablica);  
 }
}
Optymalizacja algorytmu polega na właściwym doborze elementu dzielącego. Najczęściej dokonuje się tego poprzez jego losowy wybór, bądź też wyznaczenie mediany z rozpatrywanych elementów.
Uruchomiona aplikacja:
4 6 1 2 3 8 7 9 5 
1 2 3 4 5 6 7 8 9 

Suma cyfr w liczbie rekurencyjnie

W jednym z wcześniejszych postów liczyliśmy sumę cyfr w liczbie za pomocą iteracji. Poniżej rozwiązanie tego zadania z wykorzystaniem rekurencji.
// wykorzystujemy klasę Scanner z pakietu java.util
import java.util.*;

/**
 * Suma cyfr w liczbie rekurencyjnie
 * @author kodatnik.blogspot.com 
 */ 
public class SumaCyfr {
 
 // metoda sumaCyfr zwraca sumę cyfr liczby 
 // przekazanej jako parametr jej wywołania
 public static int sumaCyfr(int liczba) {

  // jesli liczba mniejsza od 10 zwróć ją (warunek kończący wywołania rekurencyjne)
  if (liczba < 10)
   return liczba;

  // w przeciwnym razie bierzemy ostatnią cyfrę (modulo 10) plus rekurencyjne
  // wywołanie naszej metody z parametrem będącym liczbą bez ostatniej cyfry
  return (liczba % 10) + sumaCyfr(liczba / 10);
 }
 
 public static void main(String[] args){
  
  Scanner sc = new Scanner(System.in);
  System.out.print ("Podaj liczbę: " );
  
  // pobieramy od użytkownika liczbę
  int liczba = sc.nextInt();
  
  // wyświetlamy na ekranie sumę cyfr w liczbie
  System.out.println("Suma liczb: " + sumaCyfr(liczba));

 }
}
Uruchomiona aplikacja:
Podaj liczbę: 12345
Suma liczb: 15

Ciąg Fibonacciego rekurencyjnie i iteracyjnie

Ciąg Fibonacciego to ciąg liczb naturalnych określony wzorem f(n)=f(n-1)+f(n-2) dla danych f(0)=0 i f(1)=1. Chcemy napisać metodę obliczającą n-ty wyraz tego ciągu. Zastosujemy rozwiązanie rekurencyjne (metoda fibR()) oraz iteracyjne (metoda fibI()).
// wykorzystujemy klasę Scanner z pakietu java.util
import java.util.*;

/**
 * N-ty element ciągu Fibonacciego rekurencyjnie i iteracyjnie
 * @author kodatnik.blogspot.com 
 */ 
public class CiagFibonacciego {
 
 // metoda zwraca n-ty element ciągu Fibonacciego
 // wersja rekurencyjna 
 public static int fibR(int n) {
  
  if (n < 2) return n; // jeśli n<2 zwracamy n (dla zera 0 dla jedynki 1)
  
  return fibR(n-1) + fibR(n-2); // jeśli nie to zwracamy sumę elementu poprzedniego i jeszcze wcześniejszego
 }
 
 // metoda zwraca n-ty element ciągu Fibonacciego
 // wersja iteracyjna  
 public static int fibI(int n) {
  int elementA = 0; // zmienne pomocnicze symbolizujące
  int elementB = 1; // element poprzedni B i jeszcze wcześniejszy A
  
  int wynik = 0; // zmienna wynik, pod którą podstawimy obliczoną wartość
  
  if (n < 2) return n; // jeśli n<2 zwracamy n (dla zera 0 dla jedynki 1)
   
   // jeśli nie to liczymy n=ty element ciagu
   for(int i = 2; i <= n; i++){ 
    wynik = elementA + elementB; // pod wynik podstawiamy sumę poprzednich elementów
    elementA = elementB; // modyfikujemy zmienne przechowujące
    elementB = wynik;  // dwie ostatnie wartości
   }
  
  return wynik; // zwracamy wynik
 }
 
 public static void main(String[] args) {
  
  Scanner sc = new Scanner(System.in);
  System.out.print ("Który element ciągu Fibonacciego chcesz obliczyć: " );

  // pobieramy od użytkownika liczbę
  int n = sc.nextInt();

  // wyświetlamy na ekranie obliczony element
  System.out.println( n + "-ty element ciągu Fibonacciego (rekurencja) wynosi: " + fibR(n));
  System.out.println( n + "-ty element ciągu Fibonacciego (iteracja) wynosi: " + fibI(n));  
 
 }
}
Uruchomiona aplikacja:
Który element ciągu Fibonacciego chcesz obliczyć: 10
10-ty element ciągu Fibonacciego (rekurencja) wynosi: 55
10-ty element ciągu Fibonacciego (iteracja) wynosi: 55
Rozwiązanie rekurencyjne jest bardzo kosztowne. Sprawdź czas wykonania jednej i drugiej metody dla dużych n, bądź też liczbę rekurencyjnych wywołań potrzebnych do takich obliczeń.

Dodajemy Wykop do Bloggera

Wykop to serwis do którego możemy dodawać ciekawe strony. Każda dodana informacja jest oceniana i dyskutowana przez społeczność internautów. Od niej zależy czy dany wpis będzie popularny czy też nie. Jednym ze sposobów wzbogacenia Bloggera o możliwość dodawania wpisów do wykopu jest mój gadżet Podziel się. W tym poście przedstawię drugą możliwość. Na stronie wykopywarki mamy dostępne kilka kodów, które można umieścić bezpośrednio w szablonie naszej strony. Informacja o osobach, które również uznały nasz post za ciekawy (wykopały go) będzie na bieżąco aktualizowana. Pytanie tylko gdzie go wkleić. Możliwości jest kilka, albo na początku treści posta, albo w jego nagłówku, albo pod postem. Przyjrzyjmy zatem się standardowej wykopywarce (duża ikona z ilością wykopów). Zmodyfikujmy trochę kod tak, aby edytor Bloggera przyjął go bez zastrzeżeń.
<script language='javascript'>
var wykop_url=location.href;
var wykop_title=document.title; 
var wykop_desc=encodeURIComponent('Podaj opis');
var widget_bg='FFFFFF';
var widget_type='normal';
var widget_url='http://www.wykop.pl/widget.php?url='+(wykop_url)+'&amp;title='+(wykop_title)+'&amp;desc='+(wykop_desc)+'&amp;bg='+(widget_bg)+'&amp;type='+(widget_type);
document.write("<div style='float: right;'><iframe border='0' frameborder='0' scrolling='no' src='"+widget_url+"' style='border:none;width:72px;height:65px;overflow:hidden;margin:0;padding:0;'/></div>");
</script>
Dodałem dodatkowo umiejscowienie ikony (prawa strona - <div style='float: right;'>) oraz zamieniłem kilka znaków, które powodują błędy Bloggera. Mając już kod, spróbujmy go dodać do naszych postów, a dokładnie do tytułu posta. Logujemy się do Bloggera, wybieramy Układ/Edytuj kod HTML. Zaznaczamy Rozszerz szablony widżetów. W podglądzie źródła naszego szablonu szukamy (Ctrl+F) następującego fragmentu:
<b:includable id='post' var='post'>
  <div class='post hentry uncustomized-post-template'>
Wklejamy poniżej zmodyfikowany kod wykopu. Wszystko funkcjonuje prawidłowo przy wyświetlonych pojedynczych wpisach. Na stronie głównej naszego bloga ikonka wykopu będzie niestety starała się dodać adres bloga, a nie poszczególnych postów, więc....wykorzystamy wyrażenie warunkowe, które będzie dodawało wykopywarkę tylko na stronach postów, a nie na stronie głównej.
<b:if cond='data:blog.pageType != "index"'>
 Nasz zmodyfikowany kod wykopu
</b:if>
Efekt widoczny na moim blogu. Oczywiście możemy zmienić miejsce dodania ikony jak i również jej położenie (do prawej, do lewej, na środku itd.). Na przykład dodanie ikony do treści posta, to odnalezienie w szablonie następującego kodu:
<div class='post-body entry-content'>
...i wstawienie poniżej tego co poprzednio. Sposób ten umożliwia, w zależności od naszych preferencji, dodanie ikon/linków do dowolnych serwisów (zobacz np. serwis Wyczaj to)
Jeśli nie odpowiada nam duża ikona to możemy wybrać z wykopywarki kod obsługujący wersję compact.

Podziel się - gadżet do Bloggera

Często na blogach mamy możliwość dodania czytanego posta do serwisów społecznościowych takich jak Wykop czy Twitter. W Bloggerze jedyną normalną możliwością skorzystanie z tej formy promocji bloga jest pasek nawigacyjny (Navbar). Niestety nie jest on lubiany przez twórców blogów jak i również jego oferta serwisów jest minimalna (brak jakiegokolwiek rodzimego serwisu). Gdy nie ma tego czego potrzebujemy, musimy wziąć sprawy w swoje ręce. Napisałem prosty gadżet do Bloggera umożliwiający podzielenie się blogiem/postem w serwisach społecznościowych. Dodatek dostępny jest w ogólnodostępnym katalogu gadżetów Bloggera. Jak go dodać. Logujemy się do Bloggera, wybieramy Układ/Elementy strony. Na pokazanym widoku naszego bloga, klikamy Dodaj gadżet. Otworzy się okienko z możliwością wyboru i dodania gadżetu. Wybieramy Więcej gadżetów w pole wyszukiwania wpisujemy Podziel się (patrz obrazek). Po znalezieniu gadżetu możemy go dodać klikając ikonkę z plusem.



Dodatkowo możemy dokonać prostej konfiguracji wpisując inny tytuł, położenie ikonek oraz serwisy, które mają być obsługiwane (klikając aktualizacja, nasze ustawienia odświeżą się). Gadżet dostosuje do wybranych parametrów swoją wysokość.


Po dodaniu do bloga możemy umiejscowić go albo z boku (Sidebar) albo w dowolnym innym miejscu (wystarczy przeciągnąć prostokąt z gadżetem w inne miejsce układu strony). Wersja online gadżetu obok.
W zależności od tego czy jesteśmy na stronie głównej bloga czy też czytamy post, do serwisu społecznościowego trafi odpowiednio adres URL bloga, tytuł bloga, opis bloga lub też adres URL posta, tytuł posta.
Jeśli korzystasz z Bloggera w wersji angielskiej, to po kliknięciu Add a Gadget w pole wyszukiwania wpisz Sociable.

Aktualizacja: 15-02-2010
Dodana obsługa Google Buzz.

Aktualizacja: 01-04-2010
Poprawiona obsługa Wykopu.

Dodajemy Favicon do Bloggera

Standardowo Blogger udostępnia dla blogów pomarańczową ikonkę pojawiającą się przy pasku adresu naszej przeglądarki, Nic nie stoi na przeszkodzie, aby ją zmienić na własną bardziej oddającą treść naszego bloga. Plik ikony powinien mieć rozmiary 16x16 pikseli. Domyślny format to ICO (większość przeglądarek obsługuje również poprawnie pliki PNG i GIF). Do skonwertowania pliku graficznego do pliku ICO możemy wykorzystać darmowy program IrfanView, bądź też poszukać darmowych ikonek w sieci. Idealnie do tego nadaje się wyszukiwarka Google (wybieramy grafika/wyszukiwanie zaawansowane/określamy rozmiar 16x16). Wybrany obrazek musimy umieścić na serwerze i dokonać zmian w kodzie naszego szablonu (nadpisać domyślne ustawienia Bloggera). Logujemy się do Bloggera, wybieramy Układ/Edytuj kod HTML. W podglądzie źródła naszego szablonu szukamy (Ctrl+F) następującego fragmentu:
<b:include data='blog' name='all-head-content'/>
Jest to fragment odpowiedzialny za utworzenie zawartości nagłówka naszej strony. Poniżej powyższego kodu dopisujemy linijkę:
<link href='Adres URL pliku ikonki' rel='shortcut icon' 
type='image/vnd.microsoft.icon'/>
Gdzie Adres URL pliku ikonki to ścieżka dostępu do naszej ikonki (pliku z rozszerzeniem .ico). Efekt widoczny jest na moim blogu (zobacz w pasku tytułu przeglądarki).
Ikonki mogą być również animowane. Wykorzystywany jest do tego celu format GIF.
Rozmiar ikonki może być większy (np. 32x32 czy 48x48). Przeglądarka odpowiednio przeskaluje sobie nasz plik.

Zmieniamy tytuł strony w Bloggerze

Standardowo tytuł pojedynczego postu w Bloggerze jest umieszczany w kolejności (tytuł bloga + tytuł postu). Większość wyszukiwarek internetowych opiera swoje wyniki między innymi na tytule strony. Spróbujmy zatem zmienić kolejność elementów (najpierw tytuł posta, potem tytuł bloga). Logujemy się do Bloggera, wybieramy Układ/Edytuj kod HTML. W podglądzie źródła naszego szablonu szukamy (Ctrl+F) następującego fragmentu:
<title><data:blog.pageTitle/></title>
Jest to fragment odpowiedzialny za stworzenie tytułu strony. Zamieniamy go z następującym kodem:
<b:if cond='data:blog.url == data:blog.homepageUrl'>
<title><data:blog.pageTitle/></title>
<b:else/>
<title><data:blog.pageName/> | <data:blog.title/></title>
</b:if>
Dajemy Zapisz i gotowe. Powyższy fragment będzie tworzył tytuł strony w zależności od tego czy jesteśmy na stronie głównej (tytuł bloga) czy też na stronie konkretnego posta (tytuł posta | tytuł bloga). Oczywiście znak rozdzielający tytuły możemy wybrać dowolnie (w przykładzie jest to pionowa kreska). Efekt widoczny jest na moim blogu (zobacz w pasku tytułu przeglądarki).
Wszystkie tagi, z których możesz korzystać w swoim szablonie (np. <data:blog.title/> - tytuł bloga) znajdziesz tutaj (język ang.).

Populacja królików rekurencyjnie

Mamy takie zadanie: Każdego roku pewna populacja królików podwaja się. Jeżeli początkowo było m królików to ile ich będzie po n latach? Rozwiązanie rekurencyjne poniżej.
// wykorzystujemy klasę Scanner z pakietu java.util
import java.util.*;

/**
 * Populacja królików rekurencyjnie
 * @author kodatnik.blogspot.com 
 */ 
public class Kroliki {
 
 // metoda zwraca liczebność królików po określonej liczbie lat
 // parametry: m - liczebność początkowa, n - liczba lat
 public static int populacja(int m, int n) {
  // jeżeli liczba lat równa się jeden zwróć podwojoną liczbę królików
  // w przeciwnym wypadku wywołaj rekurencyjnie metodę zwiększając 
  // liczbę królików i zmniejszając liczbę lat
  if ( n == 1 ) return 2*m;
  else return populacja(2*m, --n);
 }

 public static void main(String[] args) {
  
  Scanner sc = new Scanner(System.in);
  System.out.print ("Podaj początkową populację królików: " );

  // pobieramy od użytkownika liczbę
  int m = sc.nextInt();

  System.out.print ("Podaj liczbę lat: " );

  // pobieramy od użytkownika liczbę
  int n = sc.nextInt();
    
  // wyświetlamy na ekranie obliczoną populacje królików
  System.out.println("Po " + n + " latach będzie " + populacja(m, n) + " królików");
 
 }
}
Przykładowe uruchomienie aplikacji (ach te króliki ;):
Podaj początkową populację królików: 100
Podaj liczbę lat: 10
Po 10 latach będzie 102400 królików

Silnia rekurencyjnie

Rekurencja to wywołanie z poziomu metody jej samej. Chcemy napisać metodę, która policzy wartość silni dla liczby przekazanej jako parametr. Wykorzystamy wywołania rekurencyjne.
// wykorzystujemy klasę Scanner z pakietu java.util
import java.util.*;

/**
 * Rekurencyjne liczenie silni
 * @author kodatnik.blogspot.com 
 */ 
public class Silnia {
 
 // metoda silnia zwraca silnię z liczby przekazanej jako parametr
 // obliczenie silni odbywa się za pomocą rekurencji
 public static int silnia(int wartosc) {
  // jeśli przekazany parametr jest równy zero to zwróć 1
  // a w przeciwnym wypadku zwróć wartość parametru * wywołanie metody silnia
  // z parametrem o jeden mniejszym
  if(wartosc == 0) return 1;
  else return wartosc * silnia(wartosc - 1);
 }

 public static void main(String[] args){
  
  Scanner sc = new Scanner(System.in);
  System.out.print ("Podaj liczbę: " );
  
  // pobieramy od użytkownika liczbę
  int liczba = sc.nextInt();
  
  // wyświetlamy na ekranie obliczoną silnię
  System.out.println(liczba + "! = " + silnia(liczba));
 
 }
}
Podając na wejściu liczbę 5 wywołamy metodę silnia z wartością pięć. Metoda zwróci nam wartość parametru razy ponowne wywołanie metody silnia z parametrem o 1 mniejszym itd. Czyli przebieg działania metody będzie wyglądał tak jak poniżej:
silnia(5)
   |
   5 * silnia(4)
          |
          4 * silnia(3)
                 |
                 3 * silnia(2)
                        |
                        2 * silnia(1)
                               |
                               1 * silnia(0)
                                      |
                                      1
 
Razem dostaniemy: 5*4*3*2*1*1 = 120
Przykładowe uruchomienie aplikacji:
Podaj liczbę: 5
5! = 120
Wywołania rekurencyjne są bardzo pamięciożerne. Pisząc aplikację dobrze jest zastanowić się czy wywołania iteracyjne nie będą bardziej efektywne. Istotny jest również warunek stopu (kończący wywołania rekurencyjne), bez niego rekurencja może prowadzić do zawieszenia się programu (błędy związane z przepełnieniem stosu - Stack Overflow).

Przydatna klasa Stoper

Czasami pisząc aplikację chcielibyśmy wiedzieć ile czasu wykonują się pewne jej fragmenty (pętle, zaawansowane obliczenia itp). Stwórzmy prostą klasę, która umożliwi nam włączenie i wyłączenie stopera oraz poda uzyskane czasy.
/**
 * Prosty stoper
 * @author kodatnik.blogspot.com 
 */
class Stoper {
 // pola prywatne klasy 
 // czas startu stopera
 private long start;
 // czas stopu stopera
 private long stop;
 // nazwa stopera
 private String nazwa;

 // konstruktor bezparametrowy
 public Stoper() {
  // przypisujemy pusty łańcuch do pola nazwa
  // wywołując konstruktor jednoparametrowy z naszej klasy
  this("");
 }
  
 // konstruktor z jednym parametrem - nazwa stopera
 public Stoper(String nazwa) {
  // przypisujemy do pola nazwa przekazany łańcuch tekstowy
  this.nazwa = nazwa;
 }
 
 // metoda uruchamiana przy starcie stopera
 public void start(){
  // pobieramy aktualny czas - start stopera
  start = System.currentTimeMillis();
 }
 
 // metoda zatrzymująca nasz stoper
 public void stop(){
  // pobieramy aktualny czas - stop stopera
  stop = System.currentTimeMillis();
 } 
  
 // metoda zwraca w sekundach czas pomiędzy uruchomieniem, a zatrzymaniem stopera
 public double pobierzWynik(){
  // zamiana milisekund na sekundy
  return (stop - start) / 1000.0;
 } 
 
 // przesłonięta metoda toString()
 public String toString(){
  // zwracamy w formie tekstowej informacje o naszym stoperze  
  return nazwa + ": " + this.pobierzWynik() + " s."; 
 }
}
Proste wykorzystanie naszej klasy:
// tworzymy obiekt klasy Stoper
Stoper stoper = new Stoper("Test");
// uruchamiamy stoper
stoper.start();

// tutaj instrukcje, których czas wykonania chcemy zmierzyć

// zatrzymujemy stoper
stoper.stop();
// wyświetlamy na ekranie uzyskany czas
System.out.println(stoper);

Do pobrania czasu uzyskanego przez nasz stoper możemy skorzystać z metody pobierzWynik().
Do pobrania czasu uzyskanego przez nasz stoper możemy skorzystać z metody pobierzWynik(). Dostaniemy wtedy liczbę sekund (typ double).
Metoda toString() konwertuje dowolny obiekt na łańcuch tekstowy. Każda klasa w Javie posiada tę metodę (jest ona dziedziczona z klasy Object). Możemy oczywiście przesłonić wersję oryginalną naszą własną tak jak zrobiliśmy to w klasie Stoper.
Operator this odnosi się do bieżącej instancji obiektu, ale również umożliwia odwołanie do dowolnego konstruktora wewnątrz klasy (odwołanie takie jest dokonywane na podstawie typu i liczby parametrów).

Sortowanie bąbelkowe

Chcemy napisać metodę, która posortuje nam przekazany jako parametr wektor liczb całkowitych metodą sortowania bąbelkowego. Sortowanie bąbelkowe polega na porównywaniu dwóch kolejnych elementów oraz ich zamianie jeśli nie są ułożone w odpowiedniej kolejności.
/**
 * Sortowanie bąbelkowe
 * @author kodatnik.blogspot.com 
 */ 
public class SortowanieBabelkowe {

 // metoda sortuje elementy tablicy przekazanej jako parametr 
 public static void sortowanieBabelkowe(int[] wejscie) {
  // porównujemy pary elementów w tablicy
  for (int i = wejscie.length-1; i > 1; i--) {
   for (int j = 0; j < i; j++) {
    // jeśli nie są one odpowiednio uporządkowane 
    // zamieniamy je miejscami
    if (wejscie[j] > wejscie[j+1]) {
     // zamiana elementów
     int x = wejscie[j];
     wejscie[j] = wejscie[j+1];
     wejscie[j+1] = x;
    }
   }
  }  
 } 
 
 // metoda wyświetla zawartość tablicy przekazanej jako parametr na ekranie
 public static void pokazTablice(int[] wejscie) {
  // każdy element znajdujący się w tablicy wyświetlamy na ekranie
  for(int x : wejscie) System.out.print (x + " ");
  System.out.println ();
 }

 public static void main(String[] args) {
  // tworzymy tablicę wypełniając ją od razu danymi
  int[] tablica = {4, 6, 1, 2, 3, 8, 7, 9, 5};
  
  // wyświetlamy tablicę na ekranie
  pokazTablice(tablica);
  // sortujemy tablicę
  sortowanieBabelkowe(tablica);
  // wyświetlamy posortowaną tablicę na ekranie
  pokazTablice(tablica);  
 }
}
Algorytm można zoptymalizować sprawdzając na bieżąco czy dane nie zostały już uporządkowane.
Uruchomiona aplikacja:
4 6 1 2 3 8 7 9 5 
1 2 3 4 5 6 7 8 9 

Sortowanie przez wstawianie

Chcemy napisać metodę, która posortuje nam przekazany jako parametr wektor liczb całkowitych metodą sortowania przez wstawianie. Sortowanie przez wstawianie polega na podziale wektora na dwie części, część posortowaną i część nieposortowaną. Bierzemy element z części nieposortowanej i wstawiamy na odpowiednie miejsce w części posortowanej (analogia z układaniem kart w dłoni).
/**
 * Sortowanie przez wstawianie
 * @author kodatnik.blogspot.com 
 */ 
public class SortowaniePrzezWstawianie {
 
 // metoda sortuje elementy tablicy przekazanej jako parametr
 public static void sortowaniePrzezWstawianie(int[] wejscie) {

  // pobieramy elementy z części nieposortowanej tablicy
  for (int i = 1; i < wejscie.length; i++) {
   // zapisujemy element w zmiennej
   int liczba = wejscie[i];
   // oraz jego indeks w tablicy
   int j = i;   
   // w pętli "robimy" dla niego miejsce w
   // posortowanej części tablicy
   while (( j > 0) && (wejscie[j-1] > liczba)) {
    wejscie[j] = wejscie[j-1];
    j--;
   }
   // wstawiamy go na odpowiednie miejsce
   wejscie[j] = liczba;
  }
 }
 
 // metoda wyświetla zawartość tablicy przekazanej jako parametr na ekranie
 public static void pokazTablice(int[] wejscie) {
  // każdy element znajdujący się w tablicy wyświetlamy na ekranie
  for(int x : wejscie) System.out.print (x + " ");
  System.out.println ();
 }

 public static void main(String[] args) {
  // tworzymy tablicę wypełniając ją od razu danymi
  int[] tablica = {4, 6, 1, 2, 3, 8, 7, 9, 5};
  
  // wyświetlamy tablicę na ekranie
  pokazTablice(tablica);
  // sortujemy tablicę
  sortowaniePrzezWstawianie(tablica);
  // wyświetlamy posortowaną tablicę na ekranie
  pokazTablice(tablica);  
 }
}
Algorytm wstawienia elementu na odpowiednie miejsce można zoptymalizować stosując wyszukiwanie binarne.
Uruchomiona aplikacja:
4 6 1 2 3 8 7 9 5 
1 2 3 4 5 6 7 8 9 

Sortowanie przez wybieranie

Chcemy napisać metodę, która posortuje nam przekazany jako parametr wektor liczb całkowitych metodą sortowania przez wybieranie. Sortowanie przez wybieranie polega na wyszukaniu elementu mającego znaleźć się na zadanym indeksie i zamianie miejscami z tym, który jest tam obecnie.
/**
 * Sortowanie przez wybieranie
 * @author kodatnik.blogspot.com 
 */ 
public class SortowaniePrzezWybieranie {
 
 // metoda sortuje elementy tablicy przekazanej jako parametr
 public static void sortowaniePrzezWybieranie(int[] wejscie) {
  // zmienna przechowująca rozmiar tablicy
  int rozmiarTablicy = wejscie.length;
  
  // pętla przejścia przez wszystkie elementy tablicy
  for (int i = 0; i < rozmiarTablicy; i++){
   // zakladamy, ze element na pozycji i jest najmniejszy
   int min = wejscie[i];
   // zapisujemy indeks tego elementu
   int indeks = i;
   
   // szukamy w pozostałej części tablicy elementu mniejszego niz min
   for (int j = i; j < rozmiarTablicy; j++){
    // jesli jest taki, on staje się teraz elementam najmniejszym
    if(wejscie[j] < min) {
     min = wejscie[j];
     // zapisujemy jego indeks
     indeks=j;
    }
   }
   // zamieniamy miejscami elementy w tablicy 
   // najmniejszy z aktualnym wskazywanym przez zmienną i
   wejscie[indeks] = wejscie[i];
   wejscie[i] = min;
  }
 }

 // metoda wyświetla zawartość tablicy przekazanej jako parametr na ekranie
 public static void pokazTablice(int[] wejscie) {
  // każdy element znajdujący się w tablicy wyświetlamy na ekranie
  for(int x : wejscie) System.out.print (x + " ");
  System.out.println ();
 }

 public static void main(String[] args) {
  // tworzymy tablicę wypełniając ją od razu danymi
  int[] tablica = {4, 6, 1, 2, 3, 8, 7, 9, 5};
  
  // wyświetlamy tablicę na ekranie
  pokazTablice(tablica);
  // sortujemy tablicę
  sortowaniePrzezWybieranie(tablica);  
  // wyświetlamy posortowaną tablicę na ekranie
  pokazTablice(tablica);  
 }
}
Uruchomiona aplikacja:
4 6 1 2 3 8 7 9 5 
1 2 3 4 5 6 7 8 9 

Palindrom

Palindrom to łańcuch tekstowy, który czytany normalnie jak i wspak daj taki sam ciąg. Chcemy napisać metodę, która zwróci nam prawdę jeśli przekazany jako argument łańcuch znaków jest palindromem, a fałsz jeśli nie jest.
// wykorzystujemy klasę Scanner z pakietu java.util
import java.util.*;

/**
 * Palindrom
 * @author kodatnik.blogspot.com 
 */ 
public class Palindrom {
 
 // metoda palindrom zwraca prawdę bądź fałsz 
 // dla przekazanego jako parametr łańcucha tekstowego
 public static boolean palindrom(String lancuch) {
  
  // tworzymy nowy obiekt klasy StringBuilder
  StringBuilder tekst = new StringBuilder(lancuch);
  
  // wykorzystujemu metodę reverse() do odwrócenia łańcucha
  // oraz equals() do sprawdzenia czy oba łańcuchy są takie same
  return lancuch.equals(tekst.reverse().toString());
 }

 public static void main(String[] args){
  
  Scanner sc = new Scanner(System.in);
  System.out.print ("Podaj łańcuch tekstowy: " );
  
  // pobieramy od użytkownika łańcuch tekstowy
  String lancuch = sc.nextLine();
  
  // wyświetlamy na ekranie informacje czy podany wyraz jest palindromem
  System.out.println("Łańcuch tekstowy: " + lancuch + (palindrom(lancuch) ? " jest" : " nie jest") + " palindromem"); 
 }
}
Pokazana metoda uwzględnia wielkość liter, wyraz Kajak nie będzie palindromem.
W programie zastosowano trójargumentowy operator ?:. Sprawdza on wyrażenie logiczne i zwraca dla prawdy wyrażenie występującą po ?, a dla fałszu po :. Jest to skrócona wersja if else.
Przykładowe uruchomienia programu:
Podaj łańcuch tekstowy: kajak
Łańcuch tekstowy: kajak jest palindromem
Podaj łańcuch tekstowy: marcin
Łańcuch tekstowy: marcin nie jest palindromem

Sito Eratostenesa

Sito Eratostenesa to algorytm wyznaczania liczb pierwszych z zakresu od 2 do n. Istotą algorytmu jest wykreślanie z danego zbioru 2..n wszystkich wielokrotności kolejnych liczb (zaczynając od dwójki), które nie zostały jeszcze wykreślone. Wystarczy uwzględnić tylko liczby z przedziału od 2 do wartości całkowitej pierwiastka z n. Niewykreślone liczby będą liczbami pierwszymi z podanego zakresu.
// wykorzystujemy klasę Scanner z pakietu java.util
import java.util.*;

/**
 * Sito Eratostenesa
 * @author kodatnik.blogspot.com 
 */
public class SitoEratostenesa {
 
 public static void main(String args[]) {
    
  Scanner sc = new Scanner(System.in);
  System.out.print ("Podaj n: " );   
    
  // pobieramy od użytkownika n (zakres)
  int n = sc.nextInt();    
      
  // obliczamy liczbę iteracji 
  int liczbaIteracji = (int) Math.sqrt(n);

  // zakładamy tablicę o rozmiarze n+1
  // domyślnie będzie ona miała wartości false
  boolean[] jestPierwsza = new boolean[n + 1];
       
  // zmieniamy na true (zakładamy, że wszysktie liczby
  // z przedziału 2..n są pierwsze)
  for (int i = 2; i < n+1; i++) jestPierwsza[i] = true;

  // główna pętla usuwająca wielokrotności kolejnych liczb pierwszych
  // poprzez wstawianie na odpowiednim indeksie ablicy wartości false
  for (int i = 2; i <= liczbaIteracji; i++) {

   // sprawdzamy czy pierwsza, jeśli nie to następna iteracja
   if (jestPierwsza[i]) {
    // jeśli pierwsza usuwamy jej wielokrotności wstawiając false na odpowiedni indeks tablicy
    for (int j = i * i; j <= n; j += i) jestPierwsza[j] = false;
   }
  }

  // pętla wyświetlająca liczby pierwsze z pzedzialu 2..n
  // jeśli wartość na indeksie i jest równa true to jest to liczba pierwsza
  for (int i = 2; i <= n; i++)
   if (jestPierwsza[i]) System.out.print(i + " ");
 }
}
Przykładowe uruchomienie programu:
Podaj n: 20
2 3 5 7 11 13 17 19

Liczby doskonałe

Liczba doskonała to liczba naturalna, która jest sumą wszystkich swych dzielników właściwych (np. liczba 6, gdyż 6=1+2+3). Chcemy napisać program, który znajdzie nam trzy pierwsze liczby doskonałe.
/**
 * Liczby doskonałe
 * @author kodatnik.blogspot.com 
 */
public class LiczbyDoskonale {
 
 public static void main(String[] args) {
  
  // deklaracja i inicjalizacja zmiennych
  // ile liczb doskonałych znaleziono
  int znaleziono = 0;
  // liczba początkowa
  int liczba = 1;
  
   // pętla while (działa dopóki nie znajdzie 3 liczb doskonałych)
   while( znaleziono < 3 ) {
    // zmienna przechowująca sumę dzielników
    int sumaDzielnikow = 0;
    
    // pętla licząca sumę dzielników danej liczby
    for( int i = 1; i < liczba; i++) {
      if ((liczba % i) == 0)
      sumaDzielnikow += i;
    } 
 
    // sprawdzamy czy suma dzielników jest równa danej liczbie
    if( sumaDzielnikow == liczba) {
     // jesli tak wyświetlamy ją na ekranie
     System.out.println("Liczba doskonała: " + liczba);
     // zwiększamy ilość znalezionych liczb
     znaleziono++;
    }
    // bierzemy kolejną liczbę
    liczba++;
   }
 }
}
Uruchomienie programu:
Liczba doskonała: 6
Liczba doskonała: 28
Liczba doskonała: 496
Algorytm możemy uprościć zmniejszając zakres pętli liczącej sumę dzielników (wystarczy sprawdzać liczby z zakresu od 1 do liczba/2). Dodatkowo możemy wykorzystać własność odkrytą przez Euklidesa: każda liczba doskonała jest liczbą parzystą.

Suma cyfr w liczbie

Zaczynamy. Prosta metoda obliczająca sumę cyfr w liczbie przekazanej jako parametr. Całość objaśniona mam nadzieję klarownie w komentarzach.
// wykorzystujemy klasę Scanner z pakietu java.util
import java.util.*;

/**
 * Suma cyfr w liczbie
 * @author kodatnik.blogspot.com 
 */
public class Test {
 
 // metoda sumaCyfr zwraca sumę cyfr liczby 
 // przekazanej jako parametr jej wywołania
 
 public static int sumaCyfr(int liczba) {
  // deklaracja i inicjalizacja zmiennej
  int suma = 0;
  
  do {
   // wyciagamy z liczby ostatnią cyfrę (modulo 10)
   int cyfra =  liczba % 10;
   // dodajemy ją do sumy
   suma += cyfra;
   // modyfikujemy liczbę (pozbywamy się ostatniej cyfry)
   liczba = (liczba - cyfra) / 10;
  
   // pętla działa dopóki liczba jest różna od zera 
  } while ( liczba != 0 );  
  
  // zwracamy do miejsca wywołania obliczoną sumę
  return suma;
 }

 public static void main(String[] args){
  
  Scanner sc = new Scanner(System.in);
  System.out.print ("Podaj liczbę: " );
  
  // pobieramy od użytkownika liczbę
  int liczba = sc.nextInt();
  
  // wyświetlamy na ekranie sumę cyfr w liczbie
  System.out.println("Suma cyfr: " + sumaCyfr(liczba));

 }
}
Przykładowe uruchomienie programu:
Podaj liczbę: 84521
Suma cyfr: 20

Popularne posty