Euler - címke - it-tanfolyam.hu

Euler állatos feladata – geometriai megközelítés

2024. szeptember 2. 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?

Tudjuk, hogy a feladatnak három megoldása van:

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

Klasszikus informatikai megközelítést – egymásba ágyazott ciklusokat – bemutattam már: Euler állatos feladata. A brute force alapgondolat fokozatos finomítását követően néhány ötleteket is adtam a továbbfejlesztéshez. Ez igazi örökzöld feladat. Látogatottsága alapján rendületlenül népszerű ez a blog bejegyzés az it-tanfolyam.hu szakmai blogban. Többek között ez inspirált a feladattal való további foglalkozásra.

Mit jelent a geometriai megközelítés?

Egy térbeli pont három koordinátával leírható. Az (s, k, j) ponthármas jelenti a sertések, kecskék és juhok számát. Az RGB színkockához hasonlóan (amibe belefér az összes ábrázolható színhez tartozó koordinátapont), most is elférünk egy kockában. Legyen a kocka egyik csúcsa az origó és az élei legyenek 100 egység hosszúak. A feladat megfogalmazása alapján két egyenlet (e1 és e2) írható fel 3-3 együtthatóval. Mindkét egyenlet meghatároz egy síkot (s1 és s2) a térben, amelynek ábrázoljuk a kockába eső síkmetszeteit. A két sík metszésvonala egyenes (e3), amire esnek a megoldások pontjai (m1, m2, m3). Lépésenként haladunk a geometriai ábrázolás során.

A grafikus felületen történő ábrázoláshoz, rajzoláshoz két korábbi projektünkből indulunk ki. A Kígyókocka grafikus felületen feladat ismertet egy grafikus keretrendszert JavaFX-ben megvalósítva. A három részből álló Naprendszer szimuláció esettanulmányunk pedig ismerteti az ábrázoláshoz szükséges elméleti hátteret, homogén transzformációkat, vetületi leképezést, Java forráskódot is bemutat a transzformációs mátrix alkalmazására. Az eddig említett három blog bejegyzést mind összeépítve készültek a továbbiak.

A geometriai megoldást lépésenként, saját fejlesztésű, grafikus felhasználói felülettel rendelkező, JavaFX alapú programról készült képernyőképek mutatják be – markáns Java forráskód-részletekkel.

Hogy jelenik meg a megoldásokat tartalmazó kocka?

Elegendő ábrázolni a kockának azt a három élét, amik egybeesnek a koordinátatengelyekkel. Az RGB színkockához hasonlóan piros, zöld, kék színekkel jelennek meg a három tengelyen lévő néhány pont. Az ábrázoláshoz érdemes kísérletezni egy kicsit: mekkora méretben (skála), honnan (nézőpont), milyen messziről (vetület, ideális pont, perspektíva, távolság) látszik a modelltérbeli objektum (igen, ez a kocka).

Az alábbi Java forráskód-részlet helyezi el a fenti pontokat. Mindhárom tengelyen 5-től 95-ig, 10-esével haladunk. Így elkerülhető, hogy az origóba kerüljön pont, hiszen az nem tudna egyszerre három színnel megjelenni. Mivel az állatok száma pozitív, így a koordinátapontok is nemnegatívak.

for(int i=5; i<=100; i+=10) {

Point3D cpS=new Point3D(i, 0, 0); //sertés

createPoint(cpS, 5, Color.RED);

Point3D cpK=new Point3D(0, i, 0); //kecske

createPoint(cpK, 5, Color.GREEN);

Point3D cpJ=new Point3D(0, 0, i); //juh

createPoint(cpJ, 5, Color.BLUE);

}

Hol vannak az első egyenlet síkjának pontjai?

A korábbi megoldásnál feltételként megfogalmazott első 3.5*s+4.0/3*k+0.5*j==100 egyenlet egyszerű átalakításokkal megadja a piros és zöld síkbeli ponthoz tartozó kék térbeli pontot: j=(600-21*s-8*k)/3. Ezek az s1 síkra esnek. A citromsárga pontokat páros koordinátapárokra vizsgált feltétel jelöli ki. A narancssárga vonal behatárolja ezt a síkmetszetet. Ez a négyszög (trapéz) esik bele a kockába.

A citromsárga pontokat az első egymásba ágyazott ciklusok adják hozzá az ábrázolt modelltérhez: érzékeltetve a síkbeli pontokat. A narancssárga pontokkal a második egymásba ágyazott ciklusok bővítik a modellteret: behatárolva a kockabeli négyszög síkrészletet. (A trapéz oldalait szakaszként is lehetne ábrázolni, de ez a kellően sűrű ponthalmaz is elegendő).

