hatékonyság Archives - it-tanfolyam.hu

Péntek 13

Sokan szerencsés vagy balszerencsés napnak tartják a péntek tizenharmadikát. Évente 1-2-3 alkalommal megtörténik, hogy a hónap 13. napja péntekre esik (minden vasárnap kezdődő hónapban). A hónap 13. napja valamivel valószínűbben péntekre esik, mint a hét bármely más napja. Átlagosan 212,35 naponként fordul elő péntek 13. Előfordulhat két egymást követő hónapban is, de akár 14 hónap is eltelhet két péntek 13 között.

A nap említése sok helyen előfordult: regényekben, filmekben, híres emberek születése vagy halála is esett péntek 13-ra. Átlag alatti közlekedési baleset szokott előfordulni ezeken a napokon – talán mert az emberek óvatosabbak. Kimutatható összefüggést/korrelációt, „péntek 13 hatást” figyeltek meg a tőzsdén is.

Hasznos lehet, ha írunk egy Java programot, amely néhány egymást követő év esetén listázza a konzolra azokat a hónapokat, amikor 13-a péntekre esik.

Tervezés

Legyen egy listFriday13(year) eljárás, amely a paraméterként átvett évben kiírja azokat a hónapokat a konzolra, amelyekben 13-a péntekre esett/esik. Például: 2019: szeptember, december. A hónapok nevei magyar nyelven jelenjenek meg. Az adott év hónapjain végighaladó ciklus legyen hatékony. Optimalizáljunk a ciklus lépésszámára! A ciklus álljon le, ha már talált 3 hónapot (mivel nem lehet több).

1. megoldás

A megoldást a tematika Tömbök témakörében az alábbiak szerint készíthetjük el. Előismeretek: változók, operátorok, ciklusok, programozási tételek, metódusok, tömbök, String összehasonlítás. Az ismert öröknaptár algoritmusokból implementáljuk az egyiket, például:

  static boolean isLeapYear(int year) {
    return (year>=1582) &&
           ((year%4==0 && year%100!=0) || (year%400==0));
  }

  public static String dayOfWeek(int year, int month, int day) {
    int centuryCode=2*(3-year/100%4);
    int yearOfCentury=year%100;
    int monthCode=new int[] {-1,
      isLeapYear(year)?6:0, isLeapYear(year)?2:3, 3, 6,
      1, 4, 6, 2,
      5, 0, 3, 5
    }[month];
    int dayCode=(centuryCode+yearOfCentury+
        yearOfCentury/4+monthCode+day)%7;
    return new String[] {
      "Sunday", "Monday", "Tuesday", "Wednesday",
      "Thursday", "Friday", "Saturday"
    }[dayCode];
  }
  
  public static void listFriday13v1(int year) {
    String[] months={"",
      "január", "február", "március", "április",
      "május", "június", "július", "augusztus",
      "szeptember", "október", "november", "december"};
    System.out.print(year+": ");
    for(int month=1, count=1; month<=12 && count<=3; month++) {
      if(dayOfWeek(year, month, 13).equals("Friday")) {
        System.out.print(months[month]+", ");
        count++;
      }
    }
    System.out.println();
  }

static boolean isLeapYear(int year) {

return (year>=1582) &&

((year%4==0 && year%100!=0) || (year%400==0));

}

public static String dayOfWeek(int year, int month, int day) {

int centuryCode=2*(3-year/100%4);

int yearOfCentury=year%100;

int monthCode=new int[] {-1,

isLeapYear(year)?6:0, isLeapYear(year)?2:3, 3, 6,

1, 4, 6, 2,

5, 0, 3, 5

}[month];

int dayCode=(centuryCode+yearOfCentury+

yearOfCentury/4+monthCode+day)%7;

return new String[] {

"Sunday", "Monday", "Tuesday", "Wednesday",

"Thursday", "Friday", "Saturday"

}[dayCode];

}

