Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.86/7: Рейтинг темы: голосов - 7, средняя оценка - 4.86
17 / 17 / 6
Регистрация: 10.12.2013
Сообщений: 740
1

Размен по 2 и 5

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

Привет всем. Дана логическая задача. Определите, каким количеством купюр по 2 и 5 рублей можно выдать сумму в N (8 ≤ N ≤ 1000000) рублей так, чтобы общее количество выданных купюр было минимальным. У меня с логикой плоховато. Помогите, если не трудно. Заранее спасибо.
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
28.05.2014, 12:19
Ответы с готовыми решениями:

Размен монет
Имеется n рублей. Требуется разменять данную сумму, если в кассе есть купюры 10 руб, 100 руб, 50...

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

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

Размен монет
Доброго времени суток! Дана следующая задача: имеется неограниченное количество монет; любая...

7
11 / 11 / 12
Регистрация: 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
17 / 17 / 6
Регистрация: 10.12.2013
Сообщений: 740
28.05.2014, 13:29  [ТС] 3
montkay, А как изменить эту программу, чтоб она выдавала минимальное количество выданных купюр по 2 и 5 для размена? Взять s = 0 и для каждого условия s++? (изображение)
Миниатюры
Размен по 2 и 5  
0
11 / 11 / 12
Регистрация: 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
65 / 65 / 54
Регистрация: 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
17 / 17 / 6
Регистрация: 10.12.2013
Сообщений: 740
28.05.2014, 16:17  [ТС] 6
grikukan, А как вот эту строку на С написать, а не на С++? Так как min подчеркивает у меня.
C++
1
dp[i]=min(dp[i-2],dp[i-5])+1;
0
65 / 65 / 54
Регистрация: 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
17 / 17 / 6
Регистрация: 10.12.2013
Сообщений: 740
28.05.2014, 16:32  [ТС] 8
grikukan, Спасибо большое. Перебор количества монет по 5 очень помог.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
28.05.2014, 16:32

Размен монет
помогите сделать После закупки в большом универмаге Мелу досталась сдача в размере 17 центов. Он...

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

Задача на размен денег
Помогите пожалуйста Дано натуральное число n(n&lt;100). Определить число способов выплаты суммы n...

Цикл с параметром (размен купюр)
Помогите составить программу. Условие: Покупатель должен заплатить в кассу 5 руб. У него имеются...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru