października 2009

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:

1.<b:includable id='post' var='post'>

2. <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:

1.<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:

1.<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ę:

1.<link href='Adres URL pliku ikonki' rel='shortcut icon'

2.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:

1.<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.).

Kodatnik

Odwracanie elementów w tablicy

Wyszukiwanie binarne

Wyszukiwanie liniowe - sekwencyjne

Paradoks dnia urodzin

Sprawdzamy poprawność numeru PESEL

Sortowanie szybkie - QuickSort

Suma cyfr w liczbie rekurencyjnie

Ciąg Fibonacciego rekurencyjnie i iteracyjnie

Dodajemy Wykop do Bloggera

Podziel się - gadżet do Bloggera

Dodajemy Favicon do Bloggera

Zmieniamy tytuł strony w Bloggerze

Popularne posty

Sponsorzy

Etykiety

Archiwum

Obserwatorzy

Dołącz do nas

Statystyka