Verzweifelt: Algorithmus zur Ermittlung aufeinander folgender Zahlen Array

[Ryu]

Hallo,

ich sitze seit mehreren Stunden an einer kurzen und eleganten Lösung um die Summe von aufeinanderfolgenden Zahlen <> 0 in einem Array zu bestimmen.

Beispiel
Ich hab vereinfacht gesagt ein Array vom Typ TValue

Delphi-Quellcode:

TValue = record
         value: integer;
         sum: integer;
end;

Beispielhaft:

Delphi-Quellcode:

Values.val  = [0, 5, 4, 9, 0, 0, 1, 0, 0, 3, 4, 0]

Daraus sollen die Summen aufeinanderfolgender Zahlen <> 0 ermittelt werden.

Delphi-Quellcode:

Values.sum = [0, 18, 18, 18, 0, 0, 1, 0, 0, 7, 7, 0]

Das mag jetzt für euch relativ einfach klingen, aber ich komm einfach nicht auf eine funktionierende Lösung. Deswegen bitte ich hier um Tipps.

PS: es handelt sich hier nur um Pseudo Code um das Problem einigermaßen anschaulich zu erklären...

[Der schöne Günther]

Hallo und Herzlich Willkommen in den Heiligen Hallen des Wissens und des Wahnsinns :roteyes:

Zum Thema Wahnsinn gleich vorweg: Ich verstehe deine Beispieldaten nicht. Wenn du die "Summe zweier aufeinanderfolgenden Zahlen ungleich Null" haben willst, wäre bei der Zahlenreihe

Delphi-Quellcode:

[a,b,c,d, [...]]

die "Summenreihe" doch [a+b, b+c, c+d, ...], oder? Ich finde das in deinen Beispieldaten nicht wieder. Wie kommt man da auf

Delphi-Quellcode:

[0, 18, 18, 18, 0, 0, 1, 0, 0, 7, 7, 0]

?

Außerdem würde ich stark davon abraten, deinen Record

Delphi-Quellcode:

TValue

zu nennen- Das beißt sich mit dem bereits in Delphi existierenden Typen

Delphi-Quellcode:

TValue

;-)

[BUG]

Ich geb dir mal einen Ansatz, wie ich das mit dem ersten "Bündel" machen würde:

Code:

Beginnend von Index i = 0

Solange Values[i].value = 0:
  Values[i].sum = 0
  i += 1

Anfang a = i;
Summe s = 0;

Solange Values[i].value = 0:
  s += Values[i].value
  i += 1

Für j := a bis i-1:
  Values[j].sum = s

Was fehlt noch:

• äußere Schleife um das ganze Array zu durchlaufen
• Abbruch bei Ende des Arrays

Das sollte in etwa so hinkommen :mrgreen:

[Ryu]

Hallo Günther,

ich habe den Typen nicht TValue genannt in meinem Delphi Code, wie gesagt ist dies nur reiner Pseudocode :)

Zu der Frage wie ich zu den Zahlen komme:

Die Idee ist, dass ich solange die nächste Zahl addiere bis eine Null kommt. Anschließend setze ich die aus dem vorherigem Schritt resultierende Summe auf die Zahlen die ich eben durchgegangen bin... Schwierig zu erklären, schwierig umzusetzen. Deswegen nochmal etwas anschaulicher:

Delphi-Quellcode:

Values.val = [0, 5, 4, 9, 0, 0, 1, 0, 0, 3, 4, 0] 

Values.sum = [0, 18, 18, 18, 0, 0, 1, 0, 0, 7, 7, 0]

Die erste 18 soll sich ergeben aus 5 + 4 + 9.
Die zweite 18 auch aus 5 + 4 + 9, denn es folgt vor der 4 und nach der 4 keine 0.
Die dritte 18 ebenfalls aus 5 + 4 + 9, da zwar danach eine 0 folgt aber vorher alle Zahlen <> 0 sind.

Man könnte fast sagen, ich möchte die Summe der Zahlen haben, welche "innerhalb" von 0en gekapselt ist. Die berechnete Summe soll, auf den in den "0en gekapselten" Zahlen gesetzt werden.

Ich hoffe ich habe es einigermaßen verständlich erklärt, ansonsten bitte nochmal nachhaken. Es fällt mir manchmal schwer solche Sachverhalte einfach und knapp zu erklären :oops:

Und jetzt lese ich mir mal die Antwort durch von BUG :thumb:

