Programmeerimise eriteemasid - rekursioon, otsimine, järjestamine

Rekursioon


Rekursiivne algoritm sisaldab sellesama algoritmi poole pöördumist mingi "lihtsama juhu" jaoks.

Tavaliselt saab eristada rekursiooni baasjuhtu ja sammu - analoogia matemaatilise induktsiooniga.


Näide. Faktoriaal

0! = 1
n! = n * (n-1)!    , kui n>0



Rekursioon ei pruugi olla läbinähtav ülesande sõnastuses
Näide. Hanoi tornid

On n erineva läbimõõduga ketast, augud keskel, ning kolm varrat, millele kettaid saab laduda. Igal käigul tohib võtta ühe ketta ning tõsta selle mingile teisele vardale, kuid suuremat ketast ei tohi kunagi asetada väiksema peale. Eesmärgiks on laduda "torn" ainult lubatud käikude abil ühelt vardalt teisele (kolmandat varrast abiks võttes).
Osutub, et ülesanne on eksponentsiaalse ajalise keerukusega ketaste arvu suhtes.

Arutluskäik:
Baasjuht: kui ketaste arv on null, siis ei ole tarvis mitte midagi teha.
Samm: kui oskame laduda k-1 ketast vardalt a vardale b, siis k ketta ladumiseks vardalt x vardale z tuleb:
  1. laduda k-1 ketast vardalt x vardale y (võimalik eelduse põhjal)
  2. tõsta suurim ketas (k) vardalt x vardale z "põhjaks"
  3. laduda needsamad k-1 ketast vardalt y vardale z (võimalik eelduse põhjal)
On oluline, et algseis (ja tegelikult ka mistahes järgnev seis) oleks lubatav.
kood
  public static void hanoi (int n, int x, int y, int z) {
      if (n > 0) {
         hanoi (n-1, x, z, y);
         System.out.print (String.valueOf(x) + ">" + String.valueOf(z) + " "); // tõste
	 hanoi (n-1, y, x, z);
      }
  }

Otsimine

Tuvastada etteantud elemendi kuuluvus etteantud struktuuri.
Tulemuseks võib sõltuvalt ülesandest olla: tõeväärtus (kuulub-ei kuulu), "asukoht" struktuuris (või signaal mittekuulumise kohta), element ise vms.
Meie näidetes üritame leida elemendi asukohta.

Lineaarne otsimine

Elementi võrreldakse järjest kõigi struktuuri kuuluvate elementidega. Vajalikud on  iteraator üle struktuuri ja võrdsuse kindlakstegemise predikaat.

Kahendotsimine

"Lõigu poolitamine" matemaatikas. On rakendatav kahel eeltingimusel:
    1. vaadeldav struktuur on järjestatud
    2. elemendid on indekseeritavad
   

   /**
    * Leida etteantud listist etteantud element kahendotsimise abil.
    * @param a list.
    * @param e otsitav element.
    * @returns otsitava elemendi indeks või -1, kui elementi ei leidu.
    */
   
   static public int otsi (List a, Comparable e) {

      int j = -1;
      int l = 0;              // vasakpoolne otspunkt
      int r = a.size() - 1;   // parempoolne otspunkt
      while (l <= r) {
         j = (l + r) / 2;
         if (e.compareTo ((Comparable)a.get (j)) == 0)
            return j;
         if (e.compareTo ((Comparable)a.get (j)) > 0)
            l = j+1; // vasak otspunkt nihkub paremale
         else
            r = j-1; // parem otspunkt nihkub vasakule
      };
      return -1;
   } // otsi lopp



Järjestamine

On antud elementide järjend, eesmärgiks on saada needsamad elemendid mittekahanevas (vahel ka mittekasvavas) järjekorras. Peab olema võimalik elemente võrrelda (kas kahe suvalise elemendi vahel kehtib seos "suurem", "võrdne" või "väiksem"; näit. liides Comparable Javas), samuti on vajalik, et elemente saaks indekseerida (List-liides või massiiv Javas).

