Przetwarzanie danych: liczby, daty, algorytmy

1. Opakowanie typów prostych i autoboxing

• Integer
• Short
• Byte
• Long
• Float
• Double
• Boolean

import java.io.*;
import java.util.*;

public class Test1 {

  public static void main(String[] args) throws FileNotFoundException {
    ArrayList<Integer> list = new ArrayList<Integer>();
    Scanner in = new Scanner(new File("liczby.txt"));
    while (in.hasNextInt()) {
      Integer n = new Integer(in.nextInt());
      list.add(n);
    }
    
    Collections.sort(list);
    int wynik = list.get(0).intValue() + list.get(list.size()-1).intValue();
    System.out.println(wynik);
  }

} 

• przy przypisaniach,
• przy przekazywaniu argumentów (metodom i konstruktorom),
• przy zwrocie wyników.

public class AutoBoxing {

  private int intField;

  public AutoBoxing() {
    // Konwersje przy przypisaniu
    int x = 1;
    Integer a = x;
    int y = a;
    System.out.println("Konwersje przy przypisaniu: " + a + " " + y);

    // Konwersje przy wywołaniu metod
    methodInvocationConversion1(x);
    methodInvocationConversion2(a);

    // Konwersje przy zwrocie wyników  
    y = getIntFromInteger();
    a = getIntegerFromInt();
    System.out.println("Konwersje przy zwrocie wyniku: " + a + " " + y);
  }

  public AutoBoxing(Integer i) {
    intField = i;
    System.out.println("W konstruktorze bezparametrowym: " + intField);
  }
  
  void methodInvocationConversion1(Integer p) {
    System.out.println("Parametr Integer, argument int " + p);
  }

  void methodInvocationConversion2(int p) {
    System.out.println("Parametr int, argument Integer " + p);
  }

  int getIntFromInteger() {
    return new Integer(2);
  }

  Integer getIntegerFromInt() {
    return 2;
  }

  public static void main(String[] args) {
     new AutoBoxing();
     // Zauważmy, że konstruktor możemy wołać z arg. int lub Integer
     new AutoBoxing(3);
     new AutoBoxing(new Integer(3));
  }


}

public class Test1 {

  public static void main(String[] args) throws FileNotFoundException {
    ArrayList<Integer> list = new ArrayList<Integer>();
    Scanner in = new Scanner(new File("liczby.txt"));
    while (in.hasNextInt()) 
      list.add(in.nextInt());
    Collections.sort(list);
    int wynik = list.get(0) + list.get(list.size()-1);
    System.out.println(wynik);
  }

}

isDigit()            // czy znak jest znakiem cyfry

isLetter()           // czy znak jest znakiem litery

isLetterOrDigit()    // czy znak jest litera lub cyfra

isWhiteSpace()       // czy to "biały" znak (spacja, tabulacja etc.)

isUpperCase()        // czy to duża litera   

isLowerCase()        // czy to mała litera

public class MaxVal {

  public static void main(String[] args) {

    long sum = 0;
    for (int i=1; i <= Short.MAX_VALUE; i++) sum +=i;
    System.out.println(sum);

  }

}

2. Operacje na bitach

• jednoargumentowy operator uzupełnienia jedynkowego ~ ,
• dwuargumentowe operatory przesunięcia bitowego >> (w prawo) i << (w lewo) oraz operator przesunięcia bitowego w prawo bez propagacji bitu znakowego (>>>),
• dwuragumentowy operator koniunkcji bitowej &,
• dwuargumentowy operator bitowej różnicy symetrycznej ^ (wykluczające ALBO),
• dwuargumentowy operator alternatywy bitowej | .

public class Test {

  public static void main(String[] args) {
    byte b = Byte.MAX_VALUE;
    System.out.println(b + " " + (b << 1));
    System.out.println(b + " " + (byte) (b << 1));
    int i = Integer.MAX_VALUE;
    System.out.println(i + " " + (i << 1));
  }

}

Np. jeśli a1 = 5, a2 = 7, to logiczne operacje bitowe są przeprowadzane w następujący sposób:

public class Flags {