Edit:
Danke für deinen Vorschlag Robert, ich bin den mal auf ein Blatt Papier durchgegangen und für's erste Bündel klappts aufjedenfall. Ich werde mal versuchen den zu implementieren. Weitere Vorschläge/Tipps sind gerne willkommen, nichtsdestotrotz danke schonmal.Allerdings habe ich aus der zweiten While-Schleife folgendes gemacht:

Delphi-Quellcode:

 ... Solange Values[i].value <> 0:
  s += Values[i].value
  i += 1

Edit2:
Wow Robert, dein Code funktioniert! Zumindest fürs erste Bündel läuft das ganze schonmal!!! Ziemlich peinlich wenn man seit 2 Tagen nicht auf die Lösung kommt und im Forum jemand das Problem nach 5 Minuten gelöst hat..........
Mal schauen ob ich es aufs ganze Array übertragen kann welches übrigens eine Länge von 14 hat.

Edit3:

holy fuck es funktioniert!!!!!!!!!!!! woohoo ! :D 1000-faches dankeschön, ich hätte echt ne wand eingerissen, wenn ich das Problem nicht heute noch gelöst hätte. !!!!

[jfheins]

Ich habe da mal schnell was gemacht:

Code:

    static void Main()
    {
        int[] input = new int[] {0, 5, 4, 9, 0, 0, 1, 0, 0, 3, 4, 0};
        
        int runningsum = 0;
        int elems = 0;
        
        fo&#636;(int i = 0; i < input.Length; i++)
        {                        
            if(input[i] == 0)
            {
               // Ausgabe
                for(int j = 0, j < elems, j++)
                    Console.Write("{0} ", runningsum);
                    
                Console.Write("0 ");
                runningsum = 0;
                elems = 0;
            }
            else
            {
                runningsum += input[i];
                elems++;
            }
        }
        for(int j = 0; j < elems; j++)
            Console.Write("{0} ", runningsum);        
    }

Es handelt sich dabei natürlich nur um Pseudo-Code, um die Lösung zu verdeutlichen ;-)

[himitsu]

1. Variante:

* das Array Wert für Wert durchlaufen (also erstmal der Array-Anfang)
* Wenn 0 dann 0
* wenn keine 0, dann eigener Wert + äußere Werte (zwei innere Schleifen)
* * alle Nicht-Null davor, bis zum Anfang oder zur ersten nächsten 0
* * alle Nicht-Null danach, bis zum Ende oder zur ersten nächsten 0

2. Variante:

* aktuelle Position merken
* nächste 0 suchen
* dabei gleich die Summe bilden (mitzählen)
* bei allem von aktueller Position bis vor der 0 mit der der Summe befüllen
* und nun alles von vorne
* * also Position nach der 0
* * nächste 0 suchen
* * dabei gleich die Summe bilden (mitzählen)
* * bei allem von aktueller Position bis vor der 0 mit der der Summe befüllen
* * und nun alles von vorne
* * * ...

[Blup]

Noch eine Variante:

Delphi-Quellcode:

function MyArrayCalc(const AValues: TIntegerDynArray): TIntegerDynArray;
var
  i, sum: Integer;
begin
  SetLength(Result, Length(AValues));

  sum := 0;
  for i := 0 to High(AValues) do
  begin
    if AValues[i] = 0 then
      sum := 0
    else
      sum := sum + AValues[i];
 
    Result[i] := sum;
  end;

  sum := 0;
  for i := High(AValues) downto 0 do
  begin
    if AValues[i] = 0 then
      sum := 0
    else
    begin
      Result[i] := Result[i] + sum;
      sum := sum + AValues[i];
    end;
  end;
end;

[Dejan Vu]

Diese Funktion liefert die Summe für eine beliebige Position (zumindest soll sie das).

Delphi-Quellcode:

function GetConsecutiveSum(position : Integer) : Integer;
Begin
  if Values[position]=0 then begin 
     result := 0
     exit;
  end;
    
  while (position > low(Values)) and (Values[position] <> 0) do 
    dec(position);

  result := 0;
  repeat
    inc(result,values[position]);
    Inc(position);
  until (position>High(values)) or (values[position]=0);
end;

Getippt und nicht getestet.

[Blup]

Funktioniert nicht wenn du auf einer Position stehst die den Wert 0 hat und ein Wert <> 0 folgt.

[Dejan Vu]

Jetzt vielleicht?