Задача с монетами

[Zoger]

Здравствуйте! я начал изучать С++ и вот такая задача. "Дано натуральное число N. Как наименьшим количеством монет можно выплатить N копеек. Предполагается что в достаточном количестве имеются монеты достоинством 1, 2, 3, 4, 5, 10, 15, 20, 50 копеек."

код написал в wxDev-C++

#include <iostream>
using namespace std;
int main () {
    int i;
 
    cout << "vvedite natural'noe chislo: ";
    cin >> i;
 
    if (i < 50) cout << " '50' = 0; ";
    else
     cout << " '50' = " << i / 50 << "\n";
    i = i % 50;
 
    if (i < 20) cout << " '20' = 0; ";
    else
     cout << " '20' = " << i / 20 << "\n";
    i = i % 20;
 
    if (i < 15) cout << " '15' = 0; ";
    else
     cout << " '15' = " << i / 15 << "\n";
    i = i % 15;
 
    if (i < 10) cout << " '10' = 0; ";
    else
     cout << " '10' = " << i / 10 << "\n";
    i = i % 10;
 
    if (i < 5) cout << " '5' = 0; ";
    else
     cout << " '5' = " << i / 5 << "\n";
    i = i % 5;
 
    if (i < 3) cout << " '3' = 0; ";
    else
     cout << " '3' = " << i / 3 << "\n";
    i = i % 3;
 
    if (i < 2) cout << " '2' = 0; ";
    else
     cout << " '2' = " << i / 2 << "\n";
    i = i % 2;
     cout << " '1' = " << i << "\n";
 
    getchar ();
    system ("PAUSE");
    return 0;
}

Программа показывает сколько нужно монет с определенным номиналом. а мне нужно чтобы показывало минимальное количество монет.

[waleri]

Сначала разделите на 50 - результат покажет сколько нужно монет по 50. Дальше берите остаток от деления на 50 и делайте то же самое для 20, 15 и т.д.

[Zoger]

Сообщение от waleri

Сначала разделите на 50 - результат покажет сколько нужно монет по 50. Дальше берите остаток от деления на 50 и делайте то же самое для 20, 15 и т.д.

я так и сделал. программа все это показывает. например:
вводим 76. программа выведет ответ:
"50" = 1;
"20" = 1;
"15" = 0;
"10" = 0;
"5" = 1;
"3" = 0;
"2" = 0;
"1" = 1;

а мне надо чтоб он показывал, минимальное количество монет. т.е. 4, всего надо 4 монеты.

[Abstraction]

Сначала разделите на 50 - результат покажет сколько нужно монет по 50. Дальше берите остаток от деления на 50 и делайте то же самое для 20, 15 и т.д.

Только не забыть доказательство, что так получится минимальное количество монет (при наборе монет произвольного номинала это, вообще говоря, неверно - скажем, если убрать монету достоинством 3, 8 копеек такой алгоритм выдаст тремя монетами).

а мне надо чтоб он показывал, минимальное количество монет. т.е. 4, всего надо 4 монеты.

Ну так прибавляйте выводимые числа к переменной coinsTotal.

[BDA]

#include <iostream>
#include <list>

using namespace std;

struct step
{
    int count;
    int n;
};

int
main()
{
    int coins[] = {1, 2, 3, 4, 5, 10, 15, 20, 50};
    int count = sizeof(coins) / sizeof(coins[0]);
    int n;
    cin >> n;
    list<step> l;
    l.push_back({0, n});
    while (1) {
        step tmp = l.front();
        int i;
        for (i = 0; i < count && tmp.n > coins[i]; ++i) {
            l.push_back({tmp.count + 1, tmp.n - coins[i]});
        }
        if (i < count && tmp.n == coins[i]) {
            cout << tmp.count + 1;
            l.clear();
            return 0;
        }
        l.pop_front();
    }
    return 0;
}

Вроде работает (заинтересовала задача - поэтому написал).
Скорее всего, можно "красивее" (похоже, очень медленное решение ).
Номиналы монет можно безболезненно добавлять.

#include <iostream>
#include <list>

using namespace std;

struct step
{
    int count;
    int n;
};

int
main()
{
    int coins[] = {1, 2, 3, 4, 5, 10, 15, 20, 50};
    int count = sizeof(coins) / sizeof(coins[0]);
    int n;
    cin >> n;
    list<step> l;
    l.push_back({0, n});
    while (1) {
        step tmp = l.front();
        int i;
        for (i = count - 1; i >= 0; --i) {
            if (tmp.n > coins[i]) {
                l.push_back({tmp.count + 1, tmp.n - coins[i]});
            } else if (tmp.n == coins[i]) {
                cout << tmp.count + 1;
                l.clear();
                return 0;
            }
        }
        l.pop_front();
    }
    return 0;
}

Чуть быстрее, но решение ужасно

Еще быстрее:

#include <iostream>

using namespace std;

int
count(int n, const int *c, int pos)
{
    if (n == 0) {
        return 0;
    }
    int tmp = n / c[pos];
    if (tmp > 1) {
        return min(tmp + count(n % c[pos], c, pos - 1), tmp - 1 + count(n - (tmp - 1) * c[pos], c, pos - 1));
    } else if (tmp) {
        return tmp + count(n % c[pos], c, pos - 1);
    } else {
        return count(n, c, pos - 1);
    }
}

int
main()
{
    int coins[] = {1, 2, 3, 4, 5, 10, 15, 20, 50};
    int n;
    cin >> n;
    cout << count(n, coins, sizeof(coins) / sizeof(coins[0]) - 1);
    return 0;
}

Тут есть учет варианта 8 = 5 + 2 + 1 или 4 + 4.
Смысл таков - если на данном этапе можем отнять k монет, то также рассматриваем вариант с отъемом k - 1 монет. Совершенно не уверен, что такая логика покрывает все наборы номиналов (т.е. может оказаться, что можно выбрать по-другому монеты, чтобы их было меньше).