0

値 N が与えられ、N セントを両替したい場合、S = { S1, S2, .. , Sm} 価値のコインのそれぞれが無限にある場合、両替する方法はいくつありますか? コインの順番は問いません。

以下のコードを書きましたが、常に実際の回答よりも 1 つ少ない数を返します。これがソリューションをコーディングする正しい方法であるかどうか知りたいですか?

#include <stdio.h>

int ways=0;
int remember[100] = {0};

void foo(int coin_denomination[], int size, int sum)
{
    int i;
    printf("%d\n", sum);
    if (sum==0) {
        ways++; 
        return; 
    }   
    if (remember[sum]==1)
        return; 
    remember[sum] = 1;
    if (sum < 0)
        return; 
    for(i=0;i<size;i++)
        foo(coin_denomination, size, sum-coin_denomination[i]);
}

int main()
{
    int coin_denomination[] = {1, 2, 3}; 
    int sum = 5;

    foo(coin_denomination, sizeof(coin_denomination)/sizeof(coin_denomination[0]), sum);
    printf("%d\n", ways);
    return 0;
}
4

1 に答える 1

2

fooメソッドにいくつかの変更が必要です。あなたの問題は、変数を使用すると、rememberいくつかのソリューションを数えていないことです。変数の目的がremember正しくありません。同じコイン コレクションを複数回処理しないために使用していますが、コイン コレクションの合計のみを保存しており、1 1 1合計は複数のコイン コレクションで取得できます (例1 2: 2 番目を選択すると、 remember[3]1 になり、この点を通過できず、解決策がありません1 2 2)

繰り返さない他の方法coin collectionが必要です。この場合、処理中のインデックスを表すパラメーターを追加し、coin_denominationその後のコインの処理のみを許可することで、問題は解決します。

コード (GCC 4.9.0 でテスト済み):

#include <stdio.h>

int ways=0;

void foo(int coin_denomination[], int size, int sum, int coin_idx = 0)
{
    if (sum < 0)
        return;
    int i;
    printf("%d\n", sum);
    if (sum==0) {
        ways++; 
        return; 
    }   
    for(i=coin_idx;i<size;i++)
        foo(coin_denomination, size, sum-coin_denomination[i], i);
}

int main()
{
    int coin_denomination[] = {1, 2, 3}; 
    int sum = 5;

    foo(coin_denomination, sizeof(coin_denomination)/sizeof(coin_denomination[0]), sum);
    printf("%d\n", ways);
    return 0;
}
于 2014-08-03T05:55:23.477 に答える