Fibonacci nap 2018

Fibonacci nap 2018A 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 a nulladik eleme 0), é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:

Fibonacci-nap-2018-FibTeszt

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:

Fibonacci-sorozat-n=5

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):

Fibonacci-sorozat-n=5

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ó alkalomhoz kötődik.

Az animált gif a gifmaker.me weboldalon készült.

Fát építünk

Fát építünkAz adatok strukturális és könnyen értelmezhető formában való megjelenítése egy szoftver felhasználói felületén átgondolt tervezést igényel. Az adatokhoz hozzá kell jutni, ki kell választani a megfelelő grafikus komponenst, a mögötte lévő adatmodellt, össze kell ezeket kötni. Gyakran előforduló feladat, hogy táblázatosan is ábrázolható adatokból – felhasználva az adatok közötti összefüggéseket és kapcsolatokat – csoportosítva jelenítsünk meg hierarchikusan, fa struktúrában, kinyitható-becsukható formában, ahogyan ezt a felhasználók jól ismerik a fájl- és menürendszereket használva.

Fát építünk kétféleképpen

Adatbázisból, az Oracle HR sémából lekérdezünk két összetartozó nevet: részleg és alkalmazott. A lekérdezés során figyelünk a megfelelő sorrendre, ami a későbbi feldolgozást megkönnyíti. Adatainkat részlegnév szerint növekvő, azon belül alkalmazott neve szerint is növekvő – ábécé szerinti – sorrendbe rendezzük. A vezérlő rétegben két függvényt írunk, amely a modell rétegtől jut hozzá az adatokat tartalmazó generikus listához – átvett paraméterként –, és a visszaadott érték a nézet réteghez kerül.

A csoportváltás algoritmust használjuk, amely 5 blokkból épül fel. A külső ciklus előtti 1. blokk és utáni 5. blokk egyszer hajtódik végre, az előkészítő és lezáró tevékenységek tartoznak ide. A külső ciklus elején és végén található 2. és 4. blokk a belső cikluson kívül fut le, csoportonként, kategóriánként, részlegenként egyszer (most összesen 11-szer mindkettő). A 3. blokk a belső cikluson belül található, és alkalmazottanként egyszer hajtódik végre (most összesen 106-szor).

Háromszintű fát építünk: a gyökérbe (0. szint) fix, beégetett szövegként kerül a cég neve és a teljes létszám. Az 1. szinten jelennek meg a részlegek nevei és a hozzájuk tartozó létszámok. A 2. szint az alkalmazottak neveiből áll.

1. megoldás

A megoldás faKeszit1() függvénye szöveges adatot eredményez. Ez jól használható teszteléshez: megvan-e az összes adat, megfelelő-e a részlegek sorrendje azon belül az alkalmazottak sorrendje, működik-e a csoportosítás, rendben van-e a megszámolás?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public String faKeszit1(ArrayList<Alkalmazott> lista) {
  //1
  StringBuilder faGyoker=new StringBuilder("Cég ("+lista.size()+" fő)");
  int i=0;
  while(i<lista.size()) {
    //2
    String aktReszleg=lista.get(i).getReszleg();
    ArrayList<String> faReszlegAlkalmazott=new ArrayList<>();
    while(i<lista.size() && lista.get(i).getReszleg().equals(aktReszleg)) {
      //3
      faReszlegAlkalmazott.add(lista.get(i).getNev());
      i++;
    }
    //4
    String faReszleg="\n "+aktReszleg+" ("+faReszlegAlkalmazott.size()+
      " fő)\n ";
    faGyoker.append(faReszleg+" "+String.join("\n  ",faReszlegAlkalmazott));
  }
  //5
  return faGyoker.toString();
}

 
A faKeszit1() függvény egy sok lépésben összefűzött (konkatenált) szöveget ad vissza. Az 1. blokkban előkészítjük a fa gyökerét, ami StringBuilder típusú, hiszen sokszor manipuláljuk és inicializáljuk a lista indexelésére használt i ciklusváltozót. A 2. blokkban megjegyezzük az aktuális részleget és előkészítjük az ehhez tartozó alkalmazottak nevét tároló generikus listát (faReszlegAlkalmazott). Az aktReszleg-hez tartozó alkalmazottak neveit összegyűjtjük a 3. blokkban. Egy részleg feldolgozását a 4. blokkban fejezzük be a fa aktuális 1. és 2. szinten lévő elemeinek szövegbe való beszúrásával. A belső ciklushoz kötődően megszámolást nem kell alkalmaznunk, hiszen az adott részlegben dolgozó alkalmazottak száma a generikus listától elkérhető (size()). Építünk arra, hogy a külső ciklusból nézve az egymás után végrehajtódó 2. és 4. blokkban az aktReszleg nem változik meg. A 2. blokkban még nem tudjuk a fa aktuális 1. szintjét hozzáfűzni a szöveghez, hiszen a létszám csak a belső ciklusban felépülő kollekciótól kérhető el utólag. Szükséges némi késleltetés, hiszen a szöveg összefűzése és lényegesen egyszerűbb (mint utólag manipulálni megfelelő helyeken). Az 5. blokkban a csoportváltás algoritmushoz kötődő tevékenységünk nincs.

Az 1. megoldás eredménye

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
Cég (106 fő)
 Accounting (2 fő)
  Shelley Higgins
  William Gietz
 Administration (1 fő)
  Jennifer Whalen
 Executive (3 fő)
  Lex De Haan
  Neena Kochhar
  Steven King
 Finance (6 fő)
  Daniel Faviet
  Ismael Sciarra
  John Chen
  Jose Manuel Urman
  Luis Popp
  Nancy Greenberg
 Human Resources (1 fő)
  Susan Mavris
 IT (5 fő)
  Alexander Hunold
  Bruce Ernst
  David Austin
  Diana Lorentz
  Valli Pataballa
 Marketing (2 fő)
  Michael Hartstein
  Pat Fay
 Public Relations (1 fő)
  Hermann Baer
 Purchasing (6 fő)
  Alexander Khoo
  Den Raphaely
  Guy Himuro
  Karen Colmenares
  Shelli Baida
  Sigal Tobias
 Sales (34 fő)
  Alberto Errazuriz
  Allan McEwen
  Alyssa Hutton
  Amit Banda
  Charles Johnson
  Christopher Olsen
  Clara Vishney
  Danielle Greene
  David Bernstein
  David Lee
  Eleni Zlotkey
  Elizabeth Bates
  Ellen Abel
  Gerald Cambrault
  Harrison Bloom
  Jack Livingston
  Janette King
  John Russell
  Jonathon Taylor
  Karen Partners
  Lindsey Smith
  Lisa Ozer
  Louise Doran
  Mattea Marvins
  Nanette Cambrault
  Oliver Tuvault
  Patrick Sully
  Peter Hall
  Peter Tucker
  Sarath Sewall
  Sundar Ande
  Sundita Kumar
  Tayler Fox
  William Smith
 Shipping (45 fő)
  Adam Fripp
  Alana Walsh
  Alexis Bull
  Anthony Cabrio
  Britney Everett
  Curtis Davies
  Donald OConnell
  Douglas Grant
  Girard Geoni
  Hazel Philtanker
  Irene Mikkilineni
  James Landry
  James Marlow
  Jason Mallin
  Jean Fleaur
  Jennifer Dilly
  John Seo
  Joshua Patel
  Julia Dellinger
  Julia Nayer
  Kelly Chung
  Kevin Feeney
  Kevin Mourgos
  Ki Gee
  Laura Bissot
  Martha Sullivan
  Matthew Weiss
  Michael Rogers
  Mozhe Atkinson
  Nandita Sarchand
  Payam Kaufling
  Peter Vargas
  Randall Matos
  Randall Perkins
  Renske Ladwig
  Samuel McCain
  Sarah Bell
  Shanta Vollman
  Stephen Stiles
  Steven Markle
  Timothy Gates
  TJ Olson
  Trenna Rajs
  Vance Jones
  Winston Taylor

