рекурсия — Как я могу запрограммировать рекурсивное изменение монеты в C ++?

Question

рекурсия — Как я могу запрограммировать рекурсивное изменение монеты в C ++?

Я пытаюсь создать рекурсивный вызов для изменения монеты в C ++. Я попробовал большую часть алгоритма в интернете, но он, кажется, не относится к вектору или не выводит суммы использованной монеты Может ли кто-нибудь помочь мне понять, что должна вызывать рекурсивная функция? Так что мой алгоритм не дает мне минимальное количество используемых монет, и я не знаю, как сохранить использованную монету.

int coin(vector<int> denom, int s,int N)
{
if(N == 0)
{
return 1;
}
if(N < 0 || (N > 0 && s < 0))
{
return 0;
}

return min(coin(denom,s - 1, N), 1 + coin(denom, s,N-denom[s-1]));

}Input a value N:
Input: 40
Input how many denominations:
Input: 3
Denominations #1:
Input: 5
Denominations #2:
Input: 20
Denominations #3:
Input: 30

Output:
Minimum # of coins: 2
Coin used: 20 + 20
Don't want:  30 + 5 + 5

-3

c++coin-change recursion

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Некоторые моменты для рассмотрения:

Во-первых, нет необходимости отправлять количество конфессий, т.е. s
в качестве аргумента coin метод до тех пор, пока vector используется, потому что vector имеет встроенный size() метод, который делает эту работу для нас.
Во-вторых, сохранить решение тебе нужен другой vector из int названный solution, но это vector это просто вести запись и не имеет ничего общего с рекурсивной реализацией и, следовательно, она определяется как глобальная переменная. Кроме того, вы можете передать его в качестве аргумента, ссылаясь на coin метод тоже.
В-третьих, введенные пользователем номиналы должны быть отсортированы до их передачи coin метод. Для этого я использовал Сортировать метод из algorithm библиотека.

Что в основном делает рекурсивный алгоритм:

На каждом этапе она считает наибольшую номинал d (последний элемент в отсортированном наименовании vector denom лайк denom[denom.size() - 1]) который затем удаляется из vector с помощью pop_back метод vector,
С помощью d мы нашли count_d, который является количество монет номиналом d, используемый в решении. Мы получаем это, просто применяя операцию div, такую как N/d, который дает частное.
затем d добавляется в vector solution, count_d количество раз.
Рекурсивный вызов, добавляет count_d из этой итерации и напоминает coin с уменьшенными номиналами vector denom а также остаток от суммы N с помощью N%d,

Увидеть Коэффициент и остаток для ясности, что див / и мод % операторы делают.

Вот код:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> solution;

int coin(vector<int> denom, int N)
{
if(N <= 0 || denom.size() <= 0)
{
return 0;
}

int d = denom[denom.size() - 1];
denom.pop_back();

int count_d = N/d;

solution.insert(solution.end(), count_d, d);

return count_d + coin(denom, N%d);
}

int main()
{
int N,s;
cout<<"Input a value N:\nInput: ";
cin>>N;
cout<<"Input how many denominations:\nInput: ";
cin>>s;
vector<int> denom;

for(int i = 0; i < s; i++)
{
int d;
cout<<"Denominations #"<<i+1<<":\nInput: ";
cin>>d;
denom.push_back(d);
}

std::sort(denom.begin(), denom.end());

int minNoOfCoins = coin(denom, N);

cout<<"\nOutput:\nMinimum # of coins: "<<minNoOfCoins;

if(minNoOfCoins > 0)
{
cout<<"\nCoins used: ";

for(int i = 0; i < solution.size(); i++)
{
if(i > 0)
{
cout<<" + ";
}
cout<<solution[i];
}
}

cout<<endl;

system("pause");
}

3