public static void listFriday13v1(int year) {

String[] months={"",

"január", "február", "március", "április",

"május", "június", "július", "augusztus",

"szeptember", "október", "november", "december"};

System.out.print(year+": ");

for(int month=1, count=1; month<=12 && count<=3; month++) {

if(dayOfWeek(year, month, 13).equals("Friday")) {

System.out.print(months[month]+", ");

count++;

}

System.out.println();

}

A listFriday13v1(year) eljárásban az elemi döntés egyszerű: dayOfWeek(year, month, 13).equals("Friday"). Épít az öröknaptárt megvalósító – saját – szöveget visszaadó függvényre. A függvény az algoritmus szerinti kódok előállításához ( centuryCode, monthCode, dayCode) felhasználja a szökőév ( isLeapYear(year)) függvényt, valamint két – konstansnak is tekinthető – névtelen tömböt ( new int[], new String[]).

2. megoldás

A megoldást a tematikában Objektumorientált programozás témakörében az alábbiak szerint készíthetjük el. Felhasználjuk eddigi ismereteinket és a JDK beépített dátumkezelő (tároló, formázó) funkcióit (osztályok, interfészek, konstansok, felsorolások).

  public static void listFriday13v2(int year) {
    SimpleDateFormat dfMonth=
      new SimpleDateFormat("MMMM", new Locale("hu"));
    ArrayList<String> listMonths=new ArrayList<>();
    for(int month=1, count=1; month<=12 && count<=3; month++) {
      GregorianCalendar date=new GregorianCalendar(year, month-1, 13);
      if(date.get(Calendar.DAY_OF_WEEK)==Calendar.FRIDAY) {
        listMonths.add(dfMonth.format(date.getTime()));
        count++;
      }
    }
    System.out.println(year+": "+String.join(", ", listMonths));
  }

public static void listFriday13v2(int year) {

SimpleDateFormat dfMonth=

new SimpleDateFormat("MMMM", new Locale("hu"));

ArrayList<String> listMonths=new ArrayList<>();

for(int month=1, count=1; month<=12 && count<=3; month++) {

GregorianCalendar date=new GregorianCalendar(year, month-1, 13);

if(date.get(Calendar.DAY_OF_WEEK)==Calendar.FRIDAY) {

listMonths.add(dfMonth.format(date.getTime()));

count++;

}

System.out.println(year+": "+String.join(", ", listMonths));

}

A listFriday13v2(year) eljárás a Calendar absztrakt osztály konstansait használja fel az elemi döntéshez: date.get(Calendar.DAY_OF_WEEK)==Calendar.FRIDAY. A dátumot a GregorianCalendar konstruktora példányosítja és figyelni kell a 0-bázisú hónapkezelésre. A dátum formázása során ( dfMonth) beállítjuk a megfelelően paraméterezett ( "hu") Locale típusú objektumot és a hónap hosszú nevét kérjük ( "MMMM"). A metódus generikus listába gyűjti a kiválasztott hónapok nevét, amiket végül a String.join() függvény fűz össze a megjelenítéshez.

Eredmény

A vezérlésben egy ciklus 2019-től 2038-ig szervezve az alábbi eredményt adja:

Péntek 13 előfordulások
2019: szeptember, december
2020: március, november
2021: augusztus
2022: május
2023: január, október
2024: szeptember, december
2025: június
2026: február, március, november
2027: augusztus
2028: október
2029: április, július
2030: szeptember, december
2031: június
2032: február, augusztus
2033: május
2034: január, október
2035: április, július
2036: június
2037: február, március, november
2038: augusztus

Péntek 13 előfordulások

2019: szeptember, december

2020: március, november

2021: augusztus

2022: május

2023: január, október

2024: szeptember, december

2025: június

2026: február, március, november

2027: augusztus

2028: október

2029: április, július

2030: szeptember, december

2031: június

2032: február, augusztus

2033: május

2034: január, október

2035: április, július

2036: június

2037: február, március, november

2038: augusztus

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 tematikájához kötődik a fentiek szerint: 13-16. óra: Tömbök alkalom, illetve 17-28. óra: Objektumorientált programozás alkalom.

Nemzetközi Pi nap

Szerző: Kaczur Sándor

A Pi-t ( $π$ ) mindenki ismeri. Talán sokaknak kedvenc története is van a $π$ -vel kapcsolatosan, amelyet iskolában vagy utazásai alatt szerzett. A $π$ Euklidesz geometriájában a kör kerületének és átmérőjének arányát jelöli. A $π$ irracionális szám, azaz végtelen, nem szakaszos tizedestört; másképpen számjegyei között nincs ismétlődés. A $π$ értékével a hétköznapokban 3,14-dal szokás számolni, de a tudomány területén ennél sokkal pontosabb közelítést szokás alkalmazni. A $π$ közelítése az informatikának köszönhetően akár több millió tizedesjegyig is lehetséges (például: S. Memphill: Pi to 1,000,000 places).

A nemzetközi Pi nap alkalmából (március 14) megvalósítottunk néhány – végtelen összeggel és szorzattal – $π$ közelítésre való képletet, algoritmust Java nyelven.

1. Viète-féle sor

  private static void megold1() { //Viète-féle sor
    double p=1, pi=1;
    for(int i=11; i>1; i--) {
      p=2;
      for(int j=1; j<i; j++)
        p=2+Math.sqrt(p);
      p=Math.sqrt(p);
      pi=pi*p/2;
    }
    pi*=Math.sqrt(2)/2;
    pi=2/pi;
    System.out.println(pi);
  }

private static void megold1() { //Viète-féle sor

double p=1, pi=1;

for(int i=11; i>1; i--) {

p=2;

for(int j=1; j<i; j++)

p=2+Math.sqrt(p);

p=Math.sqrt(p);

pi=pi*p/2;

}

pi*=Math.sqrt(2)/2;

pi=2/pi;

System.out.println(pi);

}

A módszer néhány eredménye: i=5 esetén 3.140331156954752 (2 tizedesjegyre pontos), i=10 -nél 3.1415914215112 (5 tizedesjegyre pontos), i=11 esetén 3.1415923455701176 (6 tizedesjegyre pontos).

2. Leibniz-féle sor

  public static void megold2() { //Leibniz-féle sor
    double s=0;
    for (int i=0; i<=2500; i++)
      s+=Math.pow(-1, i)/(2*i+1);
    double pi=s*4;
    System.out.println(pi);
  }

public static void megold2() { //Leibniz-féle sor

double s=0;

for (int i=0; i<=2500; i++)

s+=Math.pow(-1, i)/(2*i+1);

double pi=s*4;

System.out.println(pi);

}

A módszer néhány eredménye: a 24. lépéstől stabil 1 tizedesjegyre, a 626. lépéstől stabil 2. tizedesjegyre, a 2453. lépéstől stabil 3 tizedesjegyre (hiszen alternál).

3. Wallis-formula

  public static void megold3() { //Wallis-formula
    double p=1;
    for (int i=2; i<=17000; i+=2)
      p*=(1.0*i/(i-1)*(1.0*i/(i+1)));
    double pi=p*2;
    System.out.println(pi);
  }

public static void megold3() { //Wallis-formula

double p=1;

for (int i=2; i<=17000; i+=2)

p*=(1.0*i/(i-1)*(1.0*i/(i+1)));

double pi=p*2;

System.out.println(pi);

}

A módszer néhány eredménye: A 38. lépéstől 1, a 986. lépéstől 2, a 2650. lépéstől 3, a 16954. lépéstől már 4 tizedesjegyre pontos.

4. Csebisev-sor

  private static void megold8() { //Csebisev-sor, V1
    double s=0;
    for (int k=0; k<=20; k++)
      s+=(Math.pow(-1, k)*Math.pow(Math.sqrt(2)-1, 2*k+1))/(2*k+1);
    double pi=s*8;
    System.out.println(pi);
  }

private static void megold8() { //Csebisev-sor, V1

double s=0;

for (int k=0; k<=20; k++)

s+=(Math.pow(-1, k)*Math.pow(Math.sqrt(2)-1, 2*k+1))/(2*k+1);

double pi=s*8;

System.out.println(pi);

}

A módszer k=10 -re már 8 tizedesjegyig pontos.

A bejegyzéshez tartozó teljes forráskódot – további 8 közelítő módszer implementációjával együtt – 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 5-8. óra: Vezérlési szerkezetek alkalmához kötődik.

Barátságos számpárok

Szerző: Kaczur Sándor

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.

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+")");
}

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

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+")");  
}

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.

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

