рекурсия — рекурсивное изменение монет Переполнение стека

Кажется, моя программа дает сбой каждый раз, когда она вызывает рекурсивный вызов минимальной функции. Может кто-нибудь сказать мне, почему это сбой. Он мгновенно зависнет после того, как я вызову минимальную функцию. Это потому, что я использую вектор?

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

1

Решение

Я пытался объясни свой 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Тогда когда же вы ожидаете, что эта рекурсия прекратится?

Я не мог ответить на этот вопрос сам, может, ты сам объяснишь это своей резиновой утке. Когда здесь останавливается рекурсия?

5

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

У вас есть рекурсивный вызов minimum(denom,s - 1, N) так N будут никогда быть меньше или равно 0и рекурсия никогда не закончится.

Это было бы очень легко выяснить, если бы вы узнали, как использовать отладчик, шаг за шагом проходили по коду и входили в рекурсивные вызовы.

1

Еще одна вещь, на которую я хочу обратить внимание, это то, что вы пытаетесь вернуть сумму двух значений:

(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/

1
По вопросам рекламы [email protected]