递归：在一次遍历中将整数数组分为两个等和部分

Question

递归：在一次遍历中将整数数组分为两个等和部分

algorithmpuzzle

14

使用递归算法，查找一个索引，将数组分成两个部分，使得两个部分的元素之和相等。

“切割”意味着像用刀一样进行切割。所有小于或等于结果索引的单元格的总和必须与大于结果索引的所有单元格的总和相等。不能有任何单元格被省略或同时属于两边。

该数组包含任意整数（即正数、负数和零）。

如果没有这样的索引，则返回-1。

不允许分配堆对象。

必须通过单次遍历来实现。

必须使用递归算法（即不能使用循环结构）。

可以使用任何语言或伪代码。

忘记添加此内容：您不能修改数组。

- flybywire

4

在递归中，如何定义“单次遍历”？你的意思是每个节点只会被访问一次吗？ - Neil N

是的，每个节点只能读取一次（该数组为 RO，请参见问题的更新版本）。 - flybywire

如果数组的总数是奇数怎么办？或者假设它不会是奇数？ - Victor

@bill：任意整数（正数/负数/零） - flybywire

@victor 可以是奇数。例如这个数组：[1, 1, 2] 元素数量为奇数，有解决方案。 - flybywire

显示剩余5条评论

8个回答

3

使用递归进行迭代是一个微不足道的转换，因此我们假设您知道如何做到这一点。

如果您使用“一遍”来构建自己的“到这个索引的总和”数组，并且可以在该数组上进行另一次遍历，我可以看到如何做到这一点。只需遍历第二个数组并从sum[last]中减去sum[x]。如果您发现结果=sum[x]，则返回x。如果没有，则返回-1。

正如Neil N所提到的，如果您对递归的“遍历”定义非常宽松，以便整个递归实际上可以多次访问索引，则可以省略第二个数组。

经过一番思考，我怀疑这个想法是让您仅访问每个数组元素一次（按顺序），并使用递归的内置堆栈属性来摆脱任何第二个数组的需要。

您要做的是编写递归例程，将其当前索引的数组值保存在本地，将该值添加到传入的“sum_of_array”值中，然后调用下一个最高索引的自身（如果有）。如果没有下一个最高索引，则将总和保存到全局变量中，现在可供每个堆叠的递归调用使用。每个例程都通过将其总和与全局总和进行比较来完成。如果它是一半，则返回其索引。否则，返回-1。如果从自身调用返回了非-1，则跳过此最后一步并返回该值。我将以伪Ada的形式展示。

Total_Sum : integer;

function Split (Subject : Integer_Array; After : Integer := 0; Running_Sum : Integer := 0) is
begin
   Running_Sum := Running_Sum + Subject(After);
   if (After < Subject'last) then --'// comment Hack for SO colorizer
      Magic_Index : constant Integer := Split (Subject, After +  1, Running_Sum);
      if (Magic_Index = -1) then
         if (Total_Sum - Running_Sum = Running_Sum) then
            return After;
         else
            return -1;
         end if;
      else
         return Magic_Index;
      end if;
   else
      Total_Sum := Running_Sum;
      return -1;
   end if;
end Split;

这段代码应该具备以下特性：

仅使用数组作为参数调用时，返回所描述的“split”索引，如果没有则返回-1。
只读取一次源数组中的任何元素。
以严格的索引顺序读取源数组元素。
不需要额外的结构化数据存储（数组）。

- T.E.D.

0

public static Int32 SplitIndex(Int32[] array, Int32 left, Int32 right, Int32 leftsum, Int32 rightsum)
{
    if (left == right - 1)
    {
        return (leftsum == rightsum) ? left : -1;
    }

    if (leftsum > rightsum)
    {
        return SplitIndex(array, left, right - 1, leftsum, rightsum + array[right - 1]);
    }
    else
    {
        return SplitIndex(array, left + 1, right, leftsum + array[left + 1], rightsum);
    }
}

方法的调用如下。

Int32[] a = { 1, 2, 3, 1, 6, 1 };

Console.WriteLine(SplitIndex(a, -1, a.Length, 0, 0));

这可以简化为仅使用单个求和并以零为目标。

public static Int32 SplitIndex(Int32[] array, Int32 left, Int32 right, Int32 sum)
{
    if (left == right - 1)
    {
        return (sum == 0) ? left : -1;
    }

    if (sum > 0)
    {
        return SplitIndex(array, left, right - 1, sum - array[right - 1]);
    }
    else
    {
        return SplitIndex(array, left + 1, right, sum + array[left + 1]);
    }
}

现在该方法被称为如下。

Int32[] a = { 1, 2, 3, 1, 6, 1 };

Console.WriteLine(SplitIndex(a, -1, a.Length, 0));

- Daniel Brückner

你是对的 - 它在负数上失败了。我会再看一下。 - Daniel Brückner

无法处理输入 {1,-100,1,1,-100,3}，但是该数组不能被分为 {1,-100,1,1} 和 {-100, 3}，在这两种情况下的总和都是-97。 - flybywire

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)
}

- Roee Adler

0

我的版本：

# Returns either (right sum from the currentIndex, currentIndex, False),
# or, if the winning cut is found, (sum from the cut, its index, True)
def tryCut(anArray, currentIndex, currentLeftSum):
   if currentIndex == len(anArray):
      return (0, currentIndex, currentLeftSum==0)

   (nextRightSum, anIndex, isItTheWinner) = tryCut(anArray, currentIndex + 1, currentLeftSum + anArray[currentIndex])

   if isItTheWinner: return (nextRightSum, anIndex, isItTheWinner)
   rightSum = anArray[currentIndex] + nextRightSum
   return (rightSum, currentIndex, currentLeftSum == rightSum)

def findCut(anArray):
   (dummy, anIndex, isItTheWinner) = tryCut(anArray, 0, 0)
   if isItTheWinner: return anIndex
   return -1

注意：如果返回的索引是5，那么我的意思是sum(anArray[:5]) == sum(anArray[5:])。 "极端情况"也是有效的（其中空切片的总和被认为是零），即如果整个数组的总和为零，则0和len(anArray)也是有效的切割点。

- Federico A. Ramponi

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.

- Nick Johnson

0

Haskell：

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) 的空间需求，也就是说，栈随着列表长度线性增长，并且尾调用不可能，因为函数必须检查递归调用的返回值。

- Torsten Marek

-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);

- Niyaz

对我来说，这在使用数组时返回-1是不应该的...尽管我正在将其移植到Java中。我做错了什么吗？我用'public static int'替换函数，然后在递归调用中添加，a。 - Victor

你可以通过将 s1 + a[i+1] 替换为 s1+a[i] 来修复代码，这样它就可以在某些情况下正常工作。然而，存在一些病态案例会导致代码出错，比如 [3, -3, -3, 3]。这个数组在位置 1 处被分割，但是代码会返回 -1。 - Torsten Marek

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Pesto · Accepted Answer

以下是一种利用Ruby返回多个值的方法。第一个值是分割的索引（如果存在），第二个值是每半部分的总和（如果没有分割，则为整个数组的总和）：

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的意见。现在，数组中的每个索引只被访问一次：

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