  public static void main(String[] args) {

    final int  FL1 = 0x01,    // stałe pokazujące które bity (flagi) mają
               FL2 = 0x02,    // być testowane lub ustawiane
               FL3 = 0x04,
               FL4 = 0x08;

    int flags = 0;
    flags = flags | FL1;                   // ustawia flagę 1 (najmłodszy bit)
    show("flags = flags | FL1",
          flags);
    flags = 0;
    flags =  flags | FL3;                  // ustawia flagę 3 (trzeci bit)
    show("flags = flags | FL3",
          flags);
    flags = 0;
    flags = flags | (FL1 | FL4);           // ustawia 1 i 4 flagę
    show("flags = flags | (FL1 | FL4)",
          flags);

   // czy flaga 1 ustawiona
   if ((flags & FL1) > 0) System.out.println("Flaga 1 ustawiona");
   else System.out.println("Flaga 1 NIE ustawiona");

   // czy flaga 2 ustawiona
   if ((flags & FL2) > 0) System.out.println("Flaga 2 ustawiona");
   else System.out.println("Flaga 2 NIE ustawiona");

   // czy flagi 1 i 4 ustawione (jednoczesnie)
   int mask = FL1 | FL4;
   if ((flags  &  mask) ==  mask) System.out.println("Flagi 1 i 4 ustawione");
   else System.out.println("Flagi 1 i 4 NIE ustawione");

   // czy flagi 1 i 2 ustawione (jednoczesnie)
   mask = FL1 | FL2;
   if ((flags & mask) == mask) System.out.println("Flagi 1 i 2 ustawione");
   else System.out.println("Flagi 1 i 2 NIE ustawione");

  }

  static void show(String s, int flags) {
    System.out.println(s);
    char[] bits =  Unspec.getBits(flags);
    System.out.println(new String(bits) + "   --- val: " + flags);
  }

}

public class Unspec {

  public static char[] getBits(byte v)  {
    return getBits(8, (long) v);
  }

  public static char[] getBits(char v)  {
    return getBits(16, (long) v);
  }


  public static char[] getBits(int v)  {
    return getBits(32, (long) v);
  }


  public static char[] getBits(long v)  {
    return getBits(64, v);
  }

  private static char[] getBits(int n, long v)  {
    char[] bits = new char[n];
    long mask = 1;
    for (int k = n-1; k >= 0; k--) {
      if ((v & mask) != 0) bits[k] = '1';
      else bits[k] = '0';
      mask =  mask << 1;
    }
    return bits;
  }
}

class Test {
  public static void main(String[] args) {
    long l = Long.parseLong(args[0]);
    int i  = Integer.parseInt(args[1]);
    char c = args[2].charAt(0);
    byte b = Byte.parseByte(args[3]);
    System.out.println("Wartość typu long " + l);
    System.out.println(new String(getBits(l)));
    l = Long.MAX_VALUE;
    System.out.println("Maksymalna wartość typu long " + l);
    System.out.println(new String(getBits(l)));
    l = Long.MIN_VALUE;
    System.out.println("Minimalna wartość typu long " + l);
    System.out.println(new String(getBits(l)));
    System.out.println("Wartość typu int " + i);
    System.out.println(new String(getBits(i)));
    System.out.println("Wartość typu char: znak " + "'" + c + "'" + ", kod " + (int) c);
    System.out.println(new String(getBits(c)));
    System.out.println("Wartość typu byte " + b);
    System.out.println(new String(getBits(b)));
  }
}

• toBinaryString(..) zwraca napis -bitową reprezentację liczby) ,
• rotateLeft(...) i rotateRight(...) -  rotacja (w lewo,w prawo) o podaną liczbę bitów,
• bitCount(...) - zwraca liczbę bitów jedynkowych w bitowej reprezentacji liczby.

public class BitFun {
  
  static void show(int x) {
    System.out.println("Wartość: " + x);
    String s = Integer.toBinaryString(x);
    System.out.println("Bity: " + s);
    System.out.println("Liczba jedynek: " + Integer.bitCount(x));
    System.out.println("Liczba wiodących zer: " + Integer.numberOfLeadingZeros(x));
    System.out.println("Liczba zer na końcu: " + Integer.numberOfTrailingZeros(x));
  }

