Euler állatos feladata

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

1
2
3
4
5
6
7
8
9
10
  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].

1
2
3
4
5
6
7
8
9
10
  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]!

1
2
3
4
5
6
7
8
9
10
  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].

1
2
3
4
5
6
7
8
9
10
  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].

1
2
3
4
5
6
7
8
9
10
  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].

1
2
3
4
5
6
7
8
9
10
  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].

1
2
3
4
5
6
7
8
9
10
  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].

1
2
3
4
5
6
7
8
9
10
  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.