Hány féle képp váltható fel egy 100Ft-os aprópénzre?

Én is akartam írni egyet, de az algoritmust sehogy nem tudtam összehozni.

Mi alapján döntse el a program, hogy az 50,20,20,10 és az 50,20,10,10,10 is helyes? Milyen feltétel alapján érem el, hogy több esetet is vizsgáljon?

Az én programom, bár nem túl elegáns, de 94-et számolt össze véletlen próbálgatással.

1. 50 db 1 + 20 db 1 + 10 db 2 + 5 db 2

2. 50 db 2

3. 10 db 5 + 20 db 2 + 5 db 2

4. 2 db 5 + 10 db 1 + 20 db 1 + 50 db 1 + 5 db 2

5. 50 db 1 + 20 db 2 + 5 db 2

6. 50 db 1 + 10 db 3 + 5 db 4

7. 10 db 3 + 20 db 1 + 50 db 1

8. 10 db 1 + 20 db 2 + 50 db 1

9. 2 db 5 + 20 db 1 + 50 db 1 + 5 db 4

10. 10 db 4 + 20 db 2 + 2 db 5 + 5 db 2

11. 10 db 5 + 50 db 1

12. 10 db 1 + 20 db 4 + 5 db 2

13. 50 db 1 + 10 db 4 + 5 db 2

14. 10 db 7 + 20 db 1 + 5 db 2

15. 2 db 5 + 20 db 3 + 10 db 3

16. 2 db 5 + 20 db 2 + 10 db 2 + 5 db 6

17. 2 db 5 + 50 db 1 + 10 db 3 + 5 db 2

18. 10 db 4 + 20 db 1 + 2 db 5 + 5 db 6

19. 50 db 1 + 2 db 5 + 20 db 1 + 10 db 2

20. 10 db 2 + 20 db 4

21. 2 db 5 + 20 db 3 + 10 db 1 + 5 db 4

22. 10 db 2 + 20 db 3 + 5 db 4

23. 10 db 1 + 20 db 1 + 50 db 1 + 5 db 4

24. 10 db 4 + 20 db 3

25. 20 db 5

26. 10 db 3 + 20 db 3 + 5 db 2

27. 2 db 5 + 50 db 1 + 10 db 4

28. 2 db 5 + 20 db 2 + 50 db 1

29. 10 db 4 + 20 db 2 + 5 db 4

30. 2 db 5 + 10 db 7 + 5 db 4

31. 2 db 5 + 20 db 2 + 10 db 3 + 5 db 4

32. 2 db 5 + 20 db 4 + 5 db 2

33. 50 db 1 + 20 db 1 + 5 db 6

34. 10 db 2 + 20 db 3 + 2 db 5 + 5 db 2

35. 2 db 5 + 20 db 2 + 10 db 5

36. 50 db 1 + 10 db 2 + 2 db 5 + 5 db 4

37. 10 db 6 + 20 db 1 + 5 db 4

38. 10 db 2 + 20 db 2 + 5 db 8

39. 10 db 6 + 20 db 1 + 2 db 5 + 5 db 2

40. 10 db 1 + 20 db 3 + 5 db 6

41. 20 db 4 + 5 db 4

42. 10 db 3 + 20 db 2 + 5 db 6

43. 2 db 5 + 20 db 4 + 10 db 1

44. 2 db 5 + 20 db 1 + 10 db 5 + 5 db 4

45. 10 db 6 + 20 db 2

46. 10 db 2 + 50 db 1 + 5 db 6

47. 2 db 5 + 20 db 3 + 5 db 6

48. 2 db 5 + 50 db 1 + 10 db 1 + 5 db 6

49. 10 db 5 + 20 db 1 + 5 db 6

50. 2 db 5 + 10 db 1 + 20 db 2 + 5 db 8

51. 20 db 3 + 5 db 8

52. 10 db 4 + 20 db 1 + 5 db 8

53. 10 db 6 + 2 db 5 + 5 db 6

54. 50 db 1 + 10 db 1 + 5 db 8

55. 2 db 5 + 10 db 8 + 5 db 2

56. 2 db 10 + 50 db 1 + 10 db 3

57. 2 db 10 + 20 db 2 + 10 db 2 + 5 db 4

58. 2 db 10 + 20 db 2 + 10 db 3 + 5 db 2

59. 2 db 10 + 20 db 3 + 10 db 1 + 5 db 2

60. 2 db 10 + 20 db 1 + 50 db 1 + 5 db 2

61. 10 db 2 + 2 db 10 + 50 db 1 + 5 db 2

62. 2 db 5 + 20 db 1 + 10 db 3 + 5 db 8

63. 2 db 5 + 10 db 5 + 5 db 8

64. 2 db 5 + 20 db 1 + 10 db 7

65. 10 db 9 + 5 db 2

66. 50 db 1 + 2 db 5 + 5 db 8

67. 10 db 5 + 2 db 10 + 5 db 6

68. 10 db 6 + 5 db 8

69. 2 db 10 + 20 db 3 + 5 db 4

70. 10 db 3 + 20 db 1 + 5 db 10

71. 10 db 5 + 20 db 1 + 2 db 10 + 5 db 2

72. 2 db 10 + 20 db 1 + 10 db 2 + 5 db 8

73. 10 db 8 + 5 db 4

74. 2 db 10 + 20 db 1 + 10 db 4 + 5 db 4

75. 2 db 10 + 10 db 6 + 5 db 4

76. 50 db 1 + 10 db 1 + 20 db 1 + 2 db 10

77. 10 db 1 + 2 db 10 + 50 db 1 + 5 db 4

78. 2 db 5 + 20 db 1 + 10 db 2 + 5 db 10

79. 10 db 8 + 20 db 1

80. 2 db 5 + 20 db 2 + 5 db 10

81. 2 db 10 + 20 db 1 + 10 db 3 + 5 db 6

82. 2 db 10 + 20 db 2 + 10 db 4

83. 2 db 10 + 20 db 2 + 10 db 1 + 5 db 6

84. 2 db 10 + 20 db 3 + 10 db 2

85. 10 db 7 + 2 db 10 + 5 db 2

86. 2 db 5 + 10 db 4 + 5 db 10

87. 2 db 15 + 20 db 2 + 10 db 2 + 5 db 2

88. 2 db 5 + 20 db 1 + 10 db 1 + 5 db 12

89. 10 db 7 + 5 db 6

90. 10 db 1 + 20 db 2 + 5 db 10

91. 10 db 9 + 2 db 5

92. 2 db 10 + 20 db 4

93. 50 db 1 + 5 db 10

94. 2 db 5 + 10 db 3 + 5 db 12

Pardon, felcseréltem az értékeket. Így lesz jó:

1. 1 db 50 + 1 db 20 + 2 db 10 + 2 db 5

2. 2 db 50

3. 5 db 10 + 2 db 20 + 2 db 5

4. 5 db 2 + 1 db 10 + 1 db 20 + 1 db 50 + 2 db 5

5. 1 db 50 + 2 db 20 + 2 db 5

6. 1 db 50 + 3 db 10 + 4 db 5

7. 3 db 10 + 1 db 20 + 1 db 50

8. 1 db 10 + 2 db 20 + 1 db 50

9. 5 db 2 + 1 db 20 + 1 db 50 + 4 db 5

10. 4 db 10 + 2 db 20 + 5 db 2 + 2 db 5

11. 5 db 10 + 1 db 50

12. 1 db 10 + 4 db 20 + 2 db 5

13. 1 db 50 + 4 db 10 + 2 db 5

14. 7 db 10 + 1 db 20 + 2 db 5

15. 5 db 2 + 3 db 20 + 3 db 10

16. 5 db 2 + 2 db 20 + 2 db 10 + 6 db 5

17. 5 db 2 + 1 db 50 + 3 db 10 + 2 db 5

18. 4 db 10 + 1 db 20 + 5 db 2 + 6 db 5

19. 1 db 50 + 5 db 2 + 1 db 20 + 2 db 10

20. 2 db 10 + 4 db 20

21. 5 db 2 + 3 db 20 + 1 db 10 + 4 db 5

22. 2 db 10 + 3 db 20 + 4 db 5

23. 1 db 10 + 1 db 20 + 1 db 50 + 4 db 5

24. 4 db 10 + 3 db 20

25. 5 db 20

26. 3 db 10 + 3 db 20 + 2 db 5

27. 5 db 2 + 1 db 50 + 4 db 10

28. 5 db 2 + 2 db 20 + 1 db 50

29. 4 db 10 + 2 db 20 + 4 db 5

30. 5 db 2 + 7 db 10 + 4 db 5

31. 5 db 2 + 2 db 20 + 3 db 10 + 4 db 5

32. 5 db 2 + 4 db 20 + 2 db 5

33. 1 db 50 + 1 db 20 + 6 db 5

34. 2 db 10 + 3 db 20 + 5 db 2 + 2 db 5

35. 5 db 2 + 2 db 20 + 5 db 10

36. 1 db 50 + 2 db 10 + 5 db 2 + 4 db 5

37. 6 db 10 + 1 db 20 + 4 db 5

38. 2 db 10 + 2 db 20 + 8 db 5

39. 6 db 10 + 1 db 20 + 5 db 2 + 2 db 5

40. 1 db 10 + 3 db 20 + 6 db 5

41. 4 db 20 + 4 db 5

42. 3 db 10 + 2 db 20 + 6 db 5

43. 5 db 2 + 4 db 20 + 1 db 10

44. 5 db 2 + 1 db 20 + 5 db 10 + 4 db 5

45. 6 db 10 + 2 db 20

46. 2 db 10 + 1 db 50 + 6 db 5

47. 5 db 2 + 3 db 20 + 6 db 5

48. 5 db 2 + 1 db 50 + 1 db 10 + 6 db 5

49. 5 db 10 + 1 db 20 + 6 db 5

50. 5 db 2 + 1 db 10 + 2 db 20 + 8 db 5

51. 3 db 20 + 8 db 5

52. 4 db 10 + 1 db 20 + 8 db 5

53. 6 db 10 + 5 db 2 + 6 db 5

54. 1 db 50 + 1 db 10 + 8 db 5

55. 5 db 2 + 8 db 10 + 2 db 5

56. 10 db 2 + 1 db 50 + 3 db 10

57. 10 db 2 + 2 db 20 + 2 db 10 + 4 db 5

58. 10 db 2 + 2 db 20 + 3 db 10 + 2 db 5

59. 10 db 2 + 3 db 20 + 1 db 10 + 2 db 5

60. 10 db 2 + 1 db 20 + 1 db 50 + 2 db 5

61. 2 db 10 + 10 db 2 + 1 db 50 + 2 db 5

62. 5 db 2 + 1 db 20 + 3 db 10 + 8 db 5

63. 5 db 2 + 5 db 10 + 8 db 5

64. 5 db 2 + 1 db 20 + 7 db 10

65. 9 db 10 + 2 db 5

66. 1 db 50 + 5 db 2 + 8 db 5

67. 5 db 10 + 10 db 2 + 6 db 5

68. 6 db 10 + 8 db 5

69. 10 db 2 + 3 db 20 + 4 db 5

70. 3 db 10 + 1 db 20 + 10 db 5

71. 5 db 10 + 1 db 20 + 10 db 2 + 2 db 5

72. 10 db 2 + 1 db 20 + 2 db 10 + 8 db 5

73. 8 db 10 + 4 db 5

74. 10 db 2 + 1 db 20 + 4 db 10 + 4 db 5

75. 10 db 2 + 6 db 10 + 4 db 5

76. 1 db 50 + 1 db 10 + 1 db 20 + 10 db 2

77. 1 db 10 + 10 db 2 + 1 db 50 + 4 db 5

78. 5 db 2 + 1 db 20 + 2 db 10 + 10 db 5

79. 8 db 10 + 1 db 20

80. 5 db 2 + 2 db 20 + 10 db 5

81. 10 db 2 + 1 db 20 + 3 db 10 + 6 db 5

82. 10 db 2 + 2 db 20 + 4 db 10

83. 10 db 2 + 2 db 20 + 1 db 10 + 6 db 5

84. 10 db 2 + 3 db 20 + 2 db 10

85. 7 db 10 + 10 db 2 + 2 db 5

86. 5 db 2 + 4 db 10 + 10 db 5

87. 15 db 2 + 2 db 20 + 2 db 10 + 2 db 5

88. 5 db 2 + 1 db 20 + 1 db 10 + 12 db 5

89. 7 db 10 + 6 db 5

90. 1 db 10 + 2 db 20 + 10 db 5

91. 9 db 10 + 5 db 2

92. 10 db 2 + 4 db 20

93. 1 db 50 + 10 db 5

94. 5 db 2 + 3 db 10 + 12 db 5

Mivel csak véletlenül generálta a variációkat, ezért lehet, hogy van több is, csak ennyinél fogyott el a türelmem.

Ránézésre hiányzik kettő:

20 db 5

50 db 2

Többet nem írok :D

Mégis írok, mert pofon egyszerű algoritmust találtam ki, ami kiszámolta egy pillanat alatt, és 191 a végeredmény. Ezt már nem másolom be, inkább az algoritmust (Python 2.7.9):

[link]

Na kérem, lehet, hogy beteg vagyok, de felvittem az összes lehetőséget egy excel táblába. Az oszlopok az érmék, az értékek a darabszámaik. Az első sorban van a 2*50, az utolsóban a 100*1.

Nem ismételtem egy sort sem, mert szépen haladtam csökkenő értékek szerint, ahogy binárisan visszafelé számol az ember.

Az egyforintos nem volt ugyan a feladatban, de azt is belevettem. Lehet, hogy nem kellett volna, de így éreztem kereknek. (1,2,5,10,20,50) Továbbá a sorrendet sem figyeltem, tehát az 50+20+10 és az 50+10+20 egynek számít.

Az eredmény: 4532 sor.