• 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

• Izračunaj vsoto števil od 1 do n

  • Algoritem
  • Koda
  • Izvajanje

• 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));

• 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.

• Zvečer je bila črta še čisto normalna. Lepo gladka je potekala od točke A do točke B.
• A zjutraj se je zbudila s čudnim občutkom. Odtavala je pred ogledalo in groza! Ni bila več lepo gladka. Nad njeno srednjo tretjino se je bohotil mozolj.
• Ampak kakšen – špičast, trikoten z robovi kar take dolžine, kot je bila prej dolžina srednje črte.

• In naslednji dan …
• Proces se ni ustavil!

• In po 4 dneh

Končno ji je njena najboljša prijateljica, krožnica, povedala za čudovito kremo! Če se namaže z njo po vsakem delčku svoje kože, bo rast mozoljev vsaj ustavljena. A krema je draga ... In za vsak cm potrebuje črta vsaj 6g te kreme. Koliko jo mora kupiti, če je bila na začetku dolga d in je preteklo že n dni, kar je dobivala mozolje?

• Črta je po 4 dneh taka, kot bi vzeli 4 take črte med A' in B', kakršne so bile po treh dneh.
• A' in B' pa sta na tretjini razdalje med A in B

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

• Ideja:

  • Matija – M + atija
  • Obrnjeni niz dobimo tako, da M dodamo na konec obrnjenega niza atija!
  • In kako dobimo obrnjeni niz 'atija' – z istim postopkom!
  • Ustavitveni pogoj?

• Ideja 2:

  • Obrnjeni niz dobimo tako, da a dodamo na začetek obrnjenega niza 'Matij'

• Ideja 3:

  • Niz razdelimo na pol, obrnemo vsako polovico in staknemo dobljena niza

• Dano imamo tabelo celih števil. Radi bi sestavili rekurzivno metodo MinMax(stevila), ki vrne dva elementa: minimalni element seznama stevila in maksimalni element seznama stevila.

• Ideja:

  • tabelo razpolovimo
  • poiščemo min/max prvega dela (prvih pol elementov)
  • poiščemo min/max drugega dela (druga polovica elementov)
  • na podlagi min/max obeh delov poiščemo min/max celotne tabele
• Npr.:
• Naj bo tabela {23, 4, 546, 56, 776, 8}
• Poiščemo min/max {23, 4, 546} --- 4 in 546
• Poiščemo min/max {56, 776, 8} --- 8 in 776
• Odgovor za celo tabelo je 4 in 776

• Kako vrniti dva(?) rezultata

• Kako pripraviti "dele tabele"

  • Ali gre brez novih tabel?

• S pomočjo rekurzije preveri, če je niz palindrom.

• Niz je palindrom, če velja:

  • Prvi znak je enak zadnjemu
  • Vsi znaki brez prvega in zadnjega so tudi palindromski niz

• Različica naloge:

  • Dana je tabela celih števil. S pomočjo rekurzije preveri, če je "palindromska". Npr. {1, 31, 31, 1} je palindromska tabela.

• Različica naloge:

  • Dana je tabela nizov. Preveri, če je dvojno palindromskia To pomeni, da je kot tabela palindromska in da so tudi nizi, ki ga sestavljajo, palindromi.

• Različica naloge:

  • Dana je tabelaštevil. Preveri, če je dvojno palindromska. To pomeni, da je kot tabela palindromska in da so tudi števila, ki ga sestavljajo, palindromska. Število je palindomsko, če se z leve bere enako kot z desne.

Na sliki je Kochova snežinka stopnje 4

To lepo snežinko lahko dobimo z naslednjim postopkom.

Stopnja 0 kar enakostranični trikotnik. Nad vsako stranico podobno kot pri Kochovi črti potem srednji del nadomestimo z enakostraničnim trikotnikom.

• Seznam števil lahko uredimo po naslednjem postopku
• Razdelimo ga na pol na dva seznama.
• Oba dobljena seznama uredimo z enakim postopkom (rekurzivna klica).
• Dobljena urejena seznama združimo v novega, prav tako urejenega s postopkom, ki mu rečemo, zlivanje.

• Dan je nek niz. Naredi nov niz, ki vsebuje enake znake kot prvotni niz, le da so urejeni po abecedi.
• Namesto, da urejaš od najmanjšega do največjega, uredi od največjega do najmanjšega (bodisi tabelo, bodisi niz).
• Dan je tabela tabel. Uredi jo tako, da bo tabela urejena glede na dolžino tabel, ki nastopajo v njej.
• Dana je tabela nizov. Uredi to tabelo glede na dolžino nizov.
• Dana je tabela tabel števil. Uredi jo tako, da bo tabela urejena po dolžini tabel, "notranje" tabele pa bodo imele elemente urejene po velikosti.
• Dana je tabela tabel števil. Uredi jo tako, da bo tabela urejena tako,da bodo najprej tiste tabele, ki imajo najmanjše elemente, "notranje" tabele pa bodo imele elemente urejene po velikosti.
• Dana je tabela tabel števil. Uredi jo tako, da bodo "notranje" tabele imele elemente urejene po velikosti, celotna tabela pa bo urejena "leksikografsko". Torej najprej bodo tiste tabele, ki imajo najmanjše elemente, če pa imata dve tabeli enak najmanjši element, primerjamo naslednja dva najmanjša elementa teh dveh tabel, …

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

• Belokranjski vzorci za vezenine stopnje 1, 2, in 3 so naslednji:

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