2. megoldás

A faKeszit2() függvénynél alkalmazkodunk ahhoz, hogy a JTree vizuális komponenshez DefaultTreeModel observable típusú modell szükséges, így ezzel térünk vissza (faModell). A fa csomópontjai DefaultMutableTreeNode osztályú objektumok lesznek, amelyeknek a userObject tulajdonsága szükség esetén manipulálható. Az 1 blokkban beszúrjuk a fa gyökerét (faGyoker), amihez a későbbiekben csatlakozik a fa többi eleme. A 2. blokkban megjegyezzük az aktuális részleget és előkészítjük – megjelenítendő szöveg nélkül – a faReszleg csomópontot. A 3. blokkban fabeli csomópontként a fa 1. szintjén megjelenő részleghez névtelenül hozzáadjuk a fa 2. szintjére kerülő – aktuális részleghez tartozó – alkalmazottak nevét. A 4. blokkban utólag módosítjuk a faReszleg csomópont megjelenítendő szövegét. Az aktuális részleg létszámát itt sem kell külön megszámolni, mert a faReszleg-től elkérhető (getChildCount()). Az 5. blokkban itt sincs különösebb teendőnk. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public DefaultTreeModel faKeszit2(ArrayList<Alkalmazott> lista) {
  //1
  DefaultMutableTreeNode faGyoker=
    new DefaultMutableTreeNode("Cég ("+lista.size()+" fő)");
  DefaultTreeModel faModell=new DefaultTreeModel(faGyoker);
  int i=0;
  while(i<lista.size()) {
    //2
    String aktReszleg=lista.get(i).getReszleg();
    DefaultMutableTreeNode faReszleg=new DefaultMutableTreeNode();
    while(i<lista.size() && lista.get(i).getReszleg().equals(aktReszleg)) {
      //3
      faReszleg.add(new DefaultMutableTreeNode(lista.get(i).getNev()));
      i++;
    }
    //4
    faReszleg.setUserObject(
      aktReszleg+" ("+faReszleg.getChildCount()+" fő)");
    faGyoker.add(faReszleg);
  }
  //5
  return faModell;
}

A 2. megoldás eredménye

Fát építünk, képernyőkép

A bejegyzéshez tartozó teljes forráskódot ILIAS e-learning tananyagban tesszük elérhetővé tanfolyamaink résztvevői számára.

Attól függően, hogyan jutunk hozzá a megjelenítéshez szükséges adatokhoz, több tanfolyamunkhoz is kapcsolódik a feladat és a modell rétegben mindig másképpen tervezünk és implementálunk:

  • A Java SE szoftverfejlesztő tanfolyam 45-48. óra: Adatbázis-kezelés JDBC alapon, 1. rész alkalmán hagyományos SQL lekérdező utasítást készítünk JDBC környezetben.
  • A Java EE szoftverfejlesztő tanfolyam 25-32. óra: Adatbázis-kezelés JPA alapon alkalommal a perzisztencia szolgáltatásait vetjük be.
  • A Java adatbázis-kezelő tanfolyam 13-16. óra: Konzolos kliensalkalmazás fejlesztése JDBC alapon, 1. rész, 33-36. óra: Grafikus kliensalkalmazás fejlesztése JDBC alapon, 2. rész alkalmain hierarchikus lekérdezéseket használunk.

Doktoranduszok programoznak

it-tanfolyam.hu adatok elemzéseSaját doktorandusz csoporttársaimmal többször beszélgettünk már arról, hogyan tudnák/tudják használni a programozás eszköztárát, módszereit, lehetőségeit saját kutatási munkájukban, beépítve a kutatási folyamat egyes lépéseibe, illetve disszertációjuk elkészítésébe.

Mivel a 10 fős csoportban mindenkinek más az alapvégzettsége, így szoftverfejlesztéshez, programozáshoz közös szókincs és terminológia haladó szinten természetesen nincs, viszont közös bennünk, hogy mindannyian alkotunk különféle modelleket és elemzünk adatokat.

Például:

  • a mérnökök, fizikusok, geográfusok, biológusok többféle kísérletet végeznek el, szimulációkat terveznek és futtatnak, mérőeszközöket és műszereket használnak,
  • az informatikusok különböző matematikai eszközöket alkalmazva objektumorientált – vagy másféle – modellezést végeznek, szoftvereket terveznek, javítanak, újraírnak.

Adatokat is elemzünk, ki-ki előképzettségének megfelelően:

  • kérdőívező szoftverekből exportálva valamit,
  • Excel munkalapokon, függvényekkel, adatbázis-kezelő funkciókkal, kimutatásokkal (Pivot táblák),
  • különböző fájlformátumokkal (CSV, XML, JSON, egyedi) dolgozunk és konvertálunk A-ból B-be,
  • távoli adatbázisokhoz, felhőbeli adattárházakhoz csatlakozunk, lekérdezünk és kapunk valamilyen – többnyire szabványos – adathalmazt,
  • matematikai, statisztikai szoftvereket használunk, például: MATLAB, Derive, Maple, SPSS.

Önszerveződően összeállítottunk egy olyan két részből álló tematikát, ami mindannyiunk számára hasznos. A 64 óra két 32 órás modulból áll: Java programozás és SPSS programrendszer.

Java programozás modul

  • 1-8. óra: Objektumorientált modellezés, MVC rétegek, algoritmus- és eseményvezérelt programozás
  • 9-16. óra: Fájlkezelés és szövegfeldolgozás (XLS, CSV, XML, JSON formátumú adatok írása, olvasása, feldolgozása)
  • 17-24. óra: Adatbázis-kezelés JDBC alapon (SQL parancsok, CRUD műveletek, hierarchikus lekérdezések)
  • 25-32. óra: Komplex adatfeldolgozási feladatok megoldása programozási tételek használatával

SPSS programrendszer modul

  • 1-8. óra: Bevezetés az SPSS-be, interakciós eszközök, adatmátrix, menük: Transform, Analyze, szkriptek futtatása
  • 9-16. óra: Alapstatisztikák kérése, kereszttáblázatok készítése, hipotéziselmélethez kötődő funkciók, normalitásvizsgálat, minták összehasonlítása t-próbával
  • 17-24. óra: Regresszió-analízis: lineáris, nemlineáris, többváltozós; Idősorok elemzése: szűrés, periodogram, trendelemzés
  • 25-32. óra: Mesterséges neuronhálózatok: matematikai modell és működése

Mivel mindenki doktorandusz a csoportban, így a különböző MSc-s alapvégzettsége ellenére mindannyiunknak vannak strukturális programozáshoz kötődő alapismeretei, valamint adatok elemzéséhez szükséges elméleti matematikai/statisztikai alapjai. Az én részem a 32 órás Java programozás modul, ami 2018.10.28-tól 2018.12.09-ig tart hétvégi napokon. Ez nagyban lefedi a Java SE szoftverfejlesztő tanfolyamunk tematikáját. A koncepciót once-in-a-lifetime jelleggel dolgoztuk ki azzal a fő szándékkal, hogy hatékonyabban működjünk együtt a jövőben.

Koch-görbét rajzolunk

