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