Pritisnite F11

Iz varnostnih razlogov je mogoče celozaslonski način vključiti samo s pritiskom na gumb F11 na tipkovnici.

Ko ste enkrat v celozaslonskem načinu, ga izključite spet s pritiskom na F11.

Rekurzija C# - naloge in kviz

Avtor: Mateja Gorišek, pred. M.Lokar, prenos v NAUK Alja Gligić

Hvala za ogled gradiva!

Veseli bomo vaših komentarjev. Obiščite nas na www.nauk.si.

Naloga 1 - zaporedje

Dano je zaporedje . Z uporabo rekurzije napiši program, ki vrne n-ti element zaporedja! Poleg tega napiši program, ki izpiše elemente od nekega začetnega elementa do nekega končnega elementa.

Splošni n-ti element dobimo iz , torej potrebujemo prejšnji element. Zaporedje se začne s prvim členom, ki je enak 2. Manših členov od tega člena nimamo, zato bomo prvi člen uporabili za ustavitveni pogoj.
Če iščemo naprimer 5-ti element zaporedja, ga bomo izračunali rekurzivno nekako takole:

Iščemo 5-ti element zaporedja. Da bomo izračunali peti element,rabimo izračunati 4-ti element zaporedja. Tako iščemo 4-ti element, kjer ponovno uporabimo rekurzijo za iskanje vseh nadaljih elementov. Postopek izvajamo dokler ne naletimo na ustavitveni pogoj, ki poskrbi, da se ustavimo. Ko se ustavimo se postopno vračamo in računamo vrednosti zaporedja. Ko pridemo na 5-ti element, dobimo rešitev prvotnega problema, ki je enak 242.

Za izpis zaporedja od nekega začetnega elemeta do nekega končnega elementa bomo prav tako rešili rekurzivo. V tem programu bomo najprej izpisali začeni element, nato pa začetni element povečevali, dokler ne bo začetni element enak končnemu.
Sedaj lahko napišem obe metodi: Rešitev problema v C#

Naloga 1 - koda v C#

public static int zaporedje(int n)
        { // metoda mi vrne n-ti člen zaporedja
            if (n == 1) return 2; // ustavitveni pogoj
            else
            {
                return (3 * zaporedje(n - 1) + 2); // rekurzivni klic
            }
        }

        public static void izpisi(int zacetek, int konec)
        { // metoda mi izpiše elemente zaproedja od začetnega do končnega elementa
            if (zacetek <= konec)
            {
                Console.Write(zaporedje(zacetek) + " ");
                izpisi(zacetek + 1, konec); // rekurzivni klic
            }
        }
        static void Main(string[] args)
        {
            Console.Write("Vnesi začetni element zaporedja: "); // vnos uporabnika
            int zacetek = int.Parse(Console.ReadLine());
            Console.Write("Vnesi končni element zaporedja: ");
            int konec = int.Parse(Console.ReadLine());

            if (zacetek <= konec && zacetek > 0 && konec > 0)
            {
                izpisi(zacetek, konec);
            }
            else Console.WriteLine("Napačen vnos!");
            Console.ReadLine();
        }

Naloga 1 - predstavitev s filmčkom

Naloga 2 - fakulteta

Sestavi rekurzivno metodofakulteta, ki izračuna fakulteto naravnih celih števil.

Fakulteta naravnega števila n je v matematiki funkcija, ki določa zmnožek pozitivnih celih števil manjših ali enakih n. Uporabna je še posebaj v kombinatoriki. Funkcijo zapišemo kot n! in preberemo n fakulteta. Fakulteti drugače pravimo tudi faktoriela.
V matematiki jo običajno izračunamo z rekurzivno definicijo: .
Torej n! lahko izračunamo, če poznamo (n-1)!. Vendar nekje se mora funkcija končati, zato rabimo ustavitveni pogoj. Ta je določen z 1! = 1.
Torej, če želimo izračunati fakulteto števila 5 oziroma 5! jo izračunamo nekako takole:

Torej za izračun 5! zahtevamo izračun 4!. Za 4! zahtevamo izračun 3! itd., dokler ne pridemo do ustavitvenega pogoja. Ko pridemo do ustavitvenega pogoja, se lahko vračamo nazaj in izračunamo najprej 2!= 2 * 1 = 2, naprej lahko izračunamo 3!, kar je 3 * 2 = 6. In tako vse do 5!, ki se izračuna kot 5 * 24 = 120.

Sedaj lahko ta problem zapišemo v programskem jeziku C#. Za zapis rekurzivne metode fakulteta najprej rabimo ustavitveni pogoj, ta je 1! = 1. Za rekurzivni klic pa bomo uporabili rekurzivno definicijo: .
Metoda v C#: Metoda v C#

Naloga 2 - koda v C#

public static int fakulteta(int n)
        { // metoda rekurzivno izračuna fakulteto naravnega števila
            if (n == 1) return 1; // ustavitveni pogoj
            else
            {
                return n * fakulteta(n - 1); // rekurzivni klic
            }
        }
        static void Main(string[] args)
        { // klic rekurzivne metode fakulteta
            Console.Write("Vnesi število: ");
            int n = int.Parse(Console.ReadLine()); // s int.Parse niz spremenimo v število
            Console.WriteLine(n + "! = " + fakulteta(n));
            Console.ReadLine();
        }

Naloga 3 - ploščina trikotnika Sierpinskega

Napiši rekurzivno metodo, ki izračuna ploščino trikotnika Sierpinskega dane stopnje. Osnovni trikotnik je kar poln enakokraki trikotnik. Trikotnik stopnje 1 dobimo tako, da iz osnovnega trikotnika odstranimo trikotnik, katerega oglišča so razpolovišče stranic osnovnega trikotnika. Na tak način dobimo 3 manjše polne trikotnike. Trikotnik 2. stopnje dobimo tako, da iz trikotnika 1. stopnje odstranimo trikotnike iz treh polnih trikotnikov na enak način, kot smo jih odstranili iz osnovnega trikotnika:

Namig:
Namesto, da odstranjujemo trikotnike, raje ugotovimo, da je ploščina trikotnika stopnje n s stranico d, ravno 3-kratnik ploščine trikotnika stopnje n-1, vendar s pol manjšo stranico.

Naloga 4 - vsota števil v tabeli

Napiši rekurzivno metodo za seštevanje celih števil v tabeli, ki bo vrnila vsoto števil.

Namig:
Problema se lotimo tako, da najprej rekurzivno seštejemo števila od začetka do indeksa i-1. Ta vrne vsoto do tega indeksa, nato pa tej vsoti prištejemo vrednost na polju z indeksom i, ter vrnemo skupno vsoto.

Naloga 5 - potenca

Žeimo izračunati , kjer je x neko decimalno število in n neko naravno število.
Definicija potence je (n krat).

Namig:
Premislimo lahko, da lahko vsako potenco razbijemo na dva dela. Na primer: lako razbijemo na . Torej, če poznamo , lahko do pridemo le z enim množenjem. Enako lahko nadaljujemo z itd.. Ta postopek deluje le če imamo sodi eksponent. Če pa imamo lihi eksponent naredimo le en vmesni korak: . Torej, če želimo iračunati , ga izračunamo nekako takole:

Naloga 6 - palindrom

Imamo podani niz. Za podani niz preveri ali je ta niz palindrom.

Namig:
NIz je palindrom, če se bere iz obeh strani enako.
Za ustatveni pogoj podaj prazen niz ali pa niz z enim znakom, saj je ta že palindrom. Pogleg tega je tudi niz palindrom, če se ujemata prvi in zadnji znak in je tudi srednji del niza palindrom.
Primer niza, ki je palindrom: klovn in volk.

Naloga 7 - pločevinke

Zamisli si, da pobiraš pločevinke in jih zlagaš v vrste po naslednjem pravilu:

v prvi vrsti je ena pločevinka, v drugi sta dve, v tretji sta tri itd. V vsaki novi vrsti je ena pločevinka več kot v prejšnji.
Napiši program, ki bo rekurzivno izračunal skupno število pločevink za izbrano število vrst.

Namig:
Skupno število pločevink lahko izračunamo, če poznamo zaporedno številko vrste (potem vemo, da smo dodali prav toliko pločevink) in vsoto pločevink od prej. Zapisano v matematičnem jeziku: .

Rekurzija - kviz

Dopolnite stavek s pravilno izbiro:

Rekurzija pomeni podajanje metode na tak način, da se v definiciji sklicujemo na

drugo metodo

isto metodo