objektumorientált programozás - címke - Oldal 20 a 20-ből

Digitális Témahét 2017

2025. június 15.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é.

CHOO + CHOO = TRAIN

2025. június 15.2017. február 5. 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");

}

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