  public static void main(String[] args) {
    int x = 101;
    show(x);
    System.out.println("Po rotacji w lewo o 1 pozycję");
    show(Integer.rotateLeft(x, 1));
    System.out.println("Po rotacji w prawo o 1 pozycję");
    show(Integer.rotateRight(x, 1));
    System.out.println("Po odwróceniu bitów");
    show(Integer.reverse(x));
    System.out.println("Po odwróceniu bajtów");
    show(Integer.reverseBytes(x));
  }

}

3. Działania matematyczne

• specjalne wartości dla liczb typu double,
• "bibliotekę" funkcji matematycznych,
• reprezentację i precyzję liczb rzeczywistych,
• możliwość posługiwania się dowolnie dużymi liczbami dziesiętnymi w dowolnej precyzju.
  

public class InfNan {

  public static void main(String[] args) {

    double d = 1.0 / 0.0;
    System.out.println("d = " + d);
    if (d == Double.POSITIVE_INFINITY)
     System.out.println("to jest + nieskończoność");
    d = -1.0 / 0.0;
    System.out.println("d = " + d);
    if (d == Double.NEGATIVE_INFINITY)
     System.out.println("to jest - nieskończoność");
    d = 0.0 / 0.0;
    System.out.println("d = " + d);
    if (d == Double.NaN)
     System.out.println("to nie jest liczba");
    else System.out.println("to jest liczba");
    Double dd = new Double(d);
    System.out.println("naprawdę: to nie jest liczba ? - " + dd.isNaN());

  }

}

import static javax.swing.JOptionPane.*;
import java.util.*;

public class Toto {

  public static void main(String[] args) {
    String msg = "Podaj magiczne liczby,\n" +
                 "nic nie wpisuj = automatyczna inicjacja,\n" +
                 "lub wybierz Cancel, by skończyć losowania";
    
    Random rand;                          // generator

    boolean[] isDrawn = new boolean[49];  // i-ty element tablicy
                                          // ma wartość true
                                          // gdy liczba i została wylosowana
                                          // inicjalnie jest false (żadna nie wylosowana)  

    String inp;
    while ((inp = showInputDialog(msg)) != null) {

      if (!inp.equals("")) {  // inicjacja generatora sumą podanych liczb
         Scanner sc = new Scanner(inp);
         long sum = 0;
         while (sc.hasNextInt()) sum += sc.nextInt();
         rand = new Random(sum);
      }
      else rand = new Random();  // gdy nic nie podano - inicjacja czasem

      // Losowanie

      final int ILE = 6;  // liczb do wylosowania
      int k = 0;          // licznik niepowtarzających się liczb

      String out = "";   // tu będzie wynik 
      while (k < ILE) {
        int n = rand.nextInt(49);  // losowanie:  0 <= n < 49
        if (isDrawn[n]) continue;  // jeżeli ta liczba już była wylosowana
        else {                     // nie była - bierzemy ją!
          k++;                     // licznik wziętych + 1
          isDrawn[n] = true;       // teraz jest naprawdę wylosowana
          out += " " + (n+1);      // n+1, bo mamy mieć od 1 do 49
        }
      }
      showMessageDialog(null, "Wylosowane liczby:\n" + out);
    }
  }

}

public class FloatRep {

  public static void main(String[] args) {
    double liczba = 3 * 0.2;
    double wynik  = 0.6;
    if (liczba != wynik)
       System.out.println("Nie równe. Różnica wynosi: " + (liczba - wynik));
    else System.out.println("Równe");

  }

}

   double licz2 = 0.1111111111111111,
          licz3 = 1111 + licz2,
          licz4 = licz3 - 1111;

   System.out.println(licz4 - licz2);

import java.math.*;

public class BigDec {

