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) である 2 番目の関数はここから取得したものです - (www.algorithmist.com/index.php/Coin_Change)。

問題は、 count が常に予想よりもはるかに高い値を返すことです。ただし、アルゴリズムのソリューションは正しい答えを返しますが、この基本ケースを理解できません

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

インデックス (i) が 0 以下で、合計がまだ 0 でない場合、関数は 1 ではなく 0 を返すべきではありませんか?

また、 Project Eulerで正しい答えが得られたため、アルゴリズムのソリューションが正しいことも知っています。

4

2 に答える 2

0

あなたの問題は「私がコインを無制限にサポートしていると仮定して、与えられた合計をいくつの方法で変更できるか」だと思いますか？あなたが与えたalgoritimistsソリューションはまた、最小の宗派がであると仮定します1。そうしないと、正しく機能しません。今あなたの質問：

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

この値で呼び出した可能性があることに注意してください。i<0負の値で再帰呼び出しが行われることはありませんi。このような場合（i<0）はエラーであるため、適切な結果は得られません（おそらく、アサーションまたは例外の方が適しています）。さて、もし、インデックスに価値のあるコインがあるとi=0仮定すると、この金種と交換する唯一の方法があることを意味します-価値のあるコインを与えます。右？01sumsum1

しばらく考えた後、私はその仮定を取り除く方法を見つけましたa[0] == 1。変化する

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

の中へ

if (i <= 0 && sum > 0 ) return sum % a[0] == 0 ? 1 : 0;
于 2012-04-30T12:42:54.687 に答える
0

私は、アルゴリズムが金種の選択に偏っていると考えており、最小金種のコインは 1 つだけであると想定しています。正しさの反例として、コインが 2 枚ではなく 1 枚、5 枚、...、返されるターゲットが 4 枚だったとします。

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

それか、アルゴリズムを誤って実装したかのどちらかです (off by one エラーが発生する可能性がありますか?i<0または元の配列が 1 ベースである可能性がありますか?)

于 2012-04-30T12:18:16.973 に答える