рекурсия: разрезать массив целых чисел на две части равной суммы - за один проход - PullRequest
Новая
       28

рекурсия: разрезать массив целых чисел на две части равной суммы - за один проход

13 голосов
/ 15 июля 2009

Используя рекурсию, найдите индекс, который разрезает массив на две части, чтобы обе части имели равную сумму.

Резать - значит резать, как ножом. Все ячейки с индексом <= к результату должны быть равны по сумме всем ячейкам с индексом> результату. Ни одна клетка не может быть оставлена ​​или быть частью обеих сторон.

Массивы содержат произвольные целые числа (то есть положительные, отрицательные и нули).

Если такого индекса нет, верните -1.

Вы не можете размещать объекты кучи.

Вы должны сделать это за один проход.

Вы должны сделать это с помощью рекурсии (то есть не можете использовать конструкции цикла).

Может быть на любом языке или псевдокоде.

Забыл добавить это : Вы не можете изменить массив

Ответы [ 8 ]

4 голосов
/ 15 июля 2009

Вот способ сделать это, используя в своих интересах способность 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]

EDIT:

Вот слегка измененная версия для учета комментариев 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
3 голосов
/ 15 июля 2009

Итерация с рекурсией - тривиальное преобразование, поэтому мы предполагаем, что вы знаете, как это сделать.

Если вы используете свой «один проход» для построения собственного массива «сумма к этому индексу» и можете сделать еще один проход для этого массива, я мог бы увидеть, как это сделать. Просто переберите второй массив и вычтите сумму [x] из суммы [последней]. Если вы когда-нибудь найдете ситуацию, в которой результат = сумма [x], вы вернете x. Если нет, тогда верните -1. ​​

Как упомянул Нейл Н., если вы очень слабо определяете "проход" для рекурсии, так что вся рекурсия может фактически посещать индексы несколько раз, тогда вы можете обойтись без второго массива.

Подумав немного об этом, я подозреваю, что идея состоит в том, чтобы заставить вас посещать каждый элемент массива только один раз (по порядку) и использовать встроенное свойство стека рекурсии, чтобы избавиться от необходимости в любом втором массиве.

Что вы делаете, это пишете свою рекурсивную подпрограмму, чтобы сохранить значение массива ее текущего индекса в локальном коде, добавить это значение к переданному значению "sum_of_array", а затем вызвать себя для следующего наибольшего индекса (если он есть). Если нет следующего наивысшего индекса, он сохраняет сумму в глобальном значении, которое теперь доступно для каждого сложного рекурсивного вызова. Каждая процедура заканчивается проверкой ее суммы по отношению к глобальной сумме. Если он наполовину, то он возвращает свой индекс. В противном случае возвращается -1. Если не-1 был возвращен из вызова к себе, этот последний шаг пропускается, и это значение возвращается. Я покажу в псевдо-Аде 

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, если его нет.
  • Читает из любого элемента в исходном массиве только один раз
  • Читает элементы исходного массива в строгом порядке индекса.
  • Дополнительное структурированное хранилище данных (массив) не требуется.
0 голосов
/ 16 июля 2009

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), то есть стек растет линейно с длиной списка, и хвостовые вызовы невозможны, потому функция должна проверять возвращаемые значения из рекурсивного вызова.

0 голосов
/ 16 июля 2009

Вот реализация в Erlang, так как я изучаю ее, и это казалось интересным испытанием. Идея бесстыдно сорвана с решения Песто. 

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.
0 голосов
/ 15 июля 2009

Код на 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);
0 голосов
/ 15 июля 2009

Моя версия: 

# 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, я имею в виду эту сумму (anArray [: 5]) == sum (anArray [5:]). «Экстремумы» также действительны (где сумма пустого среза подразумевается равной нулю), т. Е. Если сумма всего массива равна нулю, то 0 и len (anArray) также являются действительными срезами.

0 голосов
/ 15 июля 2009

Взгляните на следующее, используя только 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)
}
0 голосов
/ 15 июля 2009 
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));
...