private static void baratsagosSzamparok3() {

System.out.println("Barátságos számpárok 1-től 10000-ig:");

for(int i=200; i<=100000; 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:

Wikipédia – Barátságos számok
Wikipedia – Amicable numbers
www.mathe.tu-freiberg.de – Vollkommene, befreundete und gesellige Zahlen
gorbem.hu – Barátságok számok
Hasonló feladat: https://projecteuler.net/problem=21 és megoldás: http://code.jasonbhill.com/c/project-euler-problem-21/

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

CHOO + CHOO = TRAIN

Szerző: Kaczur Sándor

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");
}

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 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();
              }
}

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:

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.

Euler állatos feladata

Szerző: Kaczur Sándor

Valaki 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]!

private static void megold1() {
  db=0;
  for(int s=1; s<=100; s++)
    for(int k=1; k<=100; k++)
      for(int j=1; j<=100; j++) {
        db++;
        if(3.5*s+4.0/3*k+0.5*j==100 && s+k+j==100)
          System.out.println(s+" db sertés és "+k+" db kecske és "+j+" db juh");
      }    
}

private static void megold1() {

db=0;

for(int s=1; s<=100; s++)

for(int k=1; k<=100; k++)

for(int j=1; j<=100; j++) {

db++;

if(3.5*s+4.0/3*k+0.5*j==100 && s+k+j==100)

System.out.println(s+" db sertés és "+k+" db kecske és "+j+" db juh");

}

Í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].

private static void megold2() {
  db=0;
  for(int s=1; s<=98; s++)
    for(int k=1; k<=98; k++)
      for(int j=1; j<=98; j++) {
        db++;
        if(3.5*s+4.0/3*k+0.5*j==100 && s+k+j==100)
          System.out.println(s+" db sertés és "+k+" db kecske és "+j+" db juh");
      }    
}

private static void megold2() {

db=0;

for(int s=1; s<=98; s++)

for(int k=1; k<=98; k++)

for(int j=1; j<=98; j++) {

db++;

if(3.5*s+4.0/3*k+0.5*j==100 && s+k+j==100)

System.out.println(s+" db sertés és "+k+" db kecske és "+j+" db juh");

}

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]!

private static void megold3() {
  db=0;
  for(int s=1; s<=98; s++)
    for(int k=1; k<=99-s; k++)
      for(int j=1; j<=100-s-k; j++) {
        db++;
        if(3.5*s+4.0/3*k+0.5*j==100 && s+k+j==100)
          System.out.println(s+" db sertés és "+k+" db kecske és "+j+" db juh");
      }    
}

private static void megold3() {

db=0;

for(int s=1; s<=98; s++)

for(int k=1; k<=99-s; k++)

for(int j=1; j<=100-s-k; j++) {

db++;

if(3.5*s+4.0/3*k+0.5*j==100 && s+k+j==100)

System.out.println(s+" db sertés és "+k+" db kecske és "+j+" db juh");

}

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

private static void megold4() {
  db=0;
  for(int s=1; s<=28; s++)
    for(int k=1; k<=71-s; k++)
      for(int j=1; j<=100-s-k; j++) {
        db++;
        if(3.5*s+4.0/3*k+0.5*j==100 && s+k+j==100)
          System.out.println(s+" db sertés és "+k+" db kecske és "+j+" db juh");
      }    
}

private static void megold4() {

db=0;

for(int s=1; s<=28; s++)

for(int k=1; k<=71-s; k++)

for(int j=1; j<=100-s-k; j++) {

db++;

if(3.5*s+4.0/3*k+0.5*j==100 && s+k+j==100)

System.out.println(s+" db sertés és "+k+" db kecske és "+j+" db juh");

}

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

private static void megold5() {
  db=0;
  for(int s=1; s<=28; s++)
    for(int k=3; k<=71-s; k+=3)
      for(int j=1; j<=100-s-k; j++) {
        db++;
        if(3.5*s+4.0/3*k+0.5*j==100 && s+k+j==100)
          System.out.println(s+" db sertés és "+k+" db kecske és "+j+" db juh");
      }    
}

private static void megold5() {

db=0;

for(int s=1; s<=28; s++)

for(int k=3; k<=71-s; k+=3)

for(int j=1; j<=100-s-k; j++) {

db++;

if(3.5*s+4.0/3*k+0.5*j==100 && s+k+j==100)

System.out.println(s+" db sertés és "+k+" db kecske és "+j+" db juh");

}

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

private static void megold6() {
  db=0;
  for(int s=1; s<=28; s++)
    for(int k=6; k<=71-s; k+=6)
      for(int j=1; j<=100-s-k; j++) {
        db++;
        if(3.5*s+4.0/3*k+0.5*j==100 && s+k+j==100)
          System.out.println(s+" db sertés és "+k+" db kecske és "+j+" db juh");
      }    
}

private static void megold6() {

db=0;

for(int s=1; s<=28; s++)

for(int k=6; k<=71-s; k+=6)

for(int j=1; j<=100-s-k; j++) {

db++;

if(3.5*s+4.0/3*k+0.5*j==100 && s+k+j==100)

System.out.println(s+" db sertés és "+k+" db kecske és "+j+" db juh");

}

A lépésszám 14132.

7. megoldás

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

private static void megold7() {
  db=0;
  for(int s=1; s<=28; s++)
    for(int k=6; k<=71-s; k+=6)
      for(int j=(s%2==0?2:1); j<=100-s-k; j+=2) {
        db++;
        if(3.5*s+4.0/3*k+0.5*j==100 && s+k+j==100)
          System.out.println(s+" db sertés és "+k+" db kecske és "+j+" db juh");
      }    
}

private static void megold7() {

db=0;

for(int s=1; s<=28; s++)

for(int k=6; k<=71-s; k+=6)

for(int j=(s%2==0?2:1); j<=100-s-k; j+=2) {

db++;

if(3.5*s+4.0/3*k+0.5*j==100 && s+k+j==100)

System.out.println(s+" db sertés és "+k+" db kecske és "+j+" db juh");

}

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

private static void megold8() {
  db=0;
  for(int s=1; s<=28; s++)
    for(int k=6; k<=71-s; k+=6) {
      int j=100-s-k;
      db++;
      if(3.5*s+4.0/3*k+0.5*j==100 && s+k+j==100)
        System.out.println(s+" db sertés és "+k+" db kecske és "+j+" db juh");   
    }
}

private static void megold8() {

db=0;

for(int s=1; s<=28; s++)

for(int k=6; k<=71-s; k+=6) {

int j=100-s-k;

db++;

if(3.5*s+4.0/3*k+0.5*j==100 && s+k+j==100)

System.out.println(s+" db sertés és "+k+" db kecske és "+j+" db juh");

}

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.