  public static void main(String[] args) {
    BigDecimal liczbaA = new BigDecimal("3");
    BigDecimal liczbaB = new BigDecimal("0.2");
    BigDecimal wynik  = liczbaA.multiply(liczbaB);
    if (!wynik.equals(new BigDecimal("0.6")))
       System.out.println("Nie równe.");
    else System.out.println("Równe");

    BigDecimal licz2 = new BigDecimal("0.111111111111111111111111111111111"),
               licz1111 = new BigDecimal("1111"),
               licz3 = licz1111.add(licz2),
               licz4 = licz3.subtract(licz1111);

    System.out.println(licz3);
    System.out.println(licz4);
    System.out.println(licz4.subtract(licz2).toPlainString());

  }

}

import static java.lang.Math.*;
public class Ulp1 {

  public static void main(String[] args) {
    double d1 = 1;
    System.out.println("Dla wartości:" + d1);
    System.out.println("ULP: " + ulp(d1));
    System.out.println("Następna możliwa liczba: " + nextUp(d1));
  }

}

  public static void main(String[] args) {
    double d1 = 1e16,
           d2 = d1;
    for(int i = 1; i<=1000000; i++) d2++;
    System.out.println("Różnica: " + (d2 - d1));
  }

4. Daty i czas

import java.util.*;
import static java.util.Calendar.*;

public class Kal1 {

  public static void say(String s) { System.out.println(s); }

  public static void main(String[] args) {

    // uzyskanie kalendarza domyślnego
    // (obowiązującgo dla domyślnej lokalizacji - tu dla Polski)
    // ustawionego na bieżącą datę i czas

    Calendar cal = Calendar.getInstance();

    say("ERA.............. " + cal.get(ERA) +
        " (tu: 0=pne, 1=AD)");

    say("ROK.............. " + cal.get(YEAR));
    say("MIESIĄC.......... " + cal.get(MONTH) +
        " (0-styczeń, 2-luty, ..., 11-grudzień)");

    say("LICZBA DNI\n" +
        "W MIESIĄCU....... " + cal.getActualMaximum(DAY_OF_MONTH));

    say("DZIEŃ MIESIĄCA... " + cal.get(DAY_OF_MONTH));
    say("DZIEŃ MIESIĄCA... " + cal.get(DATE));
    say("TYDZIEŃ ROKU..... " + cal.get(WEEK_OF_YEAR));
    say("TYDZIEŃ MIESIĄCA. " + cal.get(WEEK_OF_MONTH));
    say("DZIEŃ W ROKU..... " + cal.get(DAY_OF_YEAR));

    say("PIERWSZY DZIEŃ\n" +
        "TYGODNIA......... " + cal.getFirstDayOfWeek() +
        " (1-niedziela, 2-poniedziałek, ..., 7 sobota)");

    say("DZIEŃ TYGODNIA... " + cal.get(DAY_OF_WEEK) +
        " (1-niedziela, 2-poniedziałek, ..., 7-sobota)");

    say("GODZINA.......... " + cal.get(HOUR) +
        " (12 godzinna skala; następne odwolanie czy AM czy PM)");

    say("AM/PM............ " + cal.get(AM_PM) +
        " (AM=0, PM=1)");

    say("GODZINA.......... " + cal.get(HOUR_OF_DAY) +
        " (24 godzinna skala)");

    say("MINUTA........... " + cal.get(MINUTE));
    say("SEKUNDA.........  " + cal.get(SECOND));
    say("MILISEKUNDA:      " + cal.get(MILLISECOND));

    int msh = 3600*1000; // liczba milisekund w godzinie

    say("RÓŻNICA CZASU\n" +
        "WOBEC GMT........ " + cal.get(ZONE_OFFSET)/msh);

    say("PRZESUNIĘCIE\n" +
        "CZASU............ " + cal.get(DST_OFFSET)/msh +
        " (w Polsce obowiązuje w lecie)");

  }

}

