Размен по 2 и 5

@Sh@dow777 · Регистрация: 10.12.2013

Привет всем. Дана логическая задача. Определите, каким количеством купюр по 2 и 5 рублей можно выдать сумму в N (8 ≤ N ≤ 1000000) рублей так, чтобы общее количество выданных купюр было минимальным. У меня с логикой плоховато. Помогите, если не трудно. Заранее спасибо.

@montkay · 28.05.2014, 12:56

Это моё предположение. Вроде всё правильно работает. Если что-то непонятно - спрашивайте (просто не хотел зря комментировать в приложение, ведь вы можете попытаться сами во всем разобраться).

C++

#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";
}

@Sh@dow777 · 28.05.2014, 13:29 **[ТС]**

montkay, А как изменить эту программу, чтоб она выдавала минимальное количество выданных купюр по 2 и 5 для размена? Взять s = 0 и для каждого условия s++? (изображение)

@montkay · 28.05.2014, 15:25

C++

#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";
}

@grikukan · 28.05.2014, 16:06

А еще эта задача решается динамикой
При заданный ограничениях должно по скорости нормально работать

C++

#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++

#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;
 
}

@Sh@dow777 · 28.05.2014, 16:17 **[ТС]**

grikukan, А как вот эту строку на С написать, а не на С++? Так как min подчеркивает у меня.

C++

1	dp[i]=min(dp[i-2],dp[i-5])+1;

@grikukan · 28.05.2014, 16:19

C++

if(dp[i-2]<dp[i-5])
{
    dp[i]=dp[i-2]+1;
}
else
{
    dp[i]=dp[i-5]+1;
}

@Sh@dow777 · 28.05.2014, 16:32 **[ТС]**

grikukan, Спасибо большое. Перебор количества монет по 5 очень помог.

@Sh@dow777 17 / 17 / 6 Регистрация: 10.12.2013 Сообщений: 740
		1
	Размен по 2 и 5 28.05.2014, 12:19. Показов 1387. Ответов 7 Метки нет (Все метки) Привет всем. Дана логическая задача. Определите, каким количеством купюр по 2 и 5 рублей можно выдать сумму в N (8 ≤ N ≤ 1000000) рублей так, чтобы общее количество выданных купюр было минимальным. У меня с логикой плоховато. Помогите, если не трудно. Заранее спасибо. __________________ Помощь в написании контрольных, курсовых и дипломных работ здесь 0

@Sh@dow777 17 / 17 / 6 Регистрация: 10.12.2013 Сообщений: 740
	28.05.2014, 13:29 [ТС]	3
	montkay, А как изменить эту программу, чтоб она выдавала минимальное количество выданных купюр по 2 и 5 для размена? Взять s = 0 и для каждого условия s++? (изображение) Миниатюры 0

@Sh@dow777 17 / 17 / 6 Регистрация: 10.12.2013 Сообщений: 740
	28.05.2014, 16:32 [ТС]	8
	grikukan, Спасибо большое. Перебор количества монет по 5 очень помог. 0

Опции темы