14

再帰を使用して、配列を 2 つの部分に分割し、両方の部分の合計が等しくなるインデックスを見つけます。

カットとはナイフのように切るという意味です。結果に対してインデックス <= を持つすべてのセルの合計は、結果に対してインデックス > を持つすべてのセルと等しくなければなりません。セルを除外したり、両側の一部にすることはできません。

配列には、任意の整数 (つまり、正、負、ゼロ) が含まれます。

そのようなインデックスがない場合は、-1.

ヒープ オブジェクトを割り当てることはできません。

1 回のパスで実行する必要があります。

再帰を使用する必要があります (つまり、ループ構造は使用できません)。

任意の言語または疑似コードにすることができます。

これを追加するのを忘れました: 配列を変更することはできません

4

8 に答える 8

4

Ruby の複数の値を返す機能を利用して、これを行う方法を次に示します。最初の値は分割のインデックス (存在する場合)、2 番目の値は各半分の合計 (分割が見つからない場合は配列全体の合計) です。

def split(arr, index = 0, sum = 0)
  return -1, arr[index] if index == arr.length - 1
  sum = sum + arr[index]
  i, tail = split(arr, index + 1, sum)

  if i > -1
    return i, tail
  elsif sum == tail
    return index, sum 
  end
  return -1, arr[index] + tail
end

次のように呼び出します。

p split([1, 1, 2])
p split([1])
p split([-1, 2, 1])
p split([2, 3, 4])
p split([0, 5, 4, -9])

結果は次のようになります。

[1, 2]
[-1, 1]
[1, 1]
[-1, 9]
[0, 0]

編集：

これは、onebyone.livejournal.com のコメントに対処するために少し修正されたバージョンです。これで、配列内の各インデックスは 1 回だけアクセスされます。

def split(arr, index = 0, sum = 0)
  curr = arr[index]
  return -1, curr if index == arr.length - 1
  sum = sum + curr
  i, tail = split(arr, index + 1, sum)

  if i > -1
    return i, tail
  elsif sum == tail
    return index, sum 
  end
  return -1, curr + tail
end
于 2009-07-15T16:40:42.293 に答える
0

以下を見てください。1 つのインデックスのみを使用して、配列のインデックスが 1 ベースであると仮定します。

int recursion(index, rightvalue, leftvalue, array)
{
if array=[] then
{
    if rightvalue=leftvalue then return index
    else return -1
}
else
{
    if rightvalue <= leftvalue
    { recursion(index+1, rightvalue+array[1], leftvalue, array[2..len(array)] }
    else 
    { recursion(index, rightvalue, leftvalue+array[len(array)], array[1..len(array)-1] }
}

int main_function(array)
{
    return recursion(1, 0, 0, array)
}
于 2009-07-15T16:35:49.743 に答える
0

ハスケル: 

split' _ s [] = (-1, s)
split' idx s (x:xs) | sidx >= 0   = (sidx, s')
                    | s * 2 == s' = (idx - 1, s)
                    | otherwise   = (-1, s')
    where (sidx, s') = split' (idx + 1) (x + s) xs

split = fst . split' 0 0

あなたのルールはやや誤解を招くものです。ヒープにオブジェクトを割り当てないようにする必要がありますが、私見では、アルゴリズムに のスペース要件がない解決策はありませんO(n)。つまり、スタックはリストの長さに比例して増加し、関数が再帰呼び出しからの戻り値を検査します。

于 2009-07-15T21:46:26.653 に答える
0

これは Erlang での実装です。私はそれを学んでいて、これは興味深い挑戦のように思えたからです。Pesto のソリューションから恥知らずにアイデアを盗み出しました。

find_split(List) -> {Idx, _Sum} = find_split(List, 1, 0), Idx.
find_split([Head], _Idx, _Sum) -> {-1, Head};
find_split([Head|Tail], Idx, Sum) ->
  case find_split(Tail, Idx + 1, Sum + Head) of
    {-1, Tailsum} when Sum + Head == Tailsum -> {Idx, Sum + Head};
    {-1, Tailsum} -> {-1, Head + Tailsum};
    Ret -> Ret
  end.
于 2009-07-15T20:04:18.793 に答える
-1

C/C++/Java のコード:

function cut(int i, int j, int s1, int s2, int a[])
{
    if(i==j && s1==s2)
        return i;
    else if(i==j && s1!=s2)
        return -1;
    else if(s1>s2)
        return cut(i, j-1, s1, s2 + a[j-1]);
    else
        return cut(i+1, j, s1 + a[i+1], s2);
}

次の構文を使用して呼び出します。

cut(0, array.length, 0, 0, array);
于 2009-07-15T17:32:33.077 に答える