A Fun Holidays – Fun, Wacky & Trivial Holidays weboldal sokféle különleges ünnepnapot listáz. Ezek leírása többnyire vicces, emlékezős, de néhány igazán érdekes, régi-régi hagyományt elevenít fel.
Ma van (november 23.) a Fibonacci nap. Fibonacci középkori matematikus volt, ő tette közismertté a Fibonacci-sorozat-ot. A (0), 1, 1, 2, 3, 5, 8, 13, 21, 34, … sorozat igen népszerű azok közében is, akik programozást tanulnak. A sorozat első két eleme 1 és 1 (ha szükséges, akkor nulladik elemmel is dolgozhatunk), és minden további elem az előző két elem összege. Többféle történet is fűződik ehhez, talán az egyik legismertebb a nyúlpárok szaporodásához kötődik.
Honnan származik a Fibonacci nap? A mai nap hh.nn. formátumban 11.23. , és a számjegyek részei a Fibonacci-sorozatnak. Mindössze ennyi, ilyen egyszerű. 😉
A sorozat elemei könnyen előállíthatók néhány változó használatával, ha a kezdő programozó már ismeri a ciklust, mint algoritmikus építőelem – ez az iteratív megoldás. A rekurzív megoldás tipikus rossz megoldásként ismert, lássuk ennek Java megvalósítását:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
public class FibTeszt { final static int N=5; static int fib(int n) { for(int i=1; i<=N-n; i++) System.out.print("-"); System.out.println("fib("+n+")"); if(n<2) return n; return fib(n-1)+fib(n-2); } public static void main(String[] args) { System.out.println(fib(N)); } } |
Ha kiadnám a fenti Java forráskódot papíron ezt egy dolgozatban, zárthelyin, állásinterjú szakmai részén azzal a kérdéssel, hogy mit ír ki a program a képernyőre, akkor bizony sokan bajban lennének. Meg is történt ez már sokszor, tapasztalatból írom. A rekurzió első leszálló ágáig szinte mindenki eljut, de az ott induló első felszálló ágat követően sokan belezavarodnak a részlépések egymásutániságába. A végeredményt szinte mindenki tudja, de itt most arra helyezzük a hangsúlyt, hogy hogyan jutunk el odáig. Persze n=5-re fib(5)=5. Alig fordult még elő, hogy valaki hibátlanul leírta volna az alábbi eredményt:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
fib(5) -fib(4) --fib(3) ---fib(2) ----fib(1) -----fib(0) ----fib(1) ---fib(2) ----fib(1) -----fib(0) --fib(3) ---fib(2) ----fib(1) -----fib(0) ----fib(1) 5 |
A megoldás során – emlékeztetek arra, hogy ez atipikus megközelítés – sok-sok redundáns lépés történik. Hiszen például a fib(3)-at tudni kell a fib(4)-hez és a fib(5)-höz is, hiszen fib(4)=fib(2)+fib(3) és fib(5)=fib(3)+fib(4), valamint ebben az implementációban nincs semmilyen emlékezet (puffer, adatszerkezet), amivel a sok feleslegesnek vélhető számítást elkerülhetnénk.
Nyert ügye lehet annak, aki „fejben összerakja” az alábbi fát – akár dinamikusan, menet közben hozzáadva és törölve elemeket – és ebben navigálva (ezt bejárva) válaszolja meg a kérdést:
Az alábbi animáció segíthet a megértésben: 45 lépésben mutatja be az aktuális részlépést/részfeladatot (leszálló ág) és/vagy az aktuális részeredményt (felszálló ág):
A Fibonacci-sorozat többféleképpen kapcsolódik a természethez, természeti jelenséghez, növényekhez, állatokhoz (virágszirmok száma, levelek elfordulása, napraforgók magjai, fenyőtoboz pikkelyei, nautilus háza, aranymetszés, zenei hangolás, zeneművek tagolása), felhasználható algoritmusok futási idejének becsléséhez, fa adatszerkezetek építéséhez is. Az aranymetszésről megoszlanak a vélemények: vannak akik szinte mindenben ezt látják (művészet: festészet, szobrászat), mások módszeresen cáfolják ezt (például Falus Róbert: Az aranymetszés legendája, Magyar Könyvklub, 2001, második, javított kiadás, ISBN 963-547-332-X).
A bejegyzéshez tartozó teljes forráskódot ILIAS e-learning tananyagban tesszük elérhetővé tanfolyamaink résztvevői számára.
A feladat a Java SE szoftverfejlesztő tanfolyam szakmai moduljának 9-12. óra: Metódusok, rekurzió alkalmához kötődik.
Nekem tetszettek és megosztom:
Fibonacci Sequence (a sorozat és az aranymetszés kapcsolata):
https://www.mathsisfun.com/numbers/fibonacci-sequence.html
The AMAZING Fibonacci Spiral/Sequence – Extended Version! (látványos videó):
https://www.youtube.com/watch?v=Y1VL1g2Gg6o
Fibonacci Sequence—A Handy Mathematical Approach For Looking At Evolution! (innovatív foglalkozásokhoz ötletek):
https://www.sciencefriday.com/educational-resources/fibonacci-sequence-handy-mathematical-approach-looking-evolution/
Identities involving Fibonacci Series (sok-sok gondolkodtató feladattal):
https://brilliant.org/wiki/fibonacci-series/
Köszönöm Péter. Hasznos ötleteket adtál egy következő Fibonacci naphoz. 😉
Péter: készíthetnénk egy GUI-s animációs programot a 2020-as Fibonacci naphoz kötődően. Például a Fibonacci-spirál lépésenként/fázisonként GUI-n megvalósítva. Van kedved?
Sanyi: OK. Találjuk ki, hogy asztali swing legyen, vagy böngészőben fusson. Beleépíthetnénk valamilyen távirányítóhoz hasonló vezérlést a fázisok közötti váltáshoz: Első, Előző, Következő, Utolsó. Augusztus első szombatján ráérek.
Péter: rendben.
Nagy küzdelem ez a rekurzió. Hogy lehet ezt könnyen megérteni?
Endre: ezt nem tudom megválaszolni egy hozzászólásban. Ez egy összetett kérdés/probléma. A programozás tanításának egy nagy kihívása. Kapcsolódik a matematikában a teljes indukcióhoz. A kontakt óráinkon mutatunk sok-sok mintapéldát, összehasonlítjuk néhány alapfeladat, programozási tétel ciklussal való megoldását (iteratív) a ciklus nélküli megoldással (rekurzív). Megnézünk néhány tipikus és atipikus rekurzív megoldást. Lépésenként futtatunk forráskódot és közben figyeljük: melyik változóval mi történik, hol jár a végrehajtás. A rekurzió – mint elv, algoritmus, gondolatmenet – nem csupán az utasítás végrehajtás kódolása során van a fejlesztők fejében, hanem adatszerkezetek felépítésénél, feldolgozásánál (például: fa és bejárása) is.
Hasznos volt, hogy átbeszéltük szombaton. El is készültem vele. Időzítettem a blog bejegyzést az idei Fibonacci napra, azaz 2020.11.23-ra.
Ma megjelent Péter blog bejegyzése: Fibonacci-spirál
Ma Balázs is blogolt a Fibonacci-sorozatról, hiszen ma újra Fibonacci nap van. Az atipikus rekurzív megközelítés szép alternatíváját adja a Binet-formula, amihez nem kell sorozat (és hozzá adatszerkezet/tárhely) és nem kell ismerni az n-edik elem kiszámításához az előző két elemet sem. Íme: https://it-tanfolyam.hu/fibonacci-sorozat/