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.

Szólj hozzá!