• set - ustala wartość pola; jeśli trzeba  dostosowując inne pola (np. ustawienie pola DAY_OF_MONTH na wartość 31 dla kalendarza ustawionego na dowolną datę w czerwcu spowoduje, że kalendarz będzie wskazywał na 1 lipca, gdyż w czerwcu jest tylko 30 dni),
• add  - dodaje do pola podaną wartość, stosując przy tym arytmetykę kalendarzową (np. dodanie do 30 maja 2 dni spowoduje ustawienie kalendarza na  1 czerwca),
• roll - również wykonuje dodawanie, ale przy tym nie zmienia wartości "starszych" pól np. jeżeli dodajemy dni i okaże się, że nowa data znajdzie się w innym niż teraz miesiącu, to miesiąc nie zostanie zmieniony, zaś "nadwyżka" dni (poza końcem bieżącego miesiąca) będzie dodawana od początku miesiąca.

import java.util.*;
import javax.swing.*;

public class TestKal {

  public static void main(String[] args) {
    String in;
    int d = 0;
    while ((in = JOptionPane.showInputDialog("DATE:")) != null) {
      d = Integer.parseInt(in);
      show("set",  "DATE", Calendar.DATE, d);
      show("add",  "DATE", Calendar.DATE, d);
      show("roll", "DATE", Calendar.DATE, d);
    }
    System.exit(0);
  }

  static void say(String s) { System.out.println(s); }


  static void show(String oper, String what, int field, int value) {
    Calendar c = Calendar.getInstance();
    say("Teraz jest: " + c.getTime());
    say("Operacja: " + oper + "(Calendar." + what + ", " + value + ")");
    if (oper.equals("set")) c.set(field, value);
    else if (oper.equals("add")) c.add(field, value);
         else if (oper.equals("roll")) c.roll(field,value);

    say("Aktualne ustawienia kalendarza: " + c.get(Calendar.YEAR) + '-'
                               + (c.get(Calendar.MONTH) + 1) + '-' +
                               + c.get(Calendar.DATE));
     say("-----------------------------------------------------------");
  }

}

5. Formatowanie liczb i dat

import java.util.*;

public class BrakFormat {

  public static void main(String[] args) {
    double cena = 1.52;
    double ilosc = 3;
    double koszt = cena * ilosc;
    System.out.println("Koszt wynosi: " + koszt);
    Calendar c = Calendar.getInstance();
    System.out.println("Data: " + c.getTime());
  }

}

• destynację formatowanych danych (dokąd mają być zapisane), którą m.in. może być String, StringBuffer, plik tekstowy,

• lokalizację (ustawienia regionalne, reprezentowane przez obiekt klasyLocale), wpływającą  m.in. na reprezentację liczb i dat,

• stronę kodową (do kodowania napisów) - m.in. dla plików i Stringów

• statyczne metody format w klasie String, pozwalające na uzyskiwanie sformatowanych napisów,
• metody format i printf (działające tak samo) w klasach PrintStream i PrintWriter, wyprowadzające sformatowane napisy "na wyjście" (np. na standardowe wyjście lub do pliku).

import java.util.*;

public class Format1 {

  public static void main(String[] args) {
    double cena = 1.52;
    double ilosc = 3;
    double koszt = cena * ilosc;
    System.out.printf("Koszt wynosi %.2f zł", koszt);
    System.out.printf("\nData: %tF", Calendar.getInstance());
  }

}

System.out.printf(Locale.ROOT, "Koszt wynosi %.2f zł", koszt);

import javax.swing.*;

public class Format2 {

  public static void main(String[] args) {
    System.out.println("Wyrównany wydruk tablicy (po 2 elementy w wierszu)");
    int[] arr = { 1, 100, 200, 4000 };
    int k = 1;
    for (int i : arr) {
      System.out.printf("%5d", i);
      if (k%2 ==0) System.out.println();
      k++;
    }
    // Zastosowanie znaku < (elment formatu stosowany wobec argumentu z poprzedniego formatowania)
    System.out.println("Zaokraglenia");
    System.out.printf("%.3f %<.2f %<.1f", 1.256 );
    
    // Znak < szczególnie przydatny w datach/czasie
    Calendar c = Calendar.getInstance();
    c.set(Calendar.MONTH, 1);
    System.out.printf("\nW roku %tY i miesiącu %<tm mamy %d dni", c, c.getActualMaximum(Calendar.DATE) );
    
    // Oczywiście możemy formatować do Stringów
    String dateNow = String.format("%td-%<tm-%<tY", System.currentTimeMillis());
    JOptionPane.showMessageDialog(null, dateNow);
  }

}