A Koch-görbe egyike a legrégebben ismert egyszerű fraktáloknak. Mint ilyen, önhasonlóan rekurzív. Az önhasonlóság azt jelenti, hogy az ábra tetszőleges részét felnagyítva mindig hasonló/ugyanolyan részek jelennek meg (a méretaránytól függetlenül). Az n=1 szinten a Koch-görbe kiindulópontja egy szabályos háromszög. A n+1-edik szinten az n-edik szinten található szakaszokat harmadoljuk, és a középső szakasz helyére egy harmad akkora háromszög két szárát illesztjük (az alapját kihagyjuk). Ezt rekurzívan folytatva kapjuk meg a Koch-görbét, másképpen Koch-féle hópelyhet.

Írtam egy egyszerű Java programot, amely n=1-től 9-ig paraméterezhetően kirajzolja a Koch-görbét egy grafikus felületre. Így működik:

Koch-görbe rajzolását bemutató program működése

A program elkészítéséhez néhány alapvető dolgot kell csupán tudni:

  • Vászontechnikával tudunk swing GUI felületre (Graphics osztályú g objektum) rajzolni, ahol a koordináta-rendszer origója egy téglalap alakú terület bal felső csúcsa, X jobbra növekszik, Y pedig lefelé növekszik.
  • Kétféle szín áll rendelkezésre: háttérszín (most Color.WHITE), illetve rajzolószín (most Color.BLUE).
  • A rajzoláshoz grafikai primitíveket használhatunk, például pont, szakasz, téglalap, ellipszis. Szakaszt két végpontjának koordinátáival tudunk rajzolni a drawLine() metódussal.
  • Be kell állítani a vászon méreteit, azaz annak a komponensnek (JPanel-ből öröklött KochPanel osztályú pnKoch objektum) a méreteit, amelyre ráfeszül a vászon.
  • Egy Slider osztályú sSzint nevű vezérlőobjektum ChangeListener figyelőinterfész stateChanged() eseménykezelő metódust implementáló objektumával paraméterezzük a rajzolást 1-től 9-ig.
  • A pnKoch objektumnak küldött repaint() üzenet/metódushívás meghívja a felüldefiniált paintComponent() metódust.
1
2
3
4
5
6
7
8
  @Override
  protected void paintComponent(Graphics g) {
    super.paintComponent(g);
    g.setColor(Color.BLUE);
    koch(n, 200, 51, 60, 300, g);
    koch(n, 60, 300, 340, 300, g);
    koch(n, 340, 300, 200, 51, g);
  }

 
A szakasz négy darab harmad akkora szakaszra osztását a megfelelően paraméterezett rekurzív metódushívások oldják meg az alábbi lépéseket követve:

Koch-görbe rajzolásának fázisai

A rekurzív rajzolást a koch() metódus végzi el, ahol a fraktál szabályának megfelelően szakaszharmadolás és a szükséges pontok koordinátáinak (szakaszok végpontjai) kiszámítása történik:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
  private void koch(int n, int x1, int y1, int x5, int y5, Graphics g) {
    if(n==1)
      g.drawLine(x1, y1, x5, y5);
    else {
      double gy=Math.sqrt(3)/6;
      int dx=x5-x1,                       dy=y5-y1,
          x2=x1+dx/3,                     y2=y1+dy/3,
          x3=(int)((x1+x5)/2+gy*(y1-y5)), y3=(int)((y1+y5)/2+gy*(x5-x1)),
          x4=x1+dx*2/3,                   y4=y1+dy*2/3;
      koch(n-1, x1, y1, x2, y2, g);
      koch(n-1, x2, y2, x3, y3, g);
      koch(n-1, x3, y3, x4, y4, g);
      koch(n-1, x4, y4, x5, y5, g);
    }
  }

 
A Koch-görbének van néhány érdekes tulajdonsága:

  • kerülete minden rekurzív lépésben minden határon túl növekszik, azaz a végtelenhez tart,
  • területe véges, hiszen minden rekurzív lépésben belefér a háromszög köré írható körbe,
  • dimenziója tört, ~ 1,261859.

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ó alkalomra építő 29-36. Grafikus felhasználói felület alkalomhoz kötődik.

A képernyőről a videó a FlashBack Express programmal, a videóból az animált gif az aconvert.com weboldalon készült.

Ismerkedjünk Lambda-kifejezésekkel!

Lambda-kifejezésA Java 8-tól használhatunk Lambda-kifejezéseket, amivel hatékonyabban, rövidebben és könnyebben valósíthatunk meg tipikus műveleteket.

Korábban általában az eseménykezelést globálisan (interfészek implementálásával), vagy lokálisan (névtelen interfész implementálásával) oldottuk meg, illetve besegítettek adapterek is. Sok- és többféle eseménynél ez a forráskódunk elaprózódásához vezetett, ami nehézkes olvashatóságot és karbantarthatóságot eredményezett.

A lambda-kifejezés egy olyan kódrészlet, amelyben valamihez hozzárendelünk valamit (x -> y), például egy metódus paraméteréhez a végrehajtandó forráskódot. Ehhez építünk a funkcionális interfészekre és a metódus referenciákra (szintén Java 8-tól), illetve a típus kikövetkeztetés képességére is (Java 7-től).

A kiválogatás programozási tételt valósítjuk meg többféle implementációval, felhasználva a Java nyelv újdonságait, és a fentieken kívül még a Stream API-t is.

Adatforrás

Először is kellenek adatok, hiszen azokat dolgozzuk fel. Egy Termek osztályú egyszerű POJO-val dolgozunk, nev és ar tulajdonságokkal, generált konstruktorral, getter metódusokkal és toString()-gel. Az adatforrást biztosító absztrakt Lista ősosztályban a POJO-kból felépítünk egy termekLista nevű generikus listát (például CSV vagy XML fájlból beolvasva az összetartozó adatokat) – listaFeltolt() eljárás – és implementálunk egy univerzálisan használható listaKiir(String uzenet, List termekLista) eljárást is.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
abstract class Lista {
  private File xmlFajl=new File("./files/prod.xml");
  private File csvFajl=new File("./files/prod.csv");
  protected ArrayList termekLista=null;

  public Lista() {
    listaFeltolt();
    listaKiir("Összes termék listája", termekLista);
  }
 
  private void listaFeltolt() {
    …
  }

  public void listaKiir(String uzenet, List termekLista) {
    System.out.print(uzenet+" - ");
    if(termekLista.isEmpty()) {
      System.out.println("Nincs ilyen termék.\n");
      return;
    }
    System.out.println(termekLista.size()+" db:");
    termekLista.forEach(termek -> System.out.println(termek));
    System.out.println();
  }
}

 
Örökítünk három utódosztályt a Lista osztályból, amelyek különbözőképpen dolgozzák fel a termekLista-t, bemutatva a fejlődés útját, illetve a rendelkezésre álló lehetőségeket.

Válogassunk a termékek közül négyféleképpen és adjuk vissza azon termékeket, amelyek:

  • limit alatti áron kaphatók,
  • ára limit1 és limit2 közé esik (zárt intervallumban),
  • neve adott szöveggel kezdődik (kis- és nagybetű különbözik),
  • neve adott szöveget tartalmaz (kis- és nagybetű nem különbözik)!

1. változat

Hagyományos megközelítéssel a fentiek megvalósításához külön egy-egy függvény tartozik, ahogyan az alábbiakban látható:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Kivalogatas1 extends Lista {

  private List<Termek> termekListaLimitAr1(int limit) {
    List<Termek> lista=new ArrayList<>();
//    for (int i = 0; i < termekLista.size(); i++) //1
//      if(termekLista.get(i).getAr()<limit)
//        lista.add(lista.get(i));
////    Iterator i=termekLista.iterator(); //2
////    while(i.hasNext()) {
////      Termek termek=i.next();
////      if(termek.getAr()<limit)
////        lista.add(termek);
////    }
//////    for (Termek termek : termekLista) //3
//////      if(termek.getAr()<limit)
//////        lista.add(termek);
////////    termekLista.stream(). //4
////////      filter(termek -> termek.getAr()<limit).
////////      forEach(termek -> lista.add(termek));
    lista=termekLista.stream(). //5
      filter(termek -> termek.getAr()<limit).
      collect(Collectors.toList());
    return lista;
  }

  private List<Termek> termekListaLimitAr2(int limit1, int limit2) {
    List<Termek> lista=new ArrayList<>();
    termekLista.stream().
      filter(termek -> limit1<=termek.getAr() && termek.getAr()<=limit2).
      forEach(termek -> lista.add(termek));
    return lista;
  }
 
  private List<Termek> termekListaSzoveg1(String szoveg) {
    List<Termek> lista=new ArrayList<>();
    termekLista.stream().
      filter(termek -> termek.getNev().startsWith(szoveg)).
      forEach(termek -> lista.add(termek));
    return lista;
  }

  private List<Termek> termekListaSzoveg2(String szoveg) {
    List<Termek> lista=new ArrayList<>();
    termekLista.stream().
      filter(termek -> termek.getNev().toLowerCase().
        contains(szoveg.toLowerCase())).
      forEach(termek -> lista.add(termek));
    return lista;
  }

  public void run() {
    listaKiir("Terméklista - ár<10", termekListaLimitAr1(10));
    listaKiir("Terméklista - 10<=ár<=20", termekListaLimitAr2(10, 20));
    listaKiir("Terméklista - 'Sir'-rel kezdődő terméknevek (kis- és nagybetű különbözik)",
      termekListaSzoveg1("Sir"));
    listaKiir("Terméklista - 'hot'-ot tartalmazó terméknevek (kis- és nagybetű nem különbözik)",
      termekListaSzoveg2("hot"));
  }
}

 
A termekListaLimitAr1() függvényben látható ötféle lehetőség a kiválogatásra a termekLista-ból:

  • //1: hagyományos, index alapú változat,
  • //2: iterátorra közvetlenül építő változat,
  • //3: bejáró ciklus, iterátorra közvetve építő változat,
  • //4: Stream API-ra építő változat, kiválogatás lambda-kifejezéssel (filter), a megmaradó termékekre végrehajtandó forEach művelet lambda kifejezéssel,
  • //5: Stream API-ra építő változat, kiválogatás lambda-kifejezéssel (filter), a megmaradó termékeket összegyűjtő/leképező collect művelettel.

Jól megfigyelhető, hogy négy függvény vázszerkezete megegyezik, és csupán a filter-ben található lambda-kifejezések különböznek. Ez a megoldás meglehetősen redundáns, nem általánosítható, valamint további műveletek megvalósítása további függvények implementálását igényli.

2. változat

Őrizzük meg a négyféle funkciót, sőt tegyük lehetővé, hogy ez tetszőlegesen bővíthető legyen. Használjunk saját generikus, funkcionális Feltetel interfészt saját döntés megvalósítását biztosítani tudó implementálandó teszt() függvénnyel, az alábbiak szerint:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
interface Feltetel<T> {
  boolean teszt(T t);  
}

class Kivalogatas2 extends Lista {
 
  private List<Termek> termekListaFeltetel(Feltetel<Termek> feltetel) {
    List<Termek> lista=new ArrayList<>();
//    for (Termek termek : termekLista)
//      if(feltetel.teszt(termek))
//        lista.add(termek);
    termekLista.stream().
      filter(termek -> feltetel.teszt(termek)).
      forEach(termek -> lista.add(termek));
    return lista;
  }
 
  public void run() {
    listaKiir("Terméklista - ár<10", termekListaFeltetel(new Feltetel<Termek>() {
      @Override
      public boolean teszt(Termek t) {
        return t.getAr()<10;
      }
    }));
//    listaKiir("Terméklista - ár<10", termekListaFeltetel((Termek termek) -> termek.getAr()<10));
    listaKiir("Terméklista - 10<=ár<=20",
      termekListaFeltetel((Termek termek) -> 10<=termek.getAr() && termek.getAr()<=20));
    listaKiir("Terméklista - 'Sir'-rel kezdődő terméknevek (kis- és nagybetű különbözik)",
      termekListaFeltetel((Termek termek) -> termek.getNev().startsWith("Sir")));
    listaKiir("Terméklista - 'hot'-ot tartalmazó terméknevek (kis- és nagybetű nem különbözik)",
      termekListaFeltetel((Termek termek) -> termek.getNev().toLowerCase().contains("hot".toLowerCase())));
  }
}

 
A termekListaFeltetel() függvény paramétere a saját Feltetel interfészünket implementáló névtelen osztály példánya, amely felhasználható:

  • //6: ciklusban egyszerű feltételként,
  • //7: Stream API filter műveletében megadott lambda-kifejezésben,
  • //8: a listaKiir() metódusban paraméterként átadva névtelen osztály példányaként,
  • //9-től: a listaKiir() metódusban paraméterként átadva lambda-kifejezésként.

Látszik, hogy többféle kiválogató művelethez egyetlen implementált függvény szükséges. Ez a megoldás már jóval általánosabb.

3. változat

A saját interfész helyett használjuk fel a beépített Predicate generikus, funkcionális interfészt, építve annak test() függvényére az alábbiak szerint:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Kivalogatas3 extends Lista {
 
  private List<Termek> termekListaFeltetel(Predicate<Termek> feltetel) {
    List<Termek> lista=new ArrayList<>();
    termekLista.stream().
      filter(termek -> feltetel.test(termek)).
      forEach(termek -> lista.add(termek));
    return lista;
  }
 
  public void run() {
    listaKiir("Terméklista - ár<10", termekListaFeltetel(new Predicate<Termek>() {
      @Override
      public boolean test(Termek t) {
        return t.getAr()<10;
      }
    }));
    listaKiir("Terméklista - ár<10", termekListaFeltetel(
      (Termek termek) -> termek.getAr()<10));
    listaKiir("Terméklista - 10<=ár<=20",
      termekListaFeltetel((Termek termek) -> 10<=termek.getAr() && termek.getAr()<=20));
    listaKiir("Terméklista - 'Sir'-rel kezdődő terméknevek (kis- és nagybetű különbözik)",
      termekListaFeltetel((Termek termek) -> termek.getNev().startsWith("Sir")));
    listaKiir("Terméklista - 'hot'-ot tartalmazó terméknevek (kis- és nagybetű nem különbözik)",
      termekListaFeltetel((Termek termek) -> termek.getNev().toLowerCase().contains("hot".toLowerCase())));
  }
}

 

Belépési pont

Végül következzen a közös belépési pont, amelyben tetszőlegesen aktiválható és tesztelhető mindhárom változat működése:

1
2
3
4
5
6
7
public class Kivalogatas {
  public static void main(String[] args) {
    //new Kivalogatas1().run();
    //new Kivalogatas2().run();
    new Kivalogatas3().run();
  }
}

 

Mit ír ki a program a konzolra?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
Összes termék listája - 77 db:
Chai, 18.0
Chang, 19.0
Aniseed Syrup, 10.0
Chef Anton's Cajun Seasoning, 22.0
Chef Anton's Gumbo Mix, 21.35
Grandma's Boysenberry Spread, 25.0
Uncle Bob's Organic Dried Pears, 30.0
Northwoods Cranberry Sauce, 40.0
Mishi Kobe Niku, 97.0
Ikura, 31.0
Queso Cabrales, 21.0
Queso Manchego La Pastora, 38.0
Konbu, 6.0
Tofu, 23.25
Genen Shouyu, 15.5
Pavlova, 17.45
Alice Mutton, 39.0
Carnarvon Tigers, 62.5
Teatime Chocolate Biscuits, 9.2
Sir Rodney's Marmalade, 81.0
Sir Rodney's Scones, 10.0
Gustaf's Knäckebröd, 21.0
Tunnbröd, 9.0
Guaraná Fantástica, 4.5
NuNuCa Nuß-Nougat-Creme, 14.0
Gumbär Gummibärchen, 31.23
Schoggi Schokolade, 43.9
Rössle Sauerkraut, 45.6
Thüringer Rostbratwurst, 123.79
Nord-Ost Matjeshering, 25.89
Gorgonzola Telino, 12.5
Mascarpone Fabioli, 32.0
Geitost, 2.5
Sasquatch Ale, 14.0
Steeleye Stout, 18.0
Inlagd Sill, 19.0
Gravad lax, 26.0
Côte de Blaye, 263.5
Chartreuse verte, 18.0
Boston Crab Meat, 18.4
Jack's New England Clam Chowder, 9.65
Singaporean Hokkien Fried Mee, 14.0
Ipoh Coffee, 46.0
Gula Malacca, 19.45
Rogede sild, 9.5
Spegesild, 12.0
Zaanse koeken, 9.5
Chocolade, 12.75
Maxilaku, 20.0
Valkoinen suklaa, 16.25
Manjimup Dried Apples, 53.0
Filo Mix, 7.0
Perth Pasties, 32.8
Tourtiere, 7.45
Pâté chinois, 24.0
Gnocchi di nonna Alice, 38.0
Ravioli Angelo, 19.5
Escargots de Bourgogne, 13.25
Raclette Courdavault, 55.0
Camembert Pierrot, 34.0
Sirop d'érable, 28.5
Tarte au sucre, 49.3
Vegie-spread, 43.9
Wimmers gute Semmelknödel, 33.25
Louisiana Fiery Hot Pepper Sauce, 21.05
Louisiana Hot Spiced Okra, 17.0
Laughing Lumberjack Lager, 14.0
Scottish Longbreads, 12.5
Gudbrandsdalsost, 36.0
Outback Lager, 15.0
Flotemysost, 21.5
Mozzarella di Giovanni, 34.8
Röd Kaviar, 15.0
Longlife Tofu, 10.0
Rhönbräu Klosterbier, 7.75
Lakkalikööri, 18.0
Original Frankfurter grüne Soße, 13.0

Terméklista - ár<10 - 11 db:
Konbu, 6.0
Teatime Chocolate Biscuits, 9.2
Tunnbröd, 9.0
Guaraná Fantástica, 4.5
Geitost, 2.5
Jack's New England Clam Chowder, 9.65
Rogede sild, 9.5
Zaanse koeken, 9.5
Filo Mix, 7.0
Tourtiere, 7.45
Rhönbräu Klosterbier, 7.75

Terméklista - 10<=ár<=20 - 29 db:
Chai, 18.0
Chang, 19.0
Aniseed Syrup, 10.0
Genen Shouyu, 15.5
Pavlova, 17.45
Sir Rodney's Scones, 10.0
NuNuCa Nuß-Nougat-Creme, 14.0
Gorgonzola Telino, 12.5
Sasquatch Ale, 14.0
Steeleye Stout, 18.0
Inlagd Sill, 19.0
Chartreuse verte, 18.0
Boston Crab Meat, 18.4
Singaporean Hokkien Fried Mee, 14.0
Gula Malacca, 19.45
Spegesild, 12.0
Chocolade, 12.75
Maxilaku, 20.0
Valkoinen suklaa, 16.25
Ravioli Angelo, 19.5
Escargots de Bourgogne, 13.25
Louisiana Hot Spiced Okra, 17.0
Laughing Lumberjack Lager, 14.0
Scottish Longbreads, 12.5
Outback Lager, 15.0
Röd Kaviar, 15.0
Longlife Tofu, 10.0
Lakkalikööri, 18.0
Original Frankfurter grüne Soße, 13.0

Terméklista - 'Sir'-rel kezdődő terméknevek (kis- és nagybetű különbözik) - 3 db:
Sir Rodney's Marmalade, 81.0
Sir Rodney's Scones, 10.0
Sirop d'érable, 28.5

Terméklista - 'hot'-ot tartalmazó terméknevek (kis- és nagybetű nem különbözik) - 2 db:
Louisiana Fiery Hot Pepper Sauce, 21.05
Louisiana Hot Spiced Okra, 17.0

 
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 21-24. óra: Objektumorientált programozás 2. rész, 25-28. óra: Objektumorientált programozás 3. rész, valamint a Java EE szoftverfejlesztő tanfolyam szakmai moduljának 9-12. óra: XML feldolgozás alkalmaihoz kötődik.

Hány éves a kapitány?

Hány éves a kapitány?A problémamegoldó, logikus gondolkodásra nevelő képzések anyagában, illetve felvételi feladatsorokban is sokszor megtalálható – többféle változatban is.

Lássunk egyet a népszerű „Hány éves a kapitány?” típusú feladatok közül!

Három elefántot kell berakodnunk – szólt a hajóskapitány az első tiszthez.
És hány évesek ezek az elefántok? – kérdezte az első tiszt.
Mindegyik elmúlt már két éves és életkoraik szorzata 2450 – volt a válasz.
Hát életkoraik összege?
Azt fölösleges elárulnom, mert abból még nem tudnád megállapítani életkorukat – mondta a kapitány, majd hozzátette: Az egyikük idősebb nálam.
Akkor már tudom, hogy hány évesek az elefántok – mondta az első tiszt.

Feltéve, hogy tényleg tudta; … hány éves a kapitány?

Hogyan használhatnánk a feladat megoldásához programozáshoz kötődő ismereteinket?

Állítsunk elő olyan három szorzótényezőt, amelyek szorzata 2450 és egyben írassuk ki az összegüket is a konzolra!

1
2
3
4
5
6
7
8
9
10
public class Kapitany {
  public static void main(String[] args) {
    for(int i=3; i<=100; i++)
      for(int j=i; j<=100; j++)
        for(int k=j; k<=100; k++)
          if(i*j*k==2450)
            System.out.println(
              i+"*"+j+"*"+k+"=2450\t"+i+"+"+j+"+"+k+"="+(i+j+k));
  }
}

 
Az i, j, k a három elefánt életkorát jelöli. Mivel mindegyik elmúlt két éves (és feltételezzük, hogy életkoraik egész számmal kifejezhetők), így i=3-ról indul. Az elefántok lehetnek egyidősek, ezért j=i-ről és k=j-ről indul. Nincs kizárt életkor, így a változók léptethetők egyesével. Az i, j, k monoton növekvő sorozatot alkot, ezért a kiírásban nem lesznek olyan sorok, amelyek csupán a szorzótényezők sorrendjében térnek el. Durva felső becslés a 100, hiszen az elefántok általában 60-70 évig élnek. Eredményül ezt kapjuk:

1
2
3
4
5
6
7
5*5*98=2450     5+5+98=108
5*7*70=2450     5+7+70=82
5*10*49=2450    5+10+49=64
5*14*35=2450    5+14+35=54
7*7*50=2450     7+7+50=64
7*10*35=2450    7+10+35=52
7*14*25=2450    7+14+25=46

 
Az eredményből milyen következtetés(eke)t lehet levonni és mi a megoldás?

Az egyszer előforduló összegeket ki kell zárni, mert abból az első tiszt tudná az elefántok életkorát. Többször előforduló összegként marad a 64. Tehát az elefántok lehetnek 5, 10, 49, illetve 7, 7, 50 évesek. Mivel a kapitánynál idősebb az egyik elefánt, így a kapitány nem lehet 48 éves vagy fiatalabb (mert ekkor nem lenne egyértelmű az életkora), illetve nem lehet 50 éves vagy idősebb (mert ekkor nem lenne nála idősebb elefánt). Tehát a kapitány 49 éves.