for(int s=0; s<=100; s+=2)

for(int k=0; k<=100; k+=2) {

int j=(600-21*s-8*k)/3;

if(0<=j && j<=100) {

Point3D cpE1=new Point3D(s, k, j);

createPoint(cpE1, 3, Color.YELLOW);

}

for(double s=0; s<=100; s+=0.1)

for(double k=0; k<=100; k+=0.1) {

long j=Math.round((600-21*s-8*k)/3);

if(((s==0 || s==100) && 0<=j && j<=100) ||

((k==0 || k==100) && 0<=j && j<=100) ||

(j==0 || j==100)) {

Point3D cpE1=new Point3D(s, k, j);

createPoint(cpE1, 2, Color.ORANGE);

}

Hol vannak a második egyenlet síkjának pontjai?

Hasonlóan az eddigiekhez. A korábbi s+k+j==100 feltételből adódik a szintén feltételként megfogalmazott j==100-s-k egyenlet. Ezek az s2 síkra esnek. Világosszürke pontok érzékeltetik a síkot és sötétszürke pontok adják a síkrészlet határait. A síkból ez a háromszög esik bele a kockába.

A Java forráskód nagyon hasonló az előzőhöz.

Hogyan helyezkedik el a két sík a kockában?

Egyben kirajzoltatva a fentieket, könnyen adódik ez az ábra:

Hol van a két sík metszésvonala?

Mivel a két sík nem esik egybe, így van metszésvonaluk. Ez egy egyenes, amiből csak az az e3 szakasz rész szükséges, ami a kockába esik. Bíbor (magenta) szín jelöli az alábbi ábrán:

Ahol a két egyenlethez tartozó konkrét pontok egybeesnek, ott van a metszésvonal. A behelyettesítést behatároló ciklusok szervezéséből (a ciklusváltozók alsó és felső és határaiból) adódik, hogy csak a kockabeli szakaszt rajzolja ki az alábbi Java forráskód-részlet:

for(double s=0; s<=100; s+=0.1)

for(double k=0; k<=100; k+=0.1) {

long j1=Math.round((600-21*s-8*k)/3);

long j2=Math.round(100-s-k);

if(j1==j2) {

Point3D cpE1=new Point3D(s, k, j1);

createPoint(cpE1, 2, Color.MAGENTA);

}

Hol jelenik meg a feladat három megoldása?

A két egyenlethez tartozó síkok kockába eső metszésvonalán helyezkednek el az egész koordinátákkal ábrázolható, koordináta-hármasként megjelenő pontok. Nagyobb fehér pontok jelölik ezeket az alábbi ábrán:

Az eddigiek alapján könnyen adódik a három pont/megoldást ábrázoló Java forráskód-részlet:

Point3D m1=new Point3D(5, 42, 53);

createPoint(m1, 10, Color.WHITE);

Point3D m2=new Point3D(10, 24, 66);

createPoint(m2, 10, Color.WHITE);

Point3D m3=new Point3D(15, 6, 79);

createPoint(m3, 10, Color.WHITE);

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, a 29-36. óra Grafikus felhasználói felület alkalmaihoz, valamint minden tanfolyamunk orientáló moduljának 1-4. óra: Programozási tételek alkalmához kapcsolódik.

Tanfolyamainkon JavaFX grafikus felülettel hangsúlyosan nem foglalkozunk, de egy-egy kész forráskódot közösen megbeszélünk, és össze is hasonlítjuk a swing-es változattal. Fejlesztünk játékprogramot, de inkább konzolosan, vagy swing-es ablakban, vagy webes alkalmazásként.

A grafikus felületek felépítésének megismerése fontos lépcső az objektumorientált programozás elmélyítéséhez, gyakorlásához. A grafikus felületekhez egy másik lényeges szemléletváltás is kapcsolódik, hiszen a korábbi algoritmusvezérelt megközelítést felváltja az eseményvezérelt (eseménykezelés). A GUI-s feladatainkat tudatosan hangsúlyozott MVC-s projektekben készítjük el.

Barátságos számok

2023. augusztus 15.2018. július 19. Szerző: Balogh Péter

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

}

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

}

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<=10000; i++) {

int j=osztokOsszege2(i);

if(j>i && osztokOsszege2(j)==i)

System.out.println("("+i+"; "+j+")");

}

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

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.

Digitális Témahét 2017

2023. március 20.2017. április 7. Szerző: Kaczur Sándor

