algoritmus - címke - Oldal 7 a 7-ből

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.

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.

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?

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:

SEND + MORE = MONEY
6 * KAYAK = SPORT
2 * MOST = TOKYO
CROSS + ROADS = DANGER
FORTY + TEN + TEN = SIXTY
mathsisfun.com – Algebra Puzzles
cryptarithms.awardspace.us – Crack-a-Puzzle Online – Puzzles Menu
www.campusgate.co.in – Cryptoarithmetic problem with explanation

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.

Címke: algoritmus

CHOO + CHOO = TRAIN

1. megoldás

2. megoldás