6. Proste sortowanie i wyszukiwanie

• lista plików uporządkowanych według nazw lub według daty ostatniej modyfikacji,
• lista 10 pierwszych zawodników, którzy zdobyli najwięcej punktów.

  public void selectionSort(int[] a) {

    // toInd - oznacza ostatni indeks nieposortowanej części tablicy
    // na początku jest to ostatni indeks tablicy
    // w kolejnych krokach toInd będzie zmniejszany o 1
    // bo zmniejszają się rozmiary nieposortowanej częsci tablicy

    // Gdy toInd osiągnie wartość 0 - "nieposortowany" będzie pierwszy
    // element. Ale nie mamy go już gdzie przstawić, faktycznie znajduje się
    // on na własciwym miejscu.
    // Zatem nie musimy dokonywać żadnego przestawienia.
    // Tablica jest posortowana. Kończymy pętle.

    for (int toInd=a.length-1; toInd>0; toInd--) {

      int indMax = 0;   // indeks maksymalnego elementu
                        // w nieposortowanej części tablicy

      // szukamy tego indeksu, przeglądając nieposortowaną część tablicy
      for (int k=1; k <= toInd; k++)
 	if (a[indMax] < a[k]) indMax = k;

      // Przestawiamy elementy:
      // maksymalny element idzie na ostatnią pozycję w nieposortowanej
      // części tablicy; a liczba spod tego indeksu jest zapisywana
      // w miejscu okupowanym poprzednio przez max element

      int temp = a[toInd];
      a[toInd] = a[indMax];
      a[indMax] = temp;
    }
  }

import java.util.*;

public class SelSort {

  public SelSort(int n, int m) {

    Random rand = new Random();

    int[] a = new int[n];
    for (int i=0; i < n; i++) {
      a[i] = rand.nextInt(m+1);
      System.out.print(" " + a[i]);
    }
    selectionSort(a);
    System.out.print('\n');
    for (int i=0; i < n; i++) System.out.print(" " + a[i]);
  }

  public void selectionSort(int[] a) {
    // ...
  }


  public static void main(String[] args) {
     new SelSort(Integer.parseInt(args[0]), Integer.parseInt(args[1]));
   }

}

import java.util.*;

class QTimer {

   private final long start;

   public QTimer() {
     start = System.currentTimeMillis();
   }

   public long getElapsed() {
      return System.currentTimeMillis() - start;
   }
}


public class SelSort1 {

static public void selectionSort(int[] a) {
// ... jak na poprzednim wydruku
}


  public static void main(String[] args) {
    int n = Integer.parseInt(JOptionPane.showInputDialog("Liczba elementów w tablicy"));
    Random rand = new Random();
    int[] a = new int[n];
    int[] b = new int[n];
    for (int i = 0; i < n; i++) {
      a[i] = rand.nextInt(n * 10);
      b[i] = a[i];
    }
    System.out.println("Liczba elementów tablicy " + n);
    QTimer qt = new QTimer();
    selectionSort(a);
    System.out.println("Czas selection sort: " + qt.getElapsed());
    qt = new QTimer();
    Arrays.sort(b);
    System.out.println("Czas quicksort: " + qt.getElapsed());
  }
}

public class SortString {

  static public void selectionSort(String[] s) {
    for (int toInd=s.length-1; toInd>0; toInd--) {
      int indMax = 0;
      for (int k=1; k <= toInd; k++)
 	if (s[indMax].compareTo(s[k]) < 0) indMax = k;
      String temp = s[toInd];
      s[toInd] = s[indMax];
      s[indMax] = temp;
    }
  }


  public static void show(String[] s) {
    System.out.print('\n');
    for (int i=0; i < s.length; i++) System.out.print(" " + s[i]);
  }


  public static void main(String[] args) {
    String[] s =  {"A", "Z", "C", "B", "1", "3", "2", "A", "C" };
    show(s);
    selectionSort(s);
    show(s);
  }

}

