Кажется, моя программа дает сбой каждый раз, когда она вызывает рекурсивный вызов минимальной функции. Может кто-нибудь сказать мне, почему это сбой. Он мгновенно зависнет после того, как я вызову минимальную функцию. Это потому, что я использую вектор?
#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;
int minimum(vector<int> denom, int s, int N) //take in denomination , sizeofcoin, and value of N
{
if(N == 0)
{
return 1;
}
else if(N < 0 || (N > 0 && s <=0))
{
return 0;
}
else
{
return min(minimum(denom,s - 1, N), 1 + minimum(denom, s,N-denom[s-1]));
}
}
int main()
{
int N;
unsigned int sizeofcoin;
cout << "Enter the value N to produce: " << endl;
cin >> N;
cout << "Enter the number of different denominations: " << endl;
cin >> sizeofcoin;
vector<int> denom(sizeofcoin);
for(unsigned int i= 0; i < sizeofcoin; i++)
{
cout << "Enter denomination #" << (i+1) << endl; //save all the denominations in an array
cin >> denom[i];
}
sort(denom.begin() , denom.end(),greater<int>()); //sort the array from largest to smallest
if(denom.back() != 1) //check the end of the array (since the back is smallest now) if it has 1
{
denom.push_back(1); //Will include 1 if the user does not input a 1 (doesn't have to be used)
}
minimum(denom,sizeofcoin,N);
return 0;
}
Я пытался объясни свой minimum()
функционировать к вашей резиновой утке, и у твоей резиновой утки есть вопрос к тебе. Вот как прошел наш разговор:
int minimum(vector<int> denom, int s, int N) //take in denomination , sizeofcoin, and value of N
{
if(N <= 0)
{
return 0;
}
мне: этот minimum()
рекурсивная функция немедленно возвращает свой третий параметр, N
, равно 0 или отрицательно.
Ваша резиновая утка: Хорошо.
return (minimum(denom,s - 1, N)...
(Здесь я попытался объяснить ваш первый рекурсивный вызов здесь, вашей резиновой утке):
мнеТаким образом, это делает рекурсивный вызов с теми же параметрами, за исключением того, что 2-й параметр уменьшается. Третий параметр N
,
Ваша резиновая уткаИтак, если значение третьего параметра, N
, не изменяется, и рекурсивная функция возвращается без рекурсии, только когда N
0 или отрицательный, и первоначальный вызов minimum()
передает значение больше 0 для N
Тогда когда же вы ожидаете, что эта рекурсия прекратится?
Я не мог ответить на этот вопрос сам, может, ты сам объяснишь это своей резиновой утке. Когда здесь останавливается рекурсия?
У вас есть рекурсивный вызов minimum(denom,s - 1, N)
так N
будут никогда быть меньше или равно 0
и рекурсия никогда не закончится.
Это было бы очень легко выяснить, если бы вы узнали, как использовать отладчик, шаг за шагом проходили по коду и входили в рекурсивные вызовы.
Еще одна вещь, на которую я хочу обратить внимание, это то, что вы пытаетесь вернуть сумму двух значений:
(minimum(denom,s - 1, N) + minimum(denom, s,N-denom[s-1])
вместо этого вам следует сделать следующее:
min(minimum(denom,s - 1, N), 1 + minimum(denom, s,N-denom[s-1]))
Идея состоит в том, что при первом вызове вы не использовали ни одной монеты, но при втором вызове вы использовали одну, поэтому добавляете 1 для одной и той же.
Ищите решение динамического программирования для того же.
https://people.cs.clemson.edu/~bcdean/dp_practice/