Vahel pakub keele API meile järjestamismeetodid ise välja: vt. Arrays, Collections Javas. Sel juhul on otstarbeks neid kasutada - silutud, kiired.

Üldjuhul tuleks siiski osata ka mõnda järjestamismeetodit ise programmeerida.


Pistemeetod:

Jada jagatakse "järjestatud osaks" (algselt tühi) ja "järjestamata osaks" (algselt kogu jada).
Järjestatud osa pikkust suurendatakse järjekordse elemendi paigutamisega õigele kohale järjestatud osas.

     
/**
 * Sorteerime massiivi, mille elemendid realiseerivad
 * liidest Comparable.
 * @param a sorteeritav massiiv.
 */

   static public void pisteSort (Comparable[] a) {
      if (a.length < 2) return;
      for (int i=1; i<a.length; i++) {
         Comparable b = a[i];
         int j;
         for (j=i-1; j>=0; j--) {
            if (a[j].compareTo (b) <= 0) break;
            a[j+1] = a[j]; // vabastame pistekoha
         }
         a[j+1] = b; // pistame b kohale
      }
   } // pisteSort() lopp
.

Kiirmeetod:

(Osa)jada jagatakse kaheks lühemaks osajadaks nii, et ükski element esimeses osas ei oleks suurem ühestki elemendist teises osas. Siis võib kummagi osa sorteerida eraldi (nad on sõltumatud). "Jaga ja valitse". Rekursiivne.
  
   /**
    * Sorteerida massiiv kiirmeetodil.
    * @param massiiv sorteeritav massiiv.
    * @param l vasakpoolne otspunkt.
    * @param r parempoolne otspunkt.
    */

   static public void sort (Comparable[] massiiv, int l, int r) {
      if (massiiv.length < 2) return;
      int i = l; int j = r;
      Comparable x = massiiv [(i+j) / 2];
      do {
         while (massiiv [i].compareTo (x) < 0) i++;
         while (x.compareTo (massiiv [j]) < 0) j--;
         if (i <= j) {
            Comparable tmp = massiiv [i];
            massiiv [i] = massiiv [j]; massiiv [j] = tmp;
            // selle koha peal on väljatrükk silumiseks: "veelahe" ja vahetatavad
            i++; j--;
         }
      } while (i < j);
      if (l < j) sort (massiiv, l, j+1); // rekursioon
      if (i < r-1) sort (massiiv, i, r); // rekursioon
   } // sort() lopp


Tüübikirjelduste ja listidega versioon:

   /**
    * Sort a part of the list using quicksort method.
    * @param array list
    * @param l starting index (included)
    * @param r ending index (excluded)
    */
   static public <T extends Object & Comparable<? super T>>
    void qsort (List<T> array, int l, int r) {
      if (array.size() < 2) return;
      if ((r-l)<2) return;
      int i = l; int j = r-1;
      T x = array.get ((i+j) / 2);
      do {
         while (array.get (i).compareTo (x) < 0) i++;
         while (x.compareTo (array.get (j)) < 0) j--;
         if (i <= j) {
            T tmp = array.get (i);
            array.set (i, array.get (j));
            array.set (j, tmp);
            i++; j--;
         }
      } while (i < j);
      if (l < j) qsort (array, l, j+1); // recursion for left part
      if (i < r-1) qsort (array, i, r); // recursion for right part
   }

   /**
    * Sort a part of the list of comparable elements using insertion sort.
    * @param a list
    * @param l starting position (included)
    * @param r ending position (excluded)
    */
   static public <T extends Object & Comparable<? super T>>
    void insertionSort (List<T> a, int l, int r) {
      if (a.size() < 2) return;
      if ((r-l)<2) return;
      for (int i = l+1; i < r; i++) {
         T b = a.remove (i);
         int j;
         for (j=l; j < i; j++) {
            if (b.compareTo (a.get (j)) < 0) break;
         }
         a.add (j, b); // insert b to position j
      }
    }

Jaanus Pöial