首页 文章

使用递归进行硬币更改的基本案例是什么？

提问于
浏览 次
0

我基本上试图通过递归解决硬币变化问题，这是我到目前为止 - ：

#include<iostream>
#include<conio.h>
using namespace std;

int a[]={1,2,5,10,20,50,100,200},count=0;

//i is the array index we are working at
//a[] contains the list of the denominations
//count keeps track of the number of possibilities

void s(int i,int sum) //the function that i wrote
{
    if (!( i>7 || sum<0 || (i==7 && sum!=0) )){

    if (sum==0) ++count; 

    s(i+1,sum);
    s(i,sum-a[i]);

    }
}


int c(int sum,int  i ){  //the function that I took from the algorithmist
    if (sum == 0)
        return 1;
    if (sum < 0)
        return 0;
    if (i <= 0 && sum > 0 )
        return 1;

    return (c( sum - a[i], i ) + c( sum, i - 1 ));
}
int main()
{
    int a;
    cin>>a;

    s(0,a);
    cout<<c(a,7)<<endl<<count;

    getch();
    return 0;
}

第一个函数是s（i，sum）是由我编写的，第二个函数是c（sum，i）是从这里得到的 - （www.algorithmist.com/index.php/Coin_Change） .

问题是计数总是返回比预期更高的值 . 但是，算法主义解决方案给出了正确的答案，但我无法理解这个基本情况

if (i <= 0 && sum > 0 ) return 1;

如果索引（i）小于或等于零且sum仍然不为零，那么函数是否应该返回零而不是一个？

另外我知道算法主义解决方案是正确的，因为在Project Euler，这给了我正确的答案 .

c++ recursion coin-change

2 回答

  • 0

    我猜你的问题是"Assuming that I have unlimited support of coins, on how many ways can I change the given sum"？你给出的算法解决方案也假设，最小的面额是 1 . 否则它将无法正常工作 . 现在你的问题：

    if (i <= 0 && sum > 0 ) return 1;

    注意， i<0 是你用这个值调用它的唯一可能性 - 没有递归调用将使用负值 i . 这种情况（ i<0 ）是一个错误，所以没有结果是正确的（可能断言或异常会更好） . 现在如果 i=0 ，假设在索引 0 处有值硬币 1 意味着只有一种方法可以用这个面额交换 sum - 给出 sum 值为 1 的硬币 . 对？

    经过一段时间的思考，我发现了如何删除 a[0] == 1 的假设 . 更改

    if (i <= 0 && sum > 0 ) return 1;

    成

    if (i <= 0 && sum > 0 ) return sum % a[0] == 0 ? 1 : 0;
    回复于
  • 0

    我认为算法偏向于选择面额，并假设只有一个最小面额的硬币 . 考虑作为正确性的一个反例，没有2个硬币，只有1.5，......并且返回的目标是4：

    (4,1)
    (-1,1)  -> cut, sum<0 a[1]==5
    (4,0)   -> i==0 => 1

    或者你错误地实现了算法（可能有一个错误吗？可能是 i<0 ，还是原始数组是基于1的？）

    回复于

相关问题