A Digitális Témahét 2016-ban indult országos rendezvénysorozat. Fő célja a digitális pedagógia módszertanának népszerűsítése és elterjesztése. A program fontos törekvése, hogy a digitáliskompetencia-fejlesztés az informatikán túl kiterjedjen más tantárgyakra is. A résztvevő pedagógusok és diákok változatos és kreatív iskolai projektek keretében fejleszthetik képességeiket technológiával támogatott tanulás során. A Digitális Témahét rendezvény minden meghirdetett programja ingyenes.

A 2016/2017-es tanévben a rendezvény április 3-7. között valósult meg. Kiemelt témakörök/szempontok:

a multidiszciplináris megközelítés: a matematika, a természet- és mérnöki tudományok, valamint a művészet- és társadalomtudományok együttes megjelenítése;
a tanítás eszközkészletének és módszereinek megújítása;
a pedagógiai innováció, a digitális pedagógia ösztönzése;
az informatikai pályaorientáció.

Meghirdetett eseményünk

2017-ben egy eseményt hirdettem meg Digitális Témahét 2017 rendezvényen.
Helyszín: 1056 Budapest, Váci utca 47., 3. emelet 309-es terem, megközelítés
Dátum és időpont: 2017. április 7. 18:00-21:00-ig
Az esemény ingyenes volt, de a részvétel előzetes regisztrációhoz kötött.

A három órás laborgyakorlat a Brit érmék projektfeladat (forrás: Project Euler #31 Coin sums) megtervezését, négyféle megoldását és tesztelését foglalta magába.

Bevezetés:

Az Egyesült Királyságban 8-féle érme van forgalomban.
Ezek a következők (pound (£) és pence (p)): 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p), és £2 (200p).
£2-ot például így lehet kifizetni: 1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p.
Hányféleképpen lehet kifizetni £2-ot úgy, hogy bármilyen érméből bármennyit felhasználhatunk?
A válasz: 73682.

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

1. megoldás: 1×£2

2. megoldás: 2×£1

3. megoldás: 1×£1 + 2×50p

4. megoldás: 4×50p

5. megoldás: 1×£1 + 5×20p

6. megoldás: 2×50p + 5×20p

7. megoldás: 10×20p

8. megoldás: 1×£1 + 1×50p + 2×20p + 1×10p

9. megoldás: 3×50p + 2×20p + 1×10p

10. megoldás: 1×50p + 7×20p + 1×10p

11. megoldás: 1×£1 + 4×20p + 2×10p

12. megoldás: 2×50p + 4×20p + 2×10p

13. megoldás: 9×20p + 2×10p

14. megoldás: 1×£1 + 1×50p + 1×20p + 3×10p

15. megoldás: 3×50p + 1×20p + 3×10p

16. megoldás: 1×50p + 6×20p + 3×10p

17. megoldás: 1×£1 + 3×20p + 4×10p

18. megoldás: 2×50p + 3×20p + 4×10p

19. megoldás: 8×20p + 4×10p

20. megoldás: 1×£1 + 1×50p + 5×10p

21. megoldás: 3×50p + 5×10p

22. megoldás: 1×50p + 5×20p + 5×10p

23. megoldás: 1×£1 + 2×20p + 6×10p

24. megoldás: 2×50p + 2×20p + 6×10p

25. megoldás: 7×20p + 6×10p

26. megoldás: 1×50p + 4×20p + 7×10p

27. megoldás: 1×£1 + 1×20p + 8×10p

28. megoldás: 2×50p + 1×20p + 8×10p

29. megoldás: 6×20p + 8×10p

30. megoldás: 1×50p + 3×20p + 9×10p

31. megoldás: 1×£1 + 10×10p

32. megoldás: 2×50p + 10×10p

33. megoldás: 5×20p + 10×10p

34. megoldás: 1×50p + 2×20p + 11×10p

35. megoldás: 4×20p + 12×10p

36. megoldás: 1×50p + 1×20p + 13×10p

37. megoldás: 3×20p + 14×10p

38. megoldás: 1×50p + 15×10p

39. megoldás: 2×20p + 16×10p

40. megoldás: 1×20p + 18×10p

41. megoldás: 20×10p

42. megoldás: 1×£1 + 1×50p + 2×20p + 2×5p

43. megoldás: 3×50p + 2×20p + 2×5p

44. megoldás: 1×50p + 7×20p + 2×5p

45. megoldás: 1×£1 + 4×20p + 1×10p + 2×5p

46. megoldás: 2×50p + 4×20p + 1×10p + 2×5p

47. megoldás: 9×20p + 1×10p + 2×5p

48. megoldás: 1×£1 + 1×50p + 1×20p + 2×10p + 2×5p

49. megoldás: 3×50p + 1×20p + 2×10p + 2×5p

