-1

私はサブセット合計のアルゴリズムを実装しています:

SUBSET SUM(X[1 .. n], T ):
if T = 0
return T RUE
else if T < 0 or n = 0
return FALSE
else
return SUBSET SUM(X[2 .. n], T ) ∨ SUBSET SUM(X[2 .. n], T − X[1])

再帰時に縮小配列 X[2...n] を渡す方法を教えてください。

これは私が書いたコードで、セグメンテーション違反を引き起こします:

#include <stdio.h>

    int subsetsum(int a[], int sum, int size)
    {
            if(sum==0)
            return 1;
            else if (sum<0 || size <0)
            return  0;
            else
            return (subsetsum(a+1 , sum, size-1) || subsetsum(a+1, sum - *a, size-1));
    }
    `

    int main(int argc, char **argv)
    {
            int a[]={2,4,1,3,5},x;
            x=subsetsum(a,6,5);
            printf("%d",x);
            return 0;
    }
4

2 に答える 2

2 
template<class It>
void recurse(It begin, It end)
{
   ... recurse(begin+1, end) ...
}
于 2012-06-28T12:35:55.273 に答える
1

C/C++ の配列は、関数への引数として使用されると、配列を表す元のメモリ バッファーへのポインターに暗黙的に減衰されます。したがって、 を渡すX[2...n]には、配列ポインター引数を だけインクリメントするだけです1。たとえば、次のようなことができます。

bool subset_sum(const int* array, const int array_size, int* sum)
{
    //...your code for the rest of the algorithm

    subset_sum(array+1, array_size, sum) //one of the recursive calls
}

次の再帰呼び出しで引数を渡すarray+1と、配列ポインターが 1 つインクリメントされ、配列を指すポインターが取得され、それが arrayX[1...n]を指すようになりX[2...n]ます。引数を使用してarray_size、配列の終わりを検出します。

最後に、次のように呼び出しますsubset_sum。

int array_numbers = {1, 2, 3, 4, 5, 6, 7};
int sum = 0;

subset_sum(array_numbers, sizeof(array_numbers)/sizeof(int), &sum);
于 2012-06-28T12:33:06.257 に答える