0

クラスには次のようなコードがあります。

int SubsetSum(int arr[], int idx, int n, int S)
{
    if (S == 0)
        return 1; // This is stopping condition #1.

    if (S < 0 || n == 0)
        return 0; // This is stopping condition #2.

    return SubsetSum(arr, idx + 1, n - 1, S - arr[idx])
        || SubsetSum(arr, idx + 1, n - 1, S);
}

このコードは、配列が等しい合計 (配列/2 の合計) で 2 つの部分配列に分割できる場合、1 を返します。この関数を拡張して、数値を含む 2 つの配列を返すようにしたいと考えています。

入力の1,2,2,3,0場合は次のように返されます: arr1: 2,2 arr2: 3,1

どうやってやるの？ループは使用できず、再帰関数のみを使用できます。

4

1 に答える 1

1

あなたの前提条件は正しくありません: あなたは書きました

このコードは、配列を合計が等しい 2 つのサブ配列に分割できる場合、1 を返します。

本当じゃない。でテスト

int main() {
   int a[5];
   a[0] = 1; a[1] = 0; a[2] = 0; a[3] = 0; a[4] = 0;

   int const r1 = SubsetSum(a, 0, 5, 1);
   printf("%d\n", r1);

   return 0;
}

これは、合計が等しい部分配列に分割できない場合でも、'1' を返します。

コードについて考え、必要なものを正確に記述してください。

于 2012-12-21T21:25:38.663 に答える