(Másképpen megközelítve: a 2450 prímtényezős felbontása 2*52*72, amiből ugyanezekre a következtetésekre juthatunk.)


A feladat további változatai

  • Egy hajó hosszának, az árbóc magasságának, a kapitány kisfia életkorának és a kapitány életkorának szorzata 303335. Hány éves a kapitány?
  • A kapitány most kétszer annyi idős, mint a hajója volt akkor, amikor a kapitány kétszer volt annyi idős, mint most a hajója. A kapitány és a hajója összesen 70 éves. Hány éves a kapitány?
  • A Fekete Kalóz néven elhíresült kalózkapitány egyik sikeres kalandja után kiszámíttatta saját maga és kisfia életkorának, valamint hajója hosszának a szorzatát. Az eredmény 26 159 lett, amelyet mint szerencseszámot egy medálra vésetett és mindig a nyakában hordott. Hány éves a kapitány? (A hajóhosszt méterekben mérték, és a mérőszám egész szám!)
  • Te vezeted az utasszállító repülőt. Budapesten felszáll 11 utas. Bécsben leszáll 5 és felszáll 9. Párizsban 1 kivételével mindenki leszáll. Hány éves a kapitány?
  • A kapitány hajója most 40 éves. Kétszer annyi idős, mint amennyi a kapitány volt akkor, amikor a hajó annyi idős volt, mint a kapitány most. Hány éves a kapitány?

A bejegyzéshez tartozó forráskódot ILIAS e-learning tananyagban tesszük elérhetővé tanfolyamaink résztvevői számára.

Ajánlott irodalom

Aki kedvet kapott és beszerezne néhány könyvet – tele érdekes, gondolkodtató, kreatív, logikai feladatokkal – ajánlom az alábbiakat:

  • Katona, R. (szerk): Logikai egypercesek – az elme játékai, 2. kiadás, DFT-Hungária Könyvkiadó, Budapest, 2006, ISBN 963 9473 55 3
  • Róka, S.: 2×2 néha 5? – Paradoxonok, hibás bizonyítások, Tóth Könyvkereskedés és Kiadó Kft., Debrecen, 2008, ISBN 963 5965 24 3
  • Károlyi, Zs.: Csak logIQsan!, 2. javított kiadás, Typotex Elektronikus Kiadó Kft., Budapest, 2017, ISBN 963 279 693 5
  • Róka, S.: Egypercesek – Feladatok matematikából 14-18 éveseknek, Tóth Könyvkereskedés Kft., Debrecen, 1997
  • G. Nagy, L.: A világ legújabb logikai rejtvényei, Magyar Könyvklub, H. n., 2001, ISBN 963 547 512 8

Haladóknak ajánlom:

  • Smullyan, R.: A hölgy vagy a tigris? – és egyéb logikai feladatok, 2. javított kiadás, Typotex Kiadó Kft., Budapest, 2002, ISBN 963 7546 63 4
  • Smullyan, R.: Mi a címe ennek a könyvnek? – Drakula rejtélye és más logikai feladványok, Typotex Elektronikus Kiadó Kft., Budapest, 1996, ISBN 963 7546 64 2
  • Shasha, D.: Dr. Ecco talányos kalandjai, Typotex Kiadó – SHL Hungary Kft., 2000, ISBN 963 9132 72 1

A feladat a Java SE szoftverfejlesztő tanfolyam szakmai moduljának 5-8. óra: Vezérlési szerkezetek alkalmához kötődik.

Barátságos számpárok

Azokat a számpárokat, amelyekre igaz, hogy az egyik szám önmagánál kisebb osztóinak összege megegyezik a másik számmal és fordítva, külön-külön barátságos számoknak, együtt barátságos számpárnak hívjuk.

Másképpen: legyen d(n) az n természetes szám önmagánál kisebb osztóinak összege. Ha d(a)=b és d(b)=a, ahol a≠b, akkor a és b barátságos számpár.

Például: (220; 284), hiszen a 220 önmagánál kisebb osztói: 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110 és ezek összege 284, illetve 284 önmagánál kisebb osztói: 1, 2, 4, 71, 142 és ezek összege 220.

Írjunk Java programot, amely kiírja az 1-10000 zárt intervallumban található barátságos számpárokat!

1. megoldás

A baratsagosSzamparok1() eljárás ciklusai a brute force módszer szerint behelyesítik az összes lehetséges számot. Minimális lépésszám csökkentésre adódik lehetőség, hiszen a belső ciklus j változója i+1-ről indítható (így a megtalált számpárok nem íródnak ki fordítva is, mert teljesül, hogy i<j).

Az osztokOsszege1(n) függvény is minden lehetséges osztót figyelembe vesz 1-től n-1-ig.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
  private static int osztokOsszege1(int n) {
    int s=0;
    for(int i=1; i<n; i+=1)
      if(n%i==0)
        s+=i;
    return s;
  }

  private static void baratsagosSzamparok1() {
    System.out.println("Barátságos számpárok 1-től 10000-ig:");
    for(int i=1; i<=10000; i++)
      for(int j=i+1; j<=10000; j++)
        if(i==osztokOsszege1(j) && j==osztokOsszege1(i))
          System.out.println("("+i+"; "+j+")");
  }

 

2. megoldás

Kisebb módosításokkal a lépésszám csökkenthető. A baratsagosSzamparok2() eljárás külső ciklusánál figyelembe vettem, hogy a legkisebb barátságos számpár kisebb tagja nagyobb 200-nál. Mivel a barátságos számpárok tagjainak paritása mindig megegyezik (azaz mindkettő páros vagy mindkettő páratlan), így a belső ciklus j változója indítható i+2-ről és léptethető kettesével (j+=2), és továbbra is teljesül, hogy i<j.

Az osztokOsszege2(n) függvényt is módosítottam. Mivel az 1 minden számnak osztója, illetve a 2 minden páros számnak osztója, így s lehet 3 vagy 1 és a ciklus indítható 3-ról. A páros számok esetén a számnál kisebb legnagyobb osztó maximum n/2 lehet, illetve ugyanez páratlan számok esetén n/3 lehet. Ezekre figyelve a max változó adja a ciklus léptetésének felső határát. Az i változó léptetésénél figyelembe vettem, hogy páratlan számnak csak páratlan osztói lehetnek (i=3-mal szinkronban).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
  private static int osztokOsszege2(int n) {
    int s=(n%2==0?3:1);
    int max=(n%2==0?n/2:n/3);
    int lepes=(n%2==0?1:2);
    for(int i=3; i<=max; i+=lepes)
      if(n%i==0)
        s+=i;
    return s;
  }

  private static void baratsagosSzamparok2() {
    System.out.println("Barátságos számpárok 1-től 10000-ig:");
    for(int i=200; i<=10000; i++)
      for(int j=i+2; j<=10000; j+=2)
        if(i==osztokOsszege2(j) && j==osztokOsszege2(i))
          System.out.println("("+i+"; "+j+")");  
  }

 

3. megoldás

Az eddigi két egymásba ágyazott ciklus helyett átszervezhető a baratsagosSzamparok3() eljárás. A j>i && osztokOsszege2(j)==i feltétel kiértékelése így sokkal hatékonyabb.

1
2
3
4
5
6
7
8
  private static void baratsagosSzamparok3() {
    System.out.println("Barátságos számpárok 1-től 10000-ig:");
    for(int i=200; i<=10000; i++) {
      int j=osztokOsszege2(i);
      if(j>i && osztokOsszege2(j)==i)
        System.out.println("("+i+"; "+j+")");  
    }
  }

 
Mit gondolsz, milyen nagyságrendű különbségek adódnak, ha összehasonlítjuk a három megoldás futási idejét?

