Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Sh@dow777
12 / 12 / 3
Регистрация: 10.12.2013
Сообщений: 674
#1

Размен по 2 и 5 - C++

28.05.2014, 12:19. Просмотров 363. Ответов 7
Метки нет (Все метки)

Привет всем. Дана логическая задача. Определите, каким количеством купюр по 2 и 5 рублей можно выдать сумму в N (8 ≤ N ≤ 1000000) рублей так, чтобы общее количество выданных купюр было минимальным. У меня с логикой плоховато. Помогите, если не трудно. Заранее спасибо.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.05.2014, 12:19
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Размен по 2 и 5 (C++):

Цикл с параметром (размен купюр) - C++
Помогите составить программу. Условие: Покупатель должен заплатить в кассу 5 руб. У него имеются купюры по 1, 5, 10, 50, 100, 500,...

размен монет - Теория вероятностей
сколькими способами можно разместить 10-копеечную монету монетами 1,2,3 и 5 копеек при условии, что каждая из разменненых монет...

Размен суммы - Lisp
Имеется горсть из N монет различного достоинства: c1,c2, ... ,cn.Определить,можно ли на них купить товар стоимостью C копеек. Сколько монет...

Размен монет - Haskell
Написал хаскель-программу размена монет, которой на вход дается отсортированный по возрастанию список монет и количество денег больше...

Задача на размен денег - Python
Помогите пожалуйста Дано натуральное число n(n<100). Определить число способов выплаты суммы n рублей с помощью монет достоинством 1,...

Размен суммы с наименьшим количеством монет - Алгоритмы
Есть такая олимпиадная задача. Всё понятно из темы. Но, жадный алгоритм либо слишком долог, либо в некоторых случаях не работает. Нужен...

7
montkay
10 / 10 / 8
Регистрация: 19.02.2014
Сообщений: 72
28.05.2014, 12:56 #2
Это моё предположение. Вроде всё правильно работает. Если что-то непонятно - спрашивайте (просто не хотел зря комментировать в приложение, ведь вы можете попытаться сами во всем разобраться).

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
25
26
27
28
29
30
31
#include <iostream>
using namespace std;
 
int main()
{
    int money;
    while (true)
    {
        cout << "Enter amount of money: ";
        cin >> money;
        if (!cin)
        {
            cin.clear();
            while (cin.get() != '\n')
                continue;
        }
        else if (money >= 8 && money <= 1000000)
            break;
    }
    if (!(money % 5))
        cout << "For the " << money << " rubley you need " << money / 5 << " 5-rubl blanks\n";
    else if (!((money % 5) % 2))
        cout << "For the " << money << " rubley you need " << money / 5 << " 5-rubl blanks\n"
            << "and " << (money % 5) / 2 << " 2-rubl blanks\n";
    else
        if ((money % 5) && !(((money % 5) + 5) % 2))
            cout << "For the " << money << " rubley you need " << (money / 5) - 1 << " 5-rubl blanks\n"
                << "and " << ((money % 5) + 5) / 2 << " 2-rubl blanks\n";
        else
            cout << "For the " << money << " rubley you need " << money / 2 << " 2-rubl blanks\n";
}
0
Sh@dow777
12 / 12 / 3
Регистрация: 10.12.2013
Сообщений: 674
28.05.2014, 13:29  [ТС] #3
montkay, А как изменить эту программу, чтоб она выдавала минимальное количество выданных купюр по 2 и 5 для размена? Взять s = 0 и для каждого условия s++? (изображение)
0
Миниатюры
Размен по 2 и 5  
montkay
10 / 10 / 8
Регистрация: 19.02.2014
Сообщений: 72
28.05.2014, 15:25 #4
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
25
26
27
28
29
30
31
32
33
#include <iostream>
using namespace std;
 
int main()
{
    int money;
    while (true)
    {
        cout << "Enter amount of money: ";
        cin >> money;
        if (!cin)
        {
            cin.clear();
            while (cin.get() != '\n')
                continue;
        }
        else if (money >= 8 && money <= 1000000)
            break;
    }
    int blanks(0);
    if (!(money % 5))
        blanks = money / 5;
    else if (!((money % 5) % 2))
        blanks = (money / 5) + ((money % 5) / 2);
    else
        if ((money % 5) && !(((money % 5) + 5) % 2))
            blanks = ((money / 5) - 1) + (((money % 5) + 5) / 2);
        else
            blanks = money / 2;
 
    cout << "For the " << money << " rubley you need "
            << blanks << " blanks\n";
}
0
grikukan
61 / 61 / 21
Регистрация: 23.09.2012
Сообщений: 212
28.05.2014, 16:06 #5
А еще эта задача решается динамикой
При заданный ограничениях должно по скорости нормально работать
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
long n,dp[10000007];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        dp[i]=10000000;
    }
    dp[2]=1;
    dp[4]=2;
    dp[5]=1;
    for(int i=6;i<=n;i++)
    {
        dp[i]=min(dp[i-2],dp[i-5])+1;
    }
    cout<<dp[n]<<endl;
}
Добавлено через 5 минут
А еще можно перебирать количество монет по 5

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
using namespace std;
long long n,c2,c5,ans=100000000;
int main()
{
    cin>>n;
    for(c5=0;c5<=n/5;c5++)
    {
        if((n-c5*5)%2==0)
        {
            c2=(n-c5*5)/2;
            if(c5+c2<=ans)
            {
                ans=c5+c2;
            }
        }
    }
    cout<<ans<<endl;
 
}
1
Sh@dow777
12 / 12 / 3
Регистрация: 10.12.2013
Сообщений: 674
28.05.2014, 16:17  [ТС] #6
grikukan, А как вот эту строку на С написать, а не на С++? Так как min подчеркивает у меня.
C++
1
dp[i]=min(dp[i-2],dp[i-5])+1;
0
grikukan
61 / 61 / 21
Регистрация: 23.09.2012
Сообщений: 212
28.05.2014, 16:19 #7
C++
1
2
3
4
5
6
7
8
if(dp[i-2]<dp[i-5])
{
    dp[i]=dp[i-2]+1;
}
else
{
    dp[i]=dp[i-5]+1;
}
1
Sh@dow777
12 / 12 / 3
Регистрация: 10.12.2013
Сообщений: 674
28.05.2014, 16:32  [ТС] #8
grikukan, Спасибо большое. Перебор количества монет по 5 очень помог.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.05.2014, 16:32
Привет! Вот еще темы с ответами:

Программа «Размен», которая выдает все варианты размена указанной суммы - C#
Программа «Размен», которая выдает все варианты размена указанной суммы. Помогите пожалуйста!!! Не представляю как это сделать, изучаю язык...


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

Или воспользуйтесь поиском по форуму:
8
Yandex
Объявления
28.05.2014, 16:32
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru