Rekursion: Zerlegen einer Reihe ganzer Zahlen in zwei Teile mit gleicher Summe - in einem einzigen Durchgang

Question

Finde mit Hilfe einer Rekursion einen Index, der ein Array in zwei Teile teilt, so dass beide Teile die gleiche Summe haben.

Schneiden bedeutet, wie mit einem Messer zu schneiden. Alle Zellen mit dem Index <= zum Ergebnis müssen in ihrer Summe gleich sein wie alle Zellen mit dem Index > zum Ergebnis. Keine Zelle darf ausgelassen werden oder Teil beider Seiten sein.

Die Arrays enthalten beliebige ganze Zahlen (d. h. positive, negative und Nullen).

Wenn es keinen solchen Index gibt, geben Sie zurück -1 .

Es ist nicht erlaubt, Heap-Objekte zuzuweisen.

Sie müssen dies in einem einzigen Durchgang tun.

Sie müssen dies mit Rekursion tun (d.h. Sie können keine Schleifenkonstrukte verwenden).

Kann in jeder Sprache oder in Pseudocode sein.

Ich habe vergessen, dies hinzuzufügen : Sie können das Array nicht ändern

Answer 1

Hier ist eine Möglichkeit, die die Fähigkeit von Ruby, mehrere Werte zurückzugeben, ausnutzt. Der erste Wert ist der Index für die Aufteilung (wenn er existiert), der zweite ist die Summe jeder Hälfte (oder die Summe des gesamten Arrays, wenn keine Aufteilung gefunden wird):

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

Ich nenne es mal so:

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

Das Ergebnis ist dies:

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

EDIT:

---

Hier ist eine leicht geänderte Version, die auf die Kommentare von onebyone.livejournal.com eingeht. Jetzt wird auf jeden Index im Array nur einmal zugegriffen:

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

Answer 2

Die Iteration mit Rekursion ist eine triviale Transformation, also gehen wir davon aus, dass Sie wissen, wie man das macht.

Wenn Sie Ihre "einen Durchgang" verwenden, um Ihr eigenes Array von "Summe zu diesem Index" zu erstellen, und können einen weiteren Durchgang auf diesem Array machen, könnte ich sehen, wie es zu tun. Iterieren Sie einfach durch dieses zweite Array und subtrahieren Sie sum[x] von sum[last]. Wenn Sie jemals eine Situation finden, in der das Ergebnis = sum[x] ist, geben Sie x zurück. Wenn nicht, geben Sie -1 zurück.

Wie Neil N. bereits erwähnt hat, könnte man auf das zweite Array verzichten, wenn man "pass" für die Rekursion sehr locker definiert, so dass die gesamte Rekursion tatsächlich mehrfach Indizes besuchen kann.

---

Nachdem ich ein wenig darüber nachgedacht habe, vermute ich, dass die Idee darin besteht, Sie dazu zu bringen, jedes Array-Element nur einmal zu besuchen (in der Reihenfolge) und die in der Rekursion eingebaute Stack-Eigenschaft zu verwenden, um die Notwendigkeit eines zweiten Arrays loszuwerden.

Sie schreiben Ihre rekursive Routine so, dass sie den Array-Wert des aktuellen Indexes in einem Local speichert, diesen Wert zu einem übergebenen "sum_of_array"-Wert addiert und sich dann selbst beim nächsthöheren Index aufruft (falls es einen gibt). Wenn es keinen nächsthöheren Index gibt, wird die Summe in einem Global gespeichert, das nun für jeden gestapelten rekursiven Aufruf verfügbar ist. Jede Routine schließt ab, indem sie ihre Summe mit der globalen Summe vergleicht. Wenn sie halb so hoch ist, gibt sie ihren Index zurück. Andernfalls gibt sie -1 zurück. Wurde bei einem Aufruf an sich selbst ein Wert ungleich -1 zurückgegeben, wird dieser letzte Schritt übersprungen und dieser Wert zurückgegeben. Ich werde in Pseudo-Ada zeigen

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;

Dieser Code sollte die Eigenschaften haben, dass:

• Der Aufruf nur mit einem Array gibt den beschriebenen "Split"-Index zurück, oder -1, wenn es keinen gibt.
• Es wird nur einmal von jedem Element im Quell-Array gelesen
• Er liest die Elemente des Quell-Arrays in strikter Indexreihenfolge.
• Eine zusätzliche strukturierte Datenspeicherung (Array) ist nicht erforderlich.

Answer 3

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

Die Methode wird wie folgt aufgerufen.

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

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

Dies kann reduziert werden, indem man nur eine einzige Summe verwendet und auf Null abzielt.

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

Die Methode wird nun wie folgt aufgerufen.

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

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

Answer 4

Schauen Sie sich das folgende Beispiel an, bei dem nur ein Index verwendet wird, wobei davon ausgegangen wird, dass die Indizes des Arrays 1-basiert sind:

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

Answer 5

Meine Version:

# 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

Hinweis: Wenn der zurückgegebene Index 5 ist, bedeutet dies, dass sum(anArray[:5]) == sum(anArray[5:]). Die "Extreme" sind ebenfalls gültig (wobei die Summe eines leeren Slice Null sein soll), d. h. wenn die Summe des gesamten Arrays Null ist, dann sind 0 und len(anArray) ebenfalls gültige Schnitte.