Euler

Címke: Euler

3 blog bejegyzésnél szerepel:

Barátságos számok

Digitális Témahét 2017

Euler állatos feladata


22 db hozzá kapcsolódó címke:

2017 (24), 2018 (24), algoritmus (31), brute force (7), ciklusok (18), Digitális Témahét (8), előadás műhely-napon (24), fejtörő (11), hatékonyság (28), ingyenes esemény (34), Java forráskód (63), lépésszám (9), logikai feladat (21), matematika (30), metódus (30), objektumorientált programozás (85), programozás (106), programozási tételek (28), rendezvény 2017 (5), szakmai előadás (31), szakmai modul (96), többféle megoldás összehasonlítása (37)

Barátságos számok

Szerző:
Barátságos számok

Barátságos számokAzokat 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.

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

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.

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

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.

Digitális Témahét 2017

Szerző:

A Digitális Témahét 2016-ban indult országos rendezvénysorozat. Fő célja a digitális pedagógia módszertanának népszerűsítése és elterjesztése. A program fontos törekvése, hogy a digitáliskompetencia-fejlesztés az informatikán túl kiterjedjen más tantárgyakra is. A résztvevő pedagógusok és diákok változatos és kreatív iskolai projektek keretében fejleszthetik képességeiket technológiával támogatott tanulás során. A Digitális Témahét rendezvény minden meghirdetett programja ingyenes.

A 2016/2017-es tanévben a rendezvény április 3-7. között valósult meg. Kiemelt témakörök/szempontok:

  • a multidiszciplináris megközelítés: a matematika, a természet- és mérnöki tudományok, valamint a művészet- és társadalomtudományok együttes megjelenítése;
  • a tanítás eszközkészletének és módszereinek megújítása;
  • a pedagógiai innováció, a digitális pedagógia ösztönzése;
  • az informatikai pályaorientáció.

Meghirdetett eseményünk

2017-ben egy eseményt hirdettem meg Digitális Témahét 2017 rendezvényen.
Helyszín: 1056 Budapest, Váci utca 47., 3. emelet 309-es terem, megközelítés
Dátum és időpont: 2017. április 7. 18:00-21:00-ig
Az esemény ingyenes volt, de a részvétel előzetes regisztrációhoz kötött.

A három órás laborgyakorlat a Brit érmék projektfeladat (forrás: Project Euler #31 Coin sums) megtervezését, négyféle megoldását és tesztelését foglalta magába.

Bevezetés:

  • Az Egyesült Királyságban 8-féle érme van forgalomban.
  • Ezek a következők (pound (£) és pence (p)): 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p), és £2 (200p).
  • £2-ot például így lehet kifizetni: 1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p.
  • Hányféleképpen lehet kifizetni £2-ot úgy, hogy bármilyen érméből bármennyit felhasználhatunk?
  • A válasz: 73682.

A választ tartalmazó fájl letölthető: it-tanfolyam.hu-brit-ermek-megoldas-eredmeny.zip (377 kB, kicsomagolva 4,2 MB).

Feladatok Java nyelven: készíteni kell négy Java programot, amelyik listázza a lehetséges eseteket a konzolra a példa szerinti formátumban!

  • Az első iteratív megoldás brute force megoldást tartalmazzon! Ez 1473155834 lépésben fog véget érni.
  • A második iteratív megoldás próbálja csökkenteni a lépésszámot! A cél 3000000 alá eljutni, például: 2886726.
  • A harmadik megoldás rekurzív legyen!
  • A negyedik megoldás objektumorientált legyen!

A fokozatosság elvét betartva, sok-sok előismeretre volt szükség a feladatok megoldásához. A két legizgalmasabb rész a hatékonyság szempontjaihoz és a rekurzív megközelítéshez kötődött. Sok-sok kérdés hangzott el. Az i-edik megoldás direkt előállítása (a teljes sorozatból való kiválasztás nélkül) is felmerült. Köszönöm mindenkinek, aki részt vett rendezvényünkön.

A laborgyakorlaton készült forráskódokat tanfolyamaink hallgatói számára – a témához kapcsolódó témakörökhöz, ILIAS-ra feltöltve – tesszük elérhetővé.

Euler állatos feladata

Szerző:
EulerAllat

EulerAllatValaki sertést, kecskét és juhot vásá­rolt, összesen 100 állatot, pontosan 100 aranyért. A sertés darabja 3 és fél arany, a kecskéé 1 és egyharmad, a juhoké fél arany. Hány darabot vehetett az egyes állatokból?

Kezdjük informatikai eszközökkel megoldani a problémát és írjunk Java nyelven forráskódot!

1. megoldás

Klasszikus ötletként teljes leszámolást (brute force) megvalósítva ágyazzunk egymásba három ciklust és léptessük mindhárom változót ( s, k, j) 1-100-ig [//3, //4, //5]!

Így biztosan megkapjuk az összes megoldást, hiszen minden lehetséges értéket behelyettesítünk a feltételvizsgálatnál. A lépésszám 1000000, ami nagyon sok. Próbáljuk fokozatosan csökkenteni a lépésszámot!

2. megoldás

Vegyük figyelembe, hogy mindegyik fajta állatból kell legalább egyet venni, így léptessük a változókat 1-98-ig! Másképpen: ha bármelyik állatból a maximális darabot vennénk (98-at), a másik kettőből még mindig tudjunk venni minimális darabot (1-et, 1-et) [//3, //4, //5].

A lépésszám 941192.

3. megoldás

Vegyük figyelembe, hogy összesen 100 db állatot kell venni, így k legfeljebb 99-s, illetve j legfeljebb 100-s-k lehet [//4, //5]!

A lépésszám 161700.

4. megoldás

Vegyük figyelembe, hogy összesen 100 db aranyat költhetünk! A sertés a legdrágább: ezért s legfeljebb egészrész(100/3,5)=28 darab lehet, hasonlóan k legfeljebb egészrész(100/(4.0/3)-3,5)-s, azaz 71-s lehet [//3, //4].

A lépésszám 90692.

5. megoldás

Következtessünk abból, hogy az arany mérőszáma (100) egész szám: a sertések és juhok ára félre végződik és ezek összege tud lenni egész szám többféleképpen is, így a kecskék számának hárommal oszthatónak kell lennie, mivel csak így tud lenni egész szám a néhányszor négyharmad [//4].

A lépésszám 29439.

6. megoldás

Mivel páros számú állatot kell venni és s+j páros szám, így k-nak is párosnak kell lennie! A hárommal osztható számok közül minden másik páros, azaz hattal is osztható [//4].

A lépésszám 14132.

7. megoldás

Építsük be, hogy s+j legyen páros. [//5].

A lépésszám 7130.

8. megoldás

Ha s és k ismert, akkor j könnyen adódik 100-s-k-ként és nem kell rá ciklust szervezni. [//5].

A lépésszám 252.

Akinek még van kedve tovább próbálkozva csökkenteni a lépésszámot, íme néhány ötlet:

  • Az s maximális értéke könnyen csökkenthető 16-ra, ekkor a k legfeljebb 60-3*s és j adódik, így egyszerűsíthető lehet a 6*s+5.0/3*k==100 feltétel, valamint az eredmény kiírásánál j helyett 100-s-k. Ekkor a lépésszám 88.
  • Az s osztható öttel, így a ciklusa megszervezhető for(int s=5; s<=15; s+=5)-ként, amivel a lépésszám 14.
  • A k is adódik (100-6*s)*3/5.0-ként és a módosított k==Math.round(k) feltétellel a lépésszám 3.

Próbálkozhatunk egy kis matematikával is!

Néhány ötlet:

  • Egyszerű műveletekkel könnyen adódik, hogy 21s+8k+3j=600 és j=100-s-k, illetve s<600/21 és k<600/8-21s. Ezeket az összefüggéseket felhasználva is írhatunk programot.
  • Klasszikus diofantoszi (diofantikus) többismeretlenes algebrai egyenletrendszerként is megoldhatjuk a feladatot.
  • Egyebek: következtetés, kizárás, egyenlőtlenségek, becslések, kongruencia, szorzattá (hatvánnyá) alakítás, illetve az sem rossz ötlet, hogy „ránézek és kész”.

Végül a feladat megoldásai

5 db sertés és 42 db kecske és 53 db juh
10 db sertés és 24 db kecske és 66 db juh
15 db sertés és 6 db kecske és 79 db juh

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

Ez a feladat a Java SE szoftverfejlesztő tanfolyam szakmai moduljának 5-8. óra: Vezérlési szerkezetek, illetve 9-12. óra: Metódusok, rekurzió alkalmához, valamint minden tanfolyamunk orientáló moduljának 1-4. óra: Programozási tételek alkalmához kapcsolódik.