Az 1. megoldás futási ideje 1104156 ms, a 2. megoldásé 257055 ms, a 3. megoldásé 121 ms. A konkrét értékek helyett a nagyságrendet megfigyelve a különbség nagyon látványos.

A feladat megoldása során mindhárom megoldás helyes és megkapjuk az intervallumban található öt barátságos számpárt: (220; 284), (1184; 1210), (2620; 2924), (5020; 5564), (6232; 6368).

A bejegyzéshez tartozó teljes – időméréssel kiegészített – forráskódot ILIAS e-learning tananyagban tesszük elérhetővé tanfolyamaink résztvevői számára.

Források:

A feladat a Java SE szoftverfejlesztő tanfolyam szakmai moduljának 9-12. óra: Metódusok, rekurzió alkalomhoz kötődik.

CHOO + CHOO = TRAIN

Most nem a híres kisvonatról van szó, hanem egy ismert kriptoaritmetikai feladványról. Ebben a feladattípusban egyszerű matematikai műveletek szerepelnek és a különböző betűk különböző számjegyeket jelölnek. Általában többféleképpen megoldhatók: intuíció, ötlet, módszeres próbálkozás, következtetés, kizárás vagy klasszikus behelyettesítés. Ha van megoldás és meg is találunk egyet, akkor a következő kérdés az, hogy van-e még, illetve összesen hány megoldás van?

Íme a feladat:

Érdemes minden megoldás során figyelembe venni a minden számjegyet 0-9-ig végigpróbáló lépések helyett legalább az alábbi öt feltételt:

  • C >= 5, hiszen CHOO olyan négyjegyű szám, aminek a kétszerese ötjegyű szám,
  • T = 1, mivel két négyjegyű szám összege 10000 < TRAIN < 20000 (ebben az esetben),
  • O >= 6, hiszen maradéknak képződnie kell, mert I és N különbözik,
  • 2 <= N < I és
  • I >= 3 és szintén a maradékképződés miatt.

Esetleg még tovább gondolkodva, felfedezhetünk egyéb összefüggéseket, illetve kizárhatunk egyéb értékeket, így jelentősen csökkenthető egy-egy Java implementáció lépésszáma.
 

1. megoldás

Ez adatszerkezet nélküli megoldás, így eléggé összetett feltétellel valósul meg a művelet teljesülése (megfelelő helyiértékek használatával) és a különbözőségek vizsgálata.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
  public static void chooChooTrain1() {
    for (int c = 5; c <= 9; c++)
      for (int h = 0; h <= 9; h++)
        for (int o = 6; o <= 9; o++)
          for (int r = 0; r <= 9; r++)
            for (int a = 0; a <= 9; a++)
              for (int i = 3; i <= 9; i++)
                for (int n = 2; n < i; n++)
                  if((1000*c+100*h+10*o+o)*2 == 10000+1000*r+100*a+10*i+n &&
                      c!=h && c!=o && c!=1 && c!=r && c!=a && c!=i && c!=n &&
                      h!=o && h!=1 && h!=r && h!=a && h!=i && h!=n &&
                      o!=1 && o!=r && o!=a && o!=i && o!=n &&
                      r!=1 && r!=a && r!=i && r!=n &&
                      a!=1 && a!=i && a!=n &&
                      i!=1 && i!=n &&
                      n!=1)
                    System.out.println(
                      "  "+c+h+o+o+"\n+ "+c+h+o+o+"\n------\n "+1+r+a+i+n+"\n");
  }

 

2. megoldás

Itt az ellenőrzési feltétel egyszerűbb, mert a különbözőség/egyediség tesztelését áthárítottam a halmazszerűen működő HashSet generikus kollekcióra, építve annak beépített képességére.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
  public static void chooChooTrain2() {
    HashSet hs=new HashSet();
    for (int c = 5; c <= 9; c++)
      for (int h = 0; h <= 9; h++)
        for (int o = 6; o <= 9; o++)
          for (int r = 0; r <= 9; r++)
            for (int a = 0; a <= 9; a++)
              for (int i = 3; i <= 9; i++)
                for (int n = 2; n < i; n++) {
                  hs.add(c); hs.add(h); hs.add(o);
                  hs.add(1); hs.add(r); hs.add(a); hs.add(i); hs.add(n);
                  if(hs.size()==8 &&
                      (1000*c+100*h+10*o+o)*2 == 10000+1000*r+100*a+10*i+n)
                    System.out.println(
                      "  "+c+h+o+o+"\n+ "+c+h+o+o+"\n------\n "+1+r+a+i+n+"\n");
                  hs.clear();
                }
  }

 
Mit gondolsz, melyik megoldás hajtódik végre gyorsabban? Miért?

Mivel a két megoldásnál a ciklusok szervezése megegyezik, így a használt adatszerkezet dönt (hiszen annak konstrukciós és szelekciós, azaz karbantartási műveletei vannak). Az 1. megoldás a gyorsabb, mert nem használ adatszerkezetet. A 2. megoldás lényegesen lassabban fut, mert a generikus kollekció műveletei miatt az automatikus szemétgyűjtő tevékenység erősen igénybe vett. A különbség nagyságrendileg 15-szörös.

A feladatnak két megoldása van: 5466 + 5466 = 10932 és 5488 + 5488 = 10976.

A bejegyzéshez tartozó teljes – időméréssel kiegészített – forráskódot ILIAS e-learning tananyagban tesszük elérhetővé tanfolyamaink résztvevői számára.

Akinek kedve támadt, lásson hozzá hasonló feladatokhoz:

A feladat a Java SE szoftverfejlesztő tanfolyam szakmai moduljának 9-12. óra: Metódusok, rekurzió alkalomhoz, illetve a 21-24. óra: Objektumorientált programozás, 2. rész alkalomhoz kötődik.

Optikai csalódások

A grafikus felülettel rendelkező Java programok (Swing, FX, webkomponensek, HTML+CSS) fejlesztése során igény adódhat arra, hogy a GUI komponensek saját beépített rajzoló/renderelő képességét felülírjuk/-definiáljuk, hogy egy-egy nyomógomb, menüpont, rádiógomb másképpen nézzen ki. Léteznek beépített rajzoló funkciók is.

Ha például grafikont kell beilleszteni egy alkalmazásba, akkor használjunk és igényeink szerint szabjunk testre egy JFreeChart csomagbeli grafikont, illetve előfordulhat, hogy találhatunk egy olyat a JFreeChart Demo-ban, ami éppen megfelel a megrendelő igényeinek.

Persze a műfaj nem ér itt véget. Időnként kreatívabb ábrák, rajzok, grafikák megjelenítésére is használhatjuk a beépített – általában téglalap alakú – komponenseket. Ehhez egyszerűen csak felül kell írni/definiálni a paint() metódusukat és vászontechnikával, a megszokott képernyős koordináta-rendszerben, grafikai primitíveket (pont, téglalap, ellipszis) és színeket kell megfelelően paraméterezni.

Az optikai csalódások igen népszerűek, és az egyszerűbb fiziológiai és kognitív illúziók könnyen lerajzolhatók a fenti eszköztárral, hiszen csupán színek, alakzatok, kontraszt, távolság, mélység, térhatás segítségével valósulnak meg.

Íme három egyszerű példa, hogyan állítható elő optikai csalódás Java implementációval!

1. példa

Optikai csalódás 1

1
2
3
4
5
6
7
8
9
10
11
12
  @Override
  public void paint(Graphics g) {
    int egyseg=20, sorDb=10, oszlopDb=20;
    for(int i=1; i<=sorDb; i++) {
      int eltolas=(i%2==1)?0:egyseg/2;
      g.setColor(Color.BLACK);
      for(int j=1; j<=oszlopDb; j+=2)
        g.fillRect(eltolas+(j-1)*egyseg, (i-1)*egyseg+i, egyseg, egyseg);
      g.setColor(Color.LIGHT_GRAY);
      g.drawLine(0, (i-1)*egyseg+i-1, egyseg*(oszlopDb-1), (i-1)*egyseg+i-1);
    }
  }

 

