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

Popularne posty