Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия, Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки
число способов составить 600 рублей купюрами по 10, 50 и 100
23.02.2008, 13:52
Покупателю в магазине нужно оплатить покупку. У него имеются купюры по 10, 50, 100 рублей. Сколькими способами можно заплатить за покупку, если её стоимость 600 рублей?
Методом перебора нашёл, что количество возможных вариантов равно 49:
Короче: красивой замкнутой формулы нет, ответ выглядит примерно как "коэффициент при в степенном разложении для "
PAV
23.02.2008, 22:40
Через рекуррентные соотношения можно в принципе сделать. Все равно считать придется, но, возможно, чуть меньше. А, главное, можно быть более уверенным, что ни один вариант не пропущен.
Бодигрим
23.02.2008, 22:46
Но вообще вы перебрали верно - там действительно 49 вариантов.
ИСН
24.02.2008, 10:09
А нет, я трындел. Замкнутая формула таки есть (я это понял, глядя на ряд результатов), она всего лишь квадратичная от n, но уродливая и корявая, не однажды включает фрагменты вида "целая часть от n делить на что-то-там", и легче от неё никому не станет, потому выписывать её не буду.
Димитрий
26.02.2008, 06:33
Спасибо!
bot
26.02.2008, 07:04
Я бы по простому пошёл (годится и для 6000 вместо 600):