2. példa

Optikai csalódás 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
  @Override
  public void paint(Graphics g) {
    int egyseg=50, koz=10, sorDb=6, oszlopDb=8;

    g.setColor(Color.LIGHT_GRAY);
    g.fillRect(0, 0, oszlopDb*(egyseg+koz)-koz, sorDb*(egyseg+koz)-koz);

    g.setColor(Color.BLACK);
    for(int i=1; i<=sorDb; i++)
      for(int j=1; j<=oszlopDb; j++)
        g.fillRect((j-1)*(egyseg+koz), (i-1)*(egyseg+koz), egyseg, egyseg);

    g.setColor(Color.WHITE);
    for(int i=1; i<sorDb; i++)
      for(int j=1; j<oszlopDb; j++)
        g.fillOval(j*(egyseg+koz)-koz-2, i*(egyseg+koz)-koz-2, koz+4, koz+4);
  }

 

3. példa

Optikai csalódás 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
  @Override
  public void paint(Graphics g) {
    Point hely;
    for(int i=1; i<=4; i++)
      for(int j=1; j<=4; j++) {
        hely=new Point((i-1)*180, (j-1)*120);
        if((i+j)%2==1)
          minta1(g, hely);
        else
          minta2(g, hely);
      }
  }

  private void minta1(Graphics g, Point hely) {
    Point pozicio;
    for(int i=1; i<=4; i++)
      for(int j=1; j<=4; j++) {
        pozicio=new Point(hely.x+(i-1)*45, hely.y+(j-1)*30);
        if((i+j)%2==1)
          mintaAlap1(g, pozicio, Color.MAGENTA, Color.YELLOW);
        else
          mintaAlap2(g, pozicio, Color.YELLOW, Color.MAGENTA);
      }
  }

  private void minta2(Graphics g, Point hely) {
    Point pozicio;
    for(int i=1; i<=4; i++)
      for(int j=1; j<=4; j++) {
        pozicio=new Point(hely.x+(i-1)*45, hely.y+(j-1)*30);
        if((i+j)%2==1)
          mintaAlap2(g, pozicio, Color.MAGENTA, Color.YELLOW);
        else
          mintaAlap1(g, pozicio, Color.YELLOW, Color.MAGENTA);
      }
  }

  private void mintaAlap1(Graphics g, Point hely, Color kitolt, Color szin) {
    g.setColor(kitolt);
    g.fillRect(hely.x, hely.y, 45, 30);
    g.setColor(szin);
    g.fillRect(hely.x+2, hely.y+2, 13, 9);
    g.fillRect(hely.x+30, hely.y+19, 13, 9);
  }

  private void mintaAlap2(Graphics g, Point hely, Color kitolt, Color szin) {
    g.setColor(kitolt);
    g.fillRect(hely.x, hely.y, 45, 30);
    g.setColor(szin);
    g.fillRect(hely.x+30, hely.y+2, 13, 9);
    g.fillRect(hely.x+2, hely.y+19, 13, 9);
  }

 
A bejegyzéshez tartozó teljes forráskódot ILIAS e-learning tananyagban tesszük elérhetővé tanfolyamaink résztvevői számára.

Aki ezek után kedvet kapott, keressen hasonló ábrákat és tervezve, kódolva, tesztelve gyakoroljon! Ajánlom ezeket a weboldalakat:

Hasonló feladatok megoldásához a Java SE szoftverfejlesztő tanfolyam szakmai moduljának 29-36. Grafikus felhasználói felület alkalma után bátran hozzá lehet fogni, illetve érintjük még a GUI témakört a Java adatbázis-kezelő tanfolyam 33-40. óra: Grafikus kliensalkalmazás fejlesztése JDBC alapon alkalommal is.

Hogyan értékeljük az online vizsgafeladatot?

Tanfolyamaink követelményeinek teljesítéséhez több online tesztet kell kitölteni és egy komplex, online vizsgafeladatot kell megoldani.

A feladatspecifikáció mindig részletes, maximum 1 db A4-es oldal terjedelmű, folyó szövegben felsorolásokat is tartalmaz és szándékosan nincsenek benne ábrák. Törekszünk az egyértelmű megfogalmazása, de hagyunk mozgásteret egyéni értelmezésre is, amit – megfelelő indoklással – elfogadhatunk. Az online vizsgafeladat megoldásához bármilyen segédeszközt lehet használni.

Az online vizsgafeladat megoldásának tervezésére, implementálására, tesztelésére és dokumentálására és határidőre való feltöltésére körülbelül egy hét áll rendelkezésre. Közben online konzultációt biztosítunk, ahol megbeszéljük az ezzel kapcsolatos kérdéseket és rávezető (nem konkrét) segítséget biztosítunk.

vizsgafeladat értékelése

Figyelembe vett szempontok az online vizsgafeladat értékelése során

  • Objektumorientált szemléletmód alkalmazása
  • MVC architektúrális tervezési minta alkalmazása
  • Logikus MVC szeparáció
  • Egyértelműen elhatárolódó felelősségi kör: a modell, a nézet és a vezérlő azt és csak azt oldja meg, amit, ahogyan, amikor, ahányszor kell
  • Adatbázis-kapcsolatért felelős rész szeparációja
  • Vezérlésért felelős rész szeparációja
  • Megjelenítésért felelős rész szeparációja
  • MVC kommunikációs irányok betartása, megfelelő adatkonverzió
  • Szükség esetén singleton és factory típusú tervezési minta alkalmazása
  • Adatbázis-kapcsolat megfelelő menedzselése, nyitás, zárás, kivételkezelés
  • Szükséges adatbázis-karbantartó (CRUD) művelek megfelelő megvalósítása
  • Specifikáció pontos értelmezése
  • Specifikáció pontos megvalósítása
  • Specifikáció alapján tesztelés megvalósítása
  • Megfelelő GUI komponensek alkalmazása, elhelyezése, paraméterezése, kommuniká­ciója, eseménykezelése
  • Adatbázis olvasása során a keletkező eredménytábla és/vagy kivételobjektum megfelelően jut el a nézet réteghez
  • Modellvezérelt fejlesztés elveinek alkalmazása
  • Szükség esetén POJO és ezek adatszerkezeteinek konstrukciós és szelekciós műve­letei
  • Eseménykezelés logikus működésének megtervezése és megvalósítása
  • Extrém tesztadatokkal való hibakeresés, tesztelés
  • Felesleges forráskód-részletek nincsenek
  • Szintaktikai és/vagy szemantikai hibák nincsenek (Java, SQL, HQL oldalon egyaránt)
  • Projekt megfelelő elnevezése és szerkezete
  • Logikus és konvencióknak megfelelő elnevezések következetes alkalmazása
  • Algoritmusban, folyamatokban, saját modellekben való eligazodás, alkalmazkodás ké­pessége, ezek szintjei és megvalósulása
  • Szükséges programozási tételek felismerése, megvalósításuk, összeépítésük
  • Logikus gondolkodás és feladatmegoldás szintjei és alkalmazásuk
  • Hatékonysági szempontok ismerete és alkalmazása

Az online vizsgafeladatot – a tanfolyamot záró 53-56. óra: Összefoglalás alkalommal – közösen, részletesen meg is beszéljük: lépések, rétegek, funkciók, ellenőrzési/tesztelési lehetőségek, hibakeresés, tipikus problémák a megoldás során.

vizsgafeladat értékelése