3 / 3 / 2
Регистрация: 18.05.2014
Сообщений: 203
1

Сколькими способами можно разменять 100 000 рублей на монеты 1, 2, 5 рублей?

17.01.2015, 19:11. Показов 15440. Ответов 12
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Задача такова: сколькими способами можно разменять 100 000 рублей на монеты 1 2 5 рублей,то есть
нужно выписать количество решений уравнения:
1*x+2*y+5*z=100 000;

Объясните ,пожалуйста, алгоритм решения
0
17.01.2015, 19:11
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
17.01.2015, 19:11
Ответы с готовыми решениями:

Можно ли разменять 25 рублей десятью монетами достоинством в 1,2 и 5 рублей
Можно ли разменять 25 рублей десятью монетами достоинством в 1,2 и 5 рублей.Если <<Да>>, то указать количество каждой из монет....

В кассе есть монеты по 2, 5 и 10 рублей. Сколькими способами можно выдать сдачу на некоторую сумму Sum, значен
Какая то дичь, нужно сделать с for

Сколькими способами можно разменять n долларов, если имеются монеты по 50, 25, 10, 5 и 1 цент
Реализовать с помощью PascalABC.NET ЦЕЛЬ РАБОТЫ: -разработка и реализация алгоритмов решения комбинаторных задач теории информации; ...

12
Заблокирован
17.01.2015, 19:50 2
Ну я придумал только так)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
int main()
{
    using namespace std;
    int count = 0;
    for (int x = 0; x < 100000; x++)
    {
        for (int y = 0; y < 50000; y++)
        {
            for (int z = 0; z < 20000; z++)
            {
                if ((x + (2 * y) + (5 * z)) == 100000)
                    count++;
            }
        }
    }
    cout << count << endl;
    system("pause");
    return 0;
}
Но время...
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.
C++
1
2
3
int res=0;
for(int z=0;z<=20000;++z)
    res+=1+(100000-z*5)/2;
2
18 / 18 / 6
Регистрация: 02.07.2011
Сообщений: 67
17.01.2015, 20:25 4
floor(1+N/2), так как разменивать монетами по два рубля можно и нечётную сумму
0
 Аватар для D_in_practice
343 / 343 / 331
Регистрация: 02.10.2014
Сообщений: 666
17.01.2015, 20:32 5
Интересное решение (только для данных монет):
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
 
using namespace std;
 
int main(){
    
    int count = 0;
    for (int x = 0; x <= 10; ++x)
        for (int y = 0; y <= 5; ++y)
            for (int z = 0; z <= 2; ++z)
                if (x + 2*y + 5*z == 10){
                    cout << x << " + 2*" << y << " + 5*" << z << endl;
                    ++count;
                }
    cout << "count = " << count << endl;
    
    int n = 100*1000;
    int out = 1;
    while (n/10 > 0){
        out *= count;
        n /= 10;
    }
    cout << "out = " << out;            
}
0
 Аватар для Гром
212 / 131 / 28
Регистрация: 20.03.2009
Сообщений: 1,123
Записей в блоге: 16
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
4820 / 2286 / 287
Регистрация: 01.03.2013
Сообщений: 5,970
Записей в блоге: 30
17.01.2015, 21:03 8
Можно через ДП, а можно по рабоче-крестьянски:
C++
1
2
3
4
5
6
7
8
int _tmain(int argc, _TCHAR* argv[]) 
{
    long long int n, r=0; cout<<"Input n: "; cin>>n;
    while(n>=0) {r += n/2+1; n -= 5;}
    cout << "result = " << r << endl;
    system("pause");
    return 0;
}
Добавлено через 2 минуты
Цитата Сообщение от andreysv Посмотреть сообщение
floor(1+N/2), так как
за нас целочисленное деление постарается безо всякой флоры.
2
18 / 18 / 6
Регистрация: 02.07.2011
Сообщений: 67
17.01.2015, 21:21 9
Цитата Сообщение от _Ivana Посмотреть сообщение
за нас целочисленное деление постарается безо всякой флоры.
Да, потом уж заметил.
Миниатюры
Сколькими способами можно разменять 100 000 рублей на монеты 1, 2, 5 рублей?  
0
 Аватар для Гром
212 / 131 / 28
Регистрация: 20.03.2009
Сообщений: 1,123
Записей в блоге: 16
17.01.2015, 21:25 10
Цитата Сообщение от Renji Посмотреть сообщение
1) Есть только монеты по рублю. N рублей размениваются единственным способом.
2) Есть монеты по рублю и по два. Можно взять от 0 до N/2 монет по два рубля, остальную сумму добрать монетами по рублю Итого - 1+N/2 вариантов.
3) Появились монеты по пять рублей. Берем от 0 до N/5 пятирублевок. Оставшуюся сумму размениваем числом способов посчитанным в пункте 2.
Цитата Сообщение от _Ivana Посмотреть сообщение
можно по рабоче-крестьянски
Тоже довольно симпатичный вариант, легко обобщается с сохранением линейной сложности для любых трех монет 1, m, n (и, кажется, немного потруднее - для m, n, p). Быстрее, чем динпрог, и памяти не ест. Жаль, не масштабируется при росте числа монет.
0
18 / 18 / 6
Регистрация: 02.07.2011
Сообщений: 67
17.01.2015, 21:41 11
Простите, не то вставил.
Миниатюры
Сколькими способами можно разменять 100 000 рублей на монеты 1, 2, 5 рублей?  
0
2784 / 1937 / 570
Регистрация: 05.06.2014
Сообщений: 5,602
17.01.2015, 21:50 12
Цитата Сообщение от Гром Посмотреть сообщение
Тоже довольно симпатичный вариант, легко обобщается с сохранением линейной сложности для любых трех монет 1, m, n (и, кажется, немного потруднее - для m, n, p). Быстрее, чем динпрог, и памяти не ест. Жаль, не масштабируется при росте числа монет.
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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
17.01.2015, 23:31
Помогаю со студенческими работами здесь

Сколькими способами можно оплатить марками бандероль на сумму 25 рублей, если есть неограниченное число марок достоинством в 4, 3, 6 рублей и два спос
Сколькими способами можно оплатить марками бандероль на сумму 25 рублей, если есть неограниченное число марок достоинством в 4, 3, 6 рублей...

Сколькими способами можно разменять
Сколькими способами можно разменять 100руб в 5,10,20 и 50 руб? решить рекурсией..помогите пожалуйста, к завтрашнему надо

Сколькими способами можно разменять рубль?
сколькими способами можно разменять рубль на монеты достоинством в 10, 15, 20 и 50 копеек? подскажите формулу!

Сколькими способами можно разменять рубль?
сколькими способами можно разменять рубль(100 копеек) на монеты достоинством в 10,15,20 и 50 копеек? (количество копеек не ограничено)

Определить, сколькими способами можно разменять купюру
Очень срочно нужна программа!!!Задание задано по дискретной математике, а точнее по комбинаторике: Реализовать программу для решения задачи...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
13
Ответ Создать тему

Редактор формул (кликните на картинку в правом углу, чтобы закрыть)
Опции темы

Новые блоги и статьи
Отличия между venv, pyenv, pyvenv, virtualenv, pipenv, conda, virtualenvwrapp­­er, poetry и другими в Python
hw_wired 13.02.2025
В Python существует множество средств для управления зависимостями и виртуальными окружениями, что порой вызывает замешательство даже у опытных разработчиков. Каждый инструмент создавался для решения. . .
Навигация с помощью React Router
hw_wired 13.02.2025
React Router - это наиболее распространенное средство для создания навигации в React-приложениях, без которого сложно представить современную веб-разработку. Когда мы разрабатываем сложное. . .
Ошибка "error:0308010C­­:dig­ital envelope routines::unsup­­ported"
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 предлагает несколько способов для выполнения операций замены в строках, каждый из которых имеет свои особенности и область применения. От простейшей замены первого найденного вхождения до. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru