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.
Sanyi: tetszett az az öröklődést tartalmazó tesztkörnyezet, amit a feladathoz építettél. A Kutatók éjszakáján mutattad be.
Köszönöm Imre. A hatékonyságra fókuszált a megközelítésem.
Tudom, hogy didaktika, preparált példa, fokozatosság elve, de érdemes ehhez ennyire lépésenként hozzáállni?
Hasznosnak gondolom Vera, de persze lehet nagyobb léptékkel is haladni. Differenciálva előismeretek alapján.
Nekem néha nehéz az összes megoldás megtalálása. Az mindig megvan, hogy van-e megoldás, mi a megoldás. Az többnyire nem merül fel, hogy van-e másik megoldás, van-e még több megoldás, hány megoldás van összesen. A brute force szemléletmódot használva ezek fel sem merülnek. Nagyon jó!!!
Jól látod Vince. Csak arra érdemes vigyázni, hogy észleljük vagy elkerüljük a kombinatorikus robbanást. Rengeteg lépés (idő), sok helyigény (memória, tárhely) esetén már nem hatékony a teljes leszámolás. Még akkor sem, ha egyszerű (alacsony bonyolultságú) az algoritmus/forráskód.
Ajánljuk rendezvényeinket, ahol időről-időre tartunk élményszerű foglalkozásokat, válogatva a logikus gondolkodásra nevelés feladatgyűjteményünkből.
Köszönöm Balázs, kiegészítem a fejtörő címkénkkel.
A feladatot geometriai megközelítésben is megoldottam, íme a három megoldás:
A részletek itt találhatók: Euler állatos feladata – geometriai megközelítés