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

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

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

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

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

Что вы делаете, так это пишете свою рекурсивную процедуру для сохранения текущего значения массива индекса в локальном, добавляете это значение к переданному значению "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;

. Этот код должен иметь следующие свойства:

• Вызов его только с массивом вернет описанный "разделенный" индекс, или -1, если нет ' t one.
• Он считывает из любого элемента в исходном массиве только один раз
• Он считывает элементы исходного массива в строгом порядке индекса.
• Никакого дополнительного хранилища структурированных данных (массива) не требуется.

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

Моя версия:

# 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) также являются допустимыми разрезами.

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

Вот реализация на 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.

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

Ваши правила несколько вводят в заблуждение. Вы требуете, чтобы никакие объекты не были размещены в куче, но IMHO нет решения, где алгоритм не имеет требований к пространству O (n) , то есть стек растет линейно с длиной списка и хвостовые вызовы невозможны, потому что функция должна проверять значения, возвращаемые рекурсивным вызовом.

Код в 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);