3 / 3 / 2
Регистрация: 18.05.2014
Сообщений: 203
|
|
1 | |
Сколькими способами можно разменять 100 000 рублей на монеты 1, 2, 5 рублей?17.01.2015, 19:11. Показов 15440. Ответов 12
Метки нет Все метки)
(
Задача такова: сколькими способами можно разменять 100 000 рублей на монеты 1 2 5 рублей,то есть
нужно выписать количество решений уравнения: 1*x+2*y+5*z=100 000; Объясните ,пожалуйста, алгоритм решения
0
|
17.01.2015, 19:11 | |
17.01.2015, 19:11 | |
Ответы с готовыми решениями:
12
Можно ли разменять 25 рублей десятью монетами достоинством в 1,2 и 5 рублей В кассе есть монеты по 2, 5 и 10 рублей. Сколькими способами можно выдать сдачу на некоторую сумму Sum, значен
|
Заблокирован
|
||||||
17.01.2015, 19:50 | 2 | |||||
Ну я придумал только так)
0
|
2784 / 1937 / 570
Регистрация: 05.06.2014
Сообщений: 5,602
|
||||||
17.01.2015, 20:15 | 3 | |||||
Рекурсия же.
1) Есть только монеты по рублю. N рублей размениваются единственным способом. 2) Есть монеты по рублю и по два. Можно взять от 0 до N/2 монет по два рубля, остальную сумму добрать монетами по рублю Итого - 1+N/2 вариантов. 3) Появились монеты по пять рублей. Берем от 0 до N/5 пятирублевок. Оставшуюся сумму размениваем числом способов посчитанным в пункте 2.
2
|
18 / 18 / 6
Регистрация: 02.07.2011
Сообщений: 67
|
|
17.01.2015, 20:25 | 4 |
floor(1+N/2), так как разменивать монетами по два рубля можно и нечётную сумму
0
|
![]() 343 / 343 / 331
Регистрация: 02.10.2014
Сообщений: 666
|
||||||
17.01.2015, 20:32 | 5 | |||||
Интересное решение (только для данных монет):
0
|
![]() |
|
17.01.2015, 20:33 | 6 |
Классическая задача на динамическое программирование (термин "дин.прог" вообще-то не имеет отношение к созданию программного кода, ну это к слову).
Пусть мы знаем, сколькими способами можно разменять все суммы меньше N. Тогда найти число способов для N можно так - это столько же способов, сколько N-1 (сумма без монеты по копейке) плюс число способов для N-2 (сумма монет без монеты в две копейки) плюс число способов для N-5 (сумма без монеты в пять копеек). Значит, формула: F(N) = F(N-1) + F(N-2) + F(N-5) При этом начальные ограничения такие: F(N) = 0 при N < 0, F(0) = 1. Реализовывать это можно рекурсией, но, как и для чисел Фиббоначи, не стоит. Лучше заводим массив на N элементов и считаем для каждого элемента от 1 до N. Считаться будет очень быстро, т.к. формула элементарна, сложность в точности O(N). Можно сэкономить память за счет быстродействия, заведя массив всего на 6 элементов, т.к. нам нужны только 5 предыдущих (тогда придется постоянно перезаписывать его значения), а можно даже двусвязный список, чтобы при добавлении нового элемента предыдущий первый быстро удалялся (вопрос, в том, что быстрее - перезаписать 5 элементов, или вставить-удалить 5 раз элемент в список) (для быстрой работы с концами - std::list или std::deque).
1
|
D_in_practice
|
17.01.2015, 20:52
#7
|
Не по теме: простите ступил моя программа считает неправильно
0
|
17.01.2015, 21:03 | 8 | |||||
Можно через ДП, а можно по рабоче-крестьянски:
за нас целочисленное деление постарается безо всякой флоры.
2
|
18 / 18 / 6
Регистрация: 02.07.2011
Сообщений: 67
|
|
17.01.2015, 21:21 | 9 |
0
|
![]() |
|
17.01.2015, 21:25 | 10 |
Тоже довольно симпатичный вариант, легко обобщается с сохранением линейной сложности для любых трех монет 1, m, n (и, кажется, немного потруднее - для m, n, p). Быстрее, чем динпрог, и памяти не ест. Жаль, не масштабируется при росте числа монет.
0
|
18 / 18 / 6
Регистрация: 02.07.2011
Сообщений: 67
|
|
17.01.2015, 21:41 | 11 |
Простите, не то вставил.
![]()
0
|
2784 / 1937 / 570
Регистрация: 05.06.2014
Сообщений: 5,602
|
|
17.01.2015, 21:50 | 12 |
res+=1+(100000-z*5)/2 по сути сумма членов арифметической прогрессии плюс ошибки округления. Так что после некоторых шаманств решение должно свестись к константной сложности, после чего его можно расширять на четыре монеты.
0
|
3 / 3 / 2
Регистрация: 18.05.2014
Сообщений: 203
|
|
17.01.2015, 23:31 [ТС] | 13 |
тут не проходит динамика с f(n)=f(n-1)+f(n-2)+f(n-5) хотя бы по той причине, что
mass[1]=1; mass[2]=2; mass[3]=2; mass[4]=3; mass[5]=4; mass[6]=5; и mass[6]<>mass[1]+mass[5]+mass[4];
0
|
17.01.2015, 23:31 | |
17.01.2015, 23:31 | |
Помогаю со студенческими работами здесь
13
Сколькими способами можно оплатить марками бандероль на сумму 25 рублей, если есть неограниченное число марок достоинством в 4, 3, 6 рублей и два спос Сколькими способами можно разменять Сколькими способами можно разменять рубль? Сколькими способами можно разменять рубль? Определить, сколькими способами можно разменять купюру Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
![]() |
Опции темы | |
|
Новые блоги и статьи
![]() |
||||
Отличия между venv, pyenv, pyvenv, virtualenv, pipenv, conda, virtualenvwrapper, poetry и другими в Python
hw_wired 13.02.2025
В Python существует множество средств для управления зависимостями и виртуальными окружениями, что порой вызывает замешательство даже у опытных разработчиков. Каждый инструмент создавался для решения. . .
|
Навигация с помощью React Router
hw_wired 13.02.2025
React Router - это наиболее распространенное средство для создания навигации в React-приложениях, без которого сложно представить современную веб-разработку. Когда мы разрабатываем сложное. . .
|
Ошибка "error:0308010C:digital envelope routines::unsupported"
hw_wired 13.02.2025
Если вы сталкиваетесь с ошибкой "error:0308010C:digital envelope routines::unsupported" при разработке Node. js приложений, то наверняка уже успели поломать голову над её решением. Эта коварная ошибка. . .
|
Подключение к контейнеру Docker и работа с его содержимым
hw_wired 13.02.2025
В мире современной разработки контейнеры Docker изменили подход к созданию, развертыванию и масштабированию приложений. Эта технология позволяет упаковать приложение со всеми его зависимостями в. . .
|
Отличия интерфейсов и типов в TypeScript
hw_wired 13.02.2025
TypeScript - мощное средство для создания качественного и поддерживаемого кода, который расширяет возможности JavaScript, добавляя систему статической типизации. В отличие от динамической типизации. . .
|
Async/await в циклах JavaScript
hw_wired 13.02.2025
Современная веб-разработка немыслима без асинхронного программирования. Когда приложение выполняет длительные операции - загрузку данных с сервера, чтение файлов или обработку медиа-контента, важно. . .
|
Git не работает на MacOS после апдейта
hw_wired 13.02.2025
После очередного обновления MacOS многие разработчики сталкиваются с неприятным сюрпризом - Git перестает работать и выдает ошибку "xcrun: error: invalid active developer path". Эта проблема особенно. . .
|
Git отказывается объединять несвязанные истории
hw_wired 13.02.2025
Git работает безупречно, пока мы не сталкиваемся с особыми ситуациями вроде объединения веток с разными корнями истории. В таких случаях система контроля версий может преподнести неприятный сюрприз в. . .
|
Проверка email с помощью JavaScript
hw_wired 13.02.2025
Email-адреса имеют довольно запутанную спецификацию, которая допускает множество неочевидных вариантов написания. Например, знали ли вы, что адрес вида "name+tag@domain. com" или даже. . .
|
Замена всех вхождений строки с помощью JavaScript
hw_wired 13.02.2025
JavaScript предлагает несколько способов для выполнения операций замены в строках, каждый из которых имеет свои особенности и область применения. От простейшей замены первого найденного вхождения до. . .
|