Izračunaj volumen telesa, preluknjanega n-krat
- Poišči največje in najmanjše število v tabeli števil
- Uredi podatke po velikosti.
- Izračunaj produkt naravnih števil od 1 do n.
CSharp - Rekurzija - skrčeno
CSharp - Rekurzija - skrčeno
Matija Lokar
Problemi
Rekurzija
- Različni problemi
Naloga:
- Sestavi navodila (postopek), s katerim bi problem rešil
Navkljub različnosti:
- Skupni prijem: rekurzija
Rekurzivni postopek:
- Postopek, ki je definiran (določen, opisan) sam s sabo.
Rekurzija
- Rešitev problema – podana s samim problemom, le nad manjšim obsegom podatkov
- V opisu postopka rešitve uporabimo kar ta postopek
- Če želimo priti do rešitve, ne moremo nadaljevati v nedogled kot npr. pri pesmici
ustavitveni pogoj:
- Kdaj v postopku ne uporabimo istega postopka
- Običajno: ko je problem "majhen" (enostaven)
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
- S klicem istega algoritma (rekurzija) pridobi rešitve vseh podproblemov
- Združi rešitve podproblemov v enotno rešitev
Faktoriela
- Rekurzivna definicija:
- bomo izračunali, če bomo poznali
3! = 3 * 2!
- 2! = 2 * 1! =
- 1! = 1 * 0! =
- 0! = 0 * (-1)! = ???
- 1! = 1
Faktoriela - postopek
Faktoriela(n):
Če je n = 0, je rezultat 1
sicer pa
pom = Faktoriela(n-1)
rezultat = n * pom
Če je n = 0, je rezultat 1
sicer pa
pom = Faktoriela(n-1)
rezultat = n * pom
Faktoriela
public static int Faktoriela(int n) {
if (n == 1) return 1;
else {
int pom = Faktoriela(n-1);
return n * pom;
}
}
System.Console.WriteLine("4! = " + Faktoriela(4));
if (n == 1) return 1;
else {
int pom = Faktoriela(n-1);
return n * pom;
}
}
System.Console.WriteLine("4! = " + Faktoriela(4));
Faktoriela
|
klasično
- 15 množenj
- Ideja
- 4 množenja
- Kaj pa, če npr.14
- ......... 5 množenj
if (n == 1) return y;
else {
pom = Pot(y, n / 2);
if (n % 2 == 0){
return pom * pom;
}
else {
return y * pom * pom;
}
}
else {
pom = Pot(y, n / 2);
if (n % 2 == 0){
return pom * pom;
}
else {
return y * pom * pom;
}
}
Hanoiski stolpiči
Problem Hanoiskih stolpičev:
| |
|
Hanoiski stolpiči
Hanoiski stolpiči - ideja
|
Problem iste vrste, a manjši
Hanoiski stolpiči - ideja
- Daj obroč z A na C
- Prestavi n –1 obročev z B na C (s pomočjo A)
- Problem iste vrste, a manjši
Hanoiski stolpiči
Preloži n obročev z A na C s pomočjo B
- Preloži n-1 obročev z A na B s pomočjo C
- Daj obroč z A na C
- Preloži n-1 obročev z B na C s pomočjo A
- ustavi ?
Hanoiski stolpiči
Preloži n obročev z A na C s pomočjo B
- Če je n = 1 potem daj obroč z A na C
sicer pa
- Preloži n-1 obročev z A na B s pomočjo C
- Daj obroč z A na C
- Preloži n-1 obročev z B na C s pomočjo A
Hanoiski stolpiči
public static void Hanoi(int n, char st1, char st2,char st3) {
if (n == 1) {
System.Console.WriteLine("Prelozi z " + st1 + " na " + st3);
}
else {
Hanoi(n-1, st1, st3, st2);
System. Console.WriteLine("Prelozi z " + st1 + " na " + st3);
Hanoi(n-1, st2, st1, st3);
}
}
if (n == 1) {
System.Console.WriteLine("Prelozi z " + st1 + " na " + st3);
}
else {
Hanoi(n-1, st1, st3, st2);
System. Console.WriteLine("Prelozi z " + st1 + " na " + st3);
Hanoi(n-1, st2, st1, st3);
}
}
