Rekurzija I

Rekurzija I

Avtor: Matija Lokar

Več o projektu...

Rekurzija

  • Različni problemi

  • Naloga:

    • Sestavi navodila (postopek), s katerim bi problem rešil

  • Splošni algoritem:

    • Če je problem majhen, vrni rešitev

    • Sicer pa

      • Razdeli problem na manjše podprobleme iste vrste, kot je prvotni problem
      • Z klicem istega algoritma (rekurzija) pridobi rešitve vseh podproblemov
      • Združi rešitve podproblemov v enotno rešitev

Zgledi

  • Izračunaj vsoto števil od 1 do n

    • Algoritem
    • Koda
    • Izvajanje

  • Hanoiski stolpiči

    • Algoritem
    • Koda
    • Izvajanje

Kaj je kaj

  • Oglej si naslednji rekurzivni program:
    public static int Puzzle(int base, int limit) {
    //base in limit sta nenegativni števili
      if ( base > limit ) {
        return -1;
      } else {
        if ( base == limit ) {
          return 1;
        } else {
          return base * Puzzle(base + 1, limit);
        }  } }
  • kateri del metode Puzzle je ustavitveni pogoj?
  • kje se izvede rekurzivni klic?

  • kaj izpišejo sledeči stavki:

    • Console.WriteLine(Puzzle(14,10));
    • Console.WriteLine(Puzzle(4,7));
    • Console.WriteLine(Puzzle(0,0));

Osnove rekurzije

  • Dana je rekurzivna metoda. Preberi jo in ugotovi, kaj dela. Šele potem!! jo prenesi v testni program in zaženi ter preveri, da res dela tisto, kar si si predstavljal.
  • public static string KajDelam(int stevec) {
      if(stevec <= 0) {
         return "";
      } else {
         return "" + stevec + ", " +
              KajDelam(stevec - 1);
      }
    }
  • Metodo nato prepiši tako, da bo vrnila niz s števili v obratnem vrstnem redu kot prvotna.

Obrni niz

  • Napiši metodo, ki s pomočjo rekurzije vrne obrnjeni niz.

Kochova snežinka - ploščina

  • Na sliki je Kochova snežinka stopnje 4
(6a.png)
  • To lepo snežinko lahko dobimo z naslednjim postopkom.
(6b.png)
  • Stopnja 0 le kar enakostranični trikotnik. Nad vsako stranico podobno kot pri Kochovi črti potem srednji del nadomestimo z enakostraničnim trikotnikom.

Ploščina Kochove snežinke

  • Sestavi metodo, ki izračuna ploščino Kochove snežinke stopnje n in začetno stranico d.

Belokranjski vzorci I

  • Belokranjski vzorci za vezenine stopnje 1, 2, in 3 so naslednji:
(8.png)
  • Npr. vzorec stopnje 3 dobimo tako, da poln kvadrat s stranico a razdelimo na 9 enakih kvadratov. Izrežemo 4 stranske srednje kvadrate. Nato postopek 2x ponovimo na preostalih 5 kvadratih.
  • Sestavite metodo, ki izračuna, kolikšna je dolžina niti, ki jo potrebujemo za izdelavo vzorca stopnje n, če za najmanjše vbode porabimo 3mm niti (za vzorec stopnje 1 torej porabimo 5 x 4 × 3mm = 60mm).
0%
0%