Erschöpfendes Durchsuchen eines Abschnittes und Indexausgabe mit Summe = 0

Juli84

Hallo,

Ich bin gerade daran, ein Programm zu schreiben, welches folgendes macht:
Man hat eine Folge aus n ganzen Zahlen vorgegeben (diese gibt man in meinem Fall nun manuell ein. Die Folge ist: 2, -2, 3, 4, -1, -5, 2, 3, 3, -6). Ausgegeben werden sollen alle zusammenhängenden Abschnitte, deren Summe = 0 ist, also z.B. 0, ..., 1, da 2+(-2) = 0 oder 3, ... 6, da 4+(-1)+(-5)+2 = 0.

Nun hab ich folgenes Programmiert, aber mir wird immer nur 9, ..., 9 ausgegeben, was ja nicht so stimmt. Könnt ihr mir bitte helfen?

#include<stdio.h>

enum{N=10};
typedef double Folge[N];
typedef struct {
int i;
int j;
double summe;
}Abschnitt;

void sum(Folge x, int n, Abschnitt *abschnitt)
{
    int akt_summe; /* Summe des betrachteten Abschnitts */
    int i0, j0, k;

    abschnitt->i = 0;
    abschnitt->j = 0;
    abschnitt->summe = x[0];

/* alle moeglichen Abschnitte werden untersucht */
    for(i0 = 0; i0 < n; i0++)
        for(j0 = i0; j0 < n; j0++)
        {
            akt_summe = x[i0];
            for(k = i0 + 1; k <= j0; k++)
                akt_summe = akt_summe + x[k];
            if(akt_summe == 0)
            {
                abschnitt->i = i0;
                abschnitt->j = j0;
                abschnitt->summe = akt_summe;
            }
        }
}

int main(void)
{
    int n; /* Laenger der Folge */
    Folge x; /* Zahlen der Folge */
    Abschnitt abschnitt;
    int k;

    printf("Eingabe n (<= %d): ", N);
    scanf("%d", &n);
    for(k = 0; k < n; k++)
    {
        printf("Eingabe Folgenglied Nr. %d:", k);
        scanf("%d", &x[k]);
    }

    sum(x, n, &abschnitt);

    printf("Abschnitt: Indizes %d ... %d", abschnitt.i, abschnitt.j);

    return 0;
}

Ich komme irgendwie gar nicht weiter und finde meinen Denkfehler nicht. Ich hoffe, ihr könnt mir helfen!

sehe ich das falsch oda ist da iwie ne schleife zu viel drin.
lg
der in den mai tanzte

Swordfish

...

Juli84 schrieb:

Ausgegeben werden sollen alle zusammenhängenden Abschnitte, deren Summe = 0 ist

Schade, falls man sie nur zählen muss gibt es Algorithmen die schneller sind als O(n²).

Swordfish

...

Swordfish schrieb:

Ja? Cool. Stichwort?

Keine Ahnung wie die heissen. Mir ist halt Ad Hoc einer eingefallen. Prefix-Sum ausrechnen und zählen wie oft jeder Wert vorkommt (sortieren und linear durchgehen z.B.). Wenn ein Wert c mal vorkommt, ergeben sich c*(c-1)/2 Abschnitte.