public class Search {

  public static int linearSearch(int[] tab, int v) {
    for (int i=0; i < tab.length; i++)
      if (tab[i] == v) return i;
    return -1;
  }

}

public class Search {

  // v - poszukiwana wartość w tablicy tab
  static public int binarySearch(int[] tab, int v)   {
    int low = 0;                // lewy skrajny indeks "aktualnej" połówki
    int high = tab.length - 1;  // prawy skrajny indeks "aktualnej" połowki

    // dopóki możemy dzielić tablicę
    while (low <= high) {
      int mid = (low + high) / 2;  // indeks środkowego elementu
                                   // zakresu low..high

      if (v  < tab[mid])         // jeżeli wartość jest w lewej połówce:
        high = mid - 1;          // zmodyfikować skrajny prawy indeks
      else if (v > tab[mid])     // w przeciwnym razie jeżeli w prawej połówce:
              low = mid + 1;     // zmodyfikować skrajny lewy indeks
           else return mid;      // w przeciwnym razie: zanleziony!
    }
    return -1;                    // w tablicy nie znaleziono wartości v
  }

7. Rekurencja

public class Recurs {

  public static void show1(int i) {
    System.out.println("show1 " + i);
    if (i > 10) return;
    show1(i+1);
  }

  public static void main(String[] args) {
    show1(1);
 }

}

  public static void show2(int i) {
    if (i > 10) return;
    show2(i+1);
    System.out.println("show2 " + i);
  }

public class Recurs {

  public static int sum(int n) {
    if (n == 1) return 1;
    else return n + sum(n-1);
  }

  public static void main(String[] args) {
    System.out.println(sum(100));
  }

}

0  1  1  2  3  5  8 13 21 34 55 89 144 233 377 610 987 ...

  int fib(int n) {
    if (n < 2) return n;
    else return fib(n-1) + fib(n-2);
  }

  int fib(int n) {
    System.out.println("Wywołanie fib z argumentem " + n);
    int wynik = 0;
    if (n < 2) wynik = n;
    else wynik = fib(n-1) + fib(n-2);
    System.out.println("Zwrot wyniku: " + wynik);
    return wynik;
  }

public class ShowFibRec {

  int[] calls;

  ShowFibRec(int n) {
    calls = new int[n+1];
    fib(n);
    for(int i=0; i <= n; i++)
      System.out.println("Liczba wywołań fib z argumentem " + i
                          + " " + calls[i]);
  }

  int fib(int n) {
    calls[n]++;
    if (n < 2) return n;
    else return fib(n-1) + fib(n-2);
  }

  public static void main(String[] args) {
    int n = Integer.parseInt(args[0]);
    new ShowFibRec(n);
  }

}

8. Niezmienniki pętli iteracyjnych

 static int getMin(int[] a) {
   int n = a.length;
   int vmin = a[0];
   int i = 1;
   while (i < n) {
     if (a[i] < vmin) vmin = a[i];
     i++;
   }
   return vmin;
 }

 static int getMin(int[] a) {
   int n = a.length;
   int vmin = a[0];
   int i = 1;
   // N0
   while (i < n) {
     // N1
     if (a[i] < vmin) vmin = a[i];
     i++;
     // N2
   }
   // N3
   return vmin;
 }

  static int getMin(int[] a) {
    int vmin = a[0];
    for (int i=1; i < a.length; i++) {
      // NIEZMIENNIK: vmin == minimum (a[0],.. a[i-1])
      if (a[i] < vmin) vmin = a[i];
    }
    // NIEZMIENNIK: vmin == minimum (a[0],.. a[i-1])
   return vmin;
     
  }

9. Podsumowanie

• opakowanie typów prostych i autoboxing,
• operacje na bitach,
• działania matematyczne na liczbach rzeczywistych,
• posługiwanie się datami,
• formatowanie liczb i dat,
• proste algorytmy sortowania i wyszukiwania,
• pojęcie rekurencji, która pozwala niektóre algorytmy zapisywać w bardzo naturalny i intuicyjny sposób