首页 文章

递归硬币改变c

提问于
浏览 次
1

每次递归调用最小函数时，我的程序似乎都会崩溃 . 任何人都可以告诉我它崩溃的原因 . 在我调用最小函数后它会立即冻结 . 是因为我使用矢量吗？

#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;
}
c++ recursion coin-change

3 回答

  • 1

    我试着explain your minimum() function to your rubber duck，你的橡皮鸭有一个问题 . 以下是我们的对话：

    int minimum(vector<int> denom, int s, int N) //take in denomination , sizeofcoin, and value of N
{
    if(N <= 0)
    {
        return 0;
    }

    Me ：如果 minimum() 递归函数的第三个参数 N 为0或为负，则立即返回 .

    Your Rubber Duck ：好的 .

    return (minimum(denom,s - 1, N)...

    （在这里，我尝试在这里向你的橡皮鸭解释你的第一次递归调用）：

    Me ：因此，除了第二个参数递减之外，这将使用相同的参数进行递归调用 . 第三个参数是 N .

    Your Rubber Duck ：所以，如果第三个参数的值 N 未改变，并且递归函数仅在 N 为0或负数时返回而不递归，并且对 minimum() 的初始调用为 N 传递大于0的值，那么当你确切地说期望这个递归停止？

    我自己也无法回答这个问题，也许你可以自己解释一下你的橡皮鸭 . 递归什么时候停止，这里？

    回复于
  • 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/

    回复于

相关问题