0

与えられた配列で、その部分配列の要素の合計が K で割り切れる部分配列 (連続している必要はありません) がいくつ存在するかを求めます。

以下に示すように、複雑さ 2^n のアプローチを知っています。これは、i=[0,n] のすべての nCi を見つけて、合計が K で割り切れるかどうかを検証するようなものです。線形/二次または n^3 などの疑似コードを提供してください。

static int numways = 0;
void findNumOfSubArrays(int  [] arr,int index, int sum, int K) {
        if(index==arr.length) {
                if(sum%k==0) numways++;
        }
        else {
                findNumOfSubArrays(arr, index+1, sum, K);
                findNumOfSubArrays(arr, index+1, sum+arr[index], K);
        }
}
4

3 に答える 3

2

入力 - 長さ n の配列 A、自然数 k。

アルゴリズム:

  • 配列 B を構築します: 1 <= i <= n ごとに: B[i] = (A[i] modulo K)。

これで、動的計画法を使用できます。

D[i,j] = - B[i..n] のサブアレイの最大数を定義し、その要素のモジュロ k の合計が j に等しくなるようにします。

1 <= i <= n. 0 <= j <= k-1。

D[n,0] = (b[n] == 0) の場合、2。それ以外の場合、1。

j > 0 の場合:

D[n,j] = if (B[n] modulo k) == j, than 1. そうでない場合は 0.

i < n および 0 <= j <= k-1 の場合:

D[i,j] = max{D[i+1,j], 1 + D[i+1, D[i+1,(jB[i]+k) modulo k)]}.

  • D を構築します。

  • D[1,0] を返します。

全体の実行時間: O(n*k)

于 2012-08-02T06:59:24.813 に答える
0

実際、K の範囲と配列内の数値の範囲が不明な場合、この問題は O(n^3) または多項式時間で解決できる可能性は低いと思います。これが私が思うことです：

次のケースを考えてみましょう: arr の N 個の数字は次のようなものです

[1,2,4,8,16,32,...,2^(N-1)]

、

このように、arr の 2^N 個の「サブアレイ」(連続している必要はありません) の合計は、[0,2^N) のすべての整数になります。

また、そのうちのいくつが K で割り切れるかを尋ねることは、[0, 2^N) において K で割り切れる整数がいくつあるかを尋ねることと同じです。

上記の場合、答えは (2^N-1)/K (または何か) のように直接計算できることがわかっています。しかし、arr の数個 (おそらく 3? 4?) の数字をランダムに変更して、完全連続整数範囲 [0,2^N) で「ランダムな穴を掘る」と、 [0,2^N) のほとんどすべての数値を使用せずに答えを計算します。

ばかげた考えだけで大丈夫です...完全に間違っている可能性があります。

于 2012-08-02T08:08:06.707 に答える
0

補助配列を使用するA

1) 入力を取得している間、現在の総計を対応するインデックスに保存します (これは で実行されO(n)ます)。

int sum = 0;
for (int i = 0; i < n; i++)
{
    cin >> arr[i];
    sum += arr[i];
    A[i] = sum;
}

2) 今、

for (int i = 0; i < n; i++)
    for (int j = i; j < n; j++)
        check that (A[j] - A[i] + arr[i]) is divisible by k

どうぞ: O(n^2)...

于 2012-08-02T06:58:35.377 に答える