50. megoldás: 1×50p + 6×20p + 2×10p + 2×5p

51. megoldás: 1×£1 + 3×20p + 3×10p + 2×5p

52. megoldás: 2×50p + 3×20p + 3×10p + 2×5p

53. megoldás: 8×20p + 3×10p + 2×5p

54. megoldás: 1×£1 + 1×50p + 4×10p + 2×5p

55. megoldás: 3×50p + 4×10p + 2×5p

56. megoldás: 1×50p + 5×20p + 4×10p + 2×5p

57. megoldás: 1×£1 + 2×20p + 5×10p + 2×5p

58. megoldás: 2×50p + 2×20p + 5×10p + 2×5p

59. megoldás: 7×20p + 5×10p + 2×5p

60. megoldás: 1×50p + 4×20p + 6×10p + 2×5p

61. megoldás: 1×£1 + 1×20p + 7×10p + 2×5p

62. megoldás: 2×50p + 1×20p + 7×10p + 2×5p

63. megoldás: 6×20p + 7×10p + 2×5p

64. megoldás: 1×50p + 3×20p + 8×10p + 2×5p

65. megoldás: 1×£1 + 9×10p + 2×5p

66. megoldás: 2×50p + 9×10p + 2×5p

67. megoldás: 5×20p + 9×10p + 2×5p

68. megoldás: 1×50p + 2×20p + 10×10p + 2×5p

69. megoldás: 4×20p + 11×10p + 2×5p

70. megoldás: 1×50p + 1×20p + 12×10p + 2×5p

71. megoldás: 3×20p + 13×10p + 2×5p

72. megoldás: 1×50p + 14×10p + 2×5p

73. megoldás: 2×20p + 15×10p + 2×5p

74. megoldás: 1×20p + 17×10p + 2×5p

75. megoldás: 19×10p + 2×5p

76. megoldás: 1×£1 + 4×20p + 4×5p

77. megoldás: 2×50p + 4×20p + 4×5p

78. megoldás: 9×20p + 4×5p

79. megoldás: 1×£1 + 1×50p + 1×20p + 1×10p + 4×5p

80. megoldás: 3×50p + 1×20p + 1×10p + 4×5p

81. megoldás: 1×50p + 6×20p + 1×10p + 4×5p

82. megoldás: 1×£1 + 3×20p + 2×10p + 4×5p

83. megoldás: 2×50p + 3×20p + 2×10p + 4×5p

84. megoldás: 8×20p + 2×10p + 4×5p

85. megoldás: 1×£1 + 1×50p + 3×10p + 4×5p

86. megoldás: 3×50p + 3×10p + 4×5p

87. megoldás: 1×50p + 5×20p + 3×10p + 4×5p

88. megoldás: 1×£1 + 2×20p + 4×10p + 4×5p

89. megoldás: 2×50p + 2×20p + 4×10p + 4×5p

90. megoldás: 7×20p + 4×10p + 4×5p

91. megoldás: 1×50p + 4×20p + 5×10p + 4×5p

92. megoldás: 1×£1 + 1×20p + 6×10p + 4×5p

93. megoldás: 2×50p + 1×20p + 6×10p + 4×5p

94. megoldás: 6×20p + 6×10p + 4×5p

95. megoldás: 1×50p + 3×20p + 7×10p + 4×5p

96. megoldás: 1×£1 + 8×10p + 4×5p

97. megoldás: 2×50p + 8×10p + 4×5p

98. megoldás: 5×20p + 8×10p + 4×5p

99. megoldás: 1×50p + 2×20p + 9×10p + 4×5p

100. megoldás: 4×20p + 10×10p + 4×5p

101. megoldás: 1×50p + 1×20p + 11×10p + 4×5p

102. megoldás: 3×20p + 12×10p + 4×5p

103. megoldás: 1×50p + 13×10p + 4×5p

104. megoldás: 2×20p + 14×10p + 4×5p

105. megoldás: 1×20p + 16×10p + 4×5p

106. megoldás: 18×10p + 4×5p

107. megoldás: 1×£1 + 1×50p + 1×20p + 6×5p

108. megoldás: 3×50p + 1×20p + 6×5p

109. megoldás: 1×50p + 6×20p + 6×5p

110. megoldás: 1×£1 + 3×20p + 1×10p + 6×5p

...

1000. megoldás: 7×20p + 4×5p + 20×2p

1001. megoldás: 1×50p + 4×20p + 1×10p + 4×5p + 20×2p

1002. megoldás: 1×£1 + 1×20p + 2×10p + 4×5p + 20×2p

1003. megoldás: 2×50p + 1×20p + 2×10p + 4×5p + 20×2p

1004. megoldás: 6×20p + 2×10p + 4×5p + 20×2p

1005. megoldás: 1×50p + 3×20p + 3×10p + 4×5p + 20×2p

1006. megoldás: 1×£1 + 4×10p + 4×5p + 20×2p

1007. megoldás: 2×50p + 4×10p + 4×5p + 20×2p

1008. megoldás: 5×20p + 4×10p + 4×5p + 20×2p

1009. megoldás: 1×50p + 2×20p + 5×10p + 4×5p + 20×2p

1010. megoldás: 4×20p + 6×10p + 4×5p + 20×2p

...

10000. megoldás: 1×50p + 1×20p + 4×10p + 10×5p + 17×2p + 6×1p

10001. megoldás: 3×20p + 5×10p + 10×5p + 17×2p + 6×1p

10002. megoldás: 1×50p + 6×10p + 10×5p + 17×2p + 6×1p

10003. megoldás: 2×20p + 7×10p + 10×5p + 17×2p + 6×1p

10004. megoldás: 1×20p + 9×10p + 10×5p + 17×2p + 6×1p

10005. megoldás: 11×10p + 10×5p + 17×2p + 6×1p

10006. megoldás: 1×£1 + 12×5p + 17×2p + 6×1p

10007. megoldás: 2×50p + 12×5p + 17×2p + 6×1p

10008. megoldás: 5×20p + 12×5p + 17×2p + 6×1p

10009. megoldás: 1×50p + 2×20p + 1×10p + 12×5p + 17×2p + 6×1p

10010. megoldás: 4×20p + 2×10p + 12×5p + 17×2p + 6×1p

...

73655. megoldás: 1×10p + 1×5p + 1×2p + 183×1p

73656. megoldás: 3×5p + 1×2p + 183×1p

73657. megoldás: 1×5p + 6×2p + 183×1p

73658. megoldás: 1×10p + 3×2p + 184×1p

73659. megoldás: 2×5p + 3×2p + 184×1p

73660. megoldás: 8×2p + 184×1p

73661. megoldás: 1×10p + 1×5p + 185×1p

73662. megoldás: 3×5p + 185×1p

73663. megoldás: 1×5p + 5×2p + 185×1p

73664. megoldás: 1×10p + 2×2p + 186×1p

73665. megoldás: 2×5p + 2×2p + 186×1p

73666. megoldás: 7×2p + 186×1p

73667. megoldás: 1×5p + 4×2p + 187×1p

73668. megoldás: 1×10p + 1×2p + 188×1p

73669. megoldás: 2×5p + 1×2p + 188×1p

73670. megoldás: 6×2p + 188×1p

73671. megoldás: 1×5p + 3×2p + 189×1p

73672. megoldás: 1×10p + 190×1p

73673. megoldás: 2×5p + 190×1p

73674. megoldás: 5×2p + 190×1p

73675. megoldás: 1×5p + 2×2p + 191×1p

73676. megoldás: 4×2p + 192×1p

73677. megoldás: 1×5p + 1×2p + 193×1p

73678. megoldás: 3×2p + 194×1p

73679. megoldás: 1×5p + 195×1p

73680. megoldás: 2×2p + 196×1p

73681. megoldás: 1×2p + 198×1p

73682. megoldás: 200×1p

A választ tartalmazó fájl letölthető: it-tanfolyam.hu-brit-ermek-megoldas-eredmeny.zip (377 kB, kicsomagolva 4,2 MB).

Feladatok Java nyelven: készíteni kell négy Java programot, amelyik listázza a lehetséges eseteket a konzolra a példa szerinti formátumban!

Az első iteratív megoldás brute force megoldást tartalmazzon! Ez 1473155834 lépésben fog véget érni.
A második iteratív megoldás próbálja csökkenteni a lépésszámot! A cél 3000000 alá eljutni, például: 2886726.
A harmadik megoldás rekurzív legyen!
A negyedik megoldás objektumorientált legyen!

A fokozatosság elvét betartva, sok-sok előismeretre volt szükség a feladatok megoldásához. A két legizgalmasabb rész a hatékonyság szempontjaihoz és a rekurzív megközelítéshez kötődött. Sok-sok kérdés hangzott el. Az i-edik megoldás direkt előállítása (a teljes sorozatból való kiválasztás nélkül) is felmerült. Köszönöm mindenkinek, aki részt vett rendezvényünkön.

A laborgyakorlaton készült forráskódokat tanfolyamaink hallgatói számára – a témához kapcsolódó témakörökhöz, ILIAS-ra feltöltve – tesszük elérhetővé.

Euler állatos feladata

}

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.