1 blog bejegyzésnél szerepel:
16 db hozzá kapcsolódó címke:
2017 (24), algoritmus (24), brute force (7), fejtörő (7), gamifikáció (27), hatékonyság (18), Java forráskód (42), kollekció (18), lépésszám (8), logikai feladat (10), metódus (18), objektumorientált programozás (51), programozás (70), szakmai modul (67), tesztelés (8), többféle megoldás összehasonlítása (20)
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:
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.
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"); } |
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<Integer> 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?
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.