[C] Trovare massimo segmento nullo

[Manugal]

Ciao a tutti!

Un segmento nullo in un vettore t[0,..,n-1] è un segmento del vettore
t[min,...,max] tale che la somma dei suoi elementi è 0.

Devo scrivere un programma per calcolare la posizione min e max
del massimo segmento nullo in un vettore di interi.

Esempio: t =[-3,-2-1,0,3,5,8] min = 1, max = 4.

Io ho provato a creare un'algoritmo:

#include <stdio.h>
#include <stdlib.h>

void max_segmento(int [], int);

int main(void){

   int length,i;

   printf("Inserisci lunghezza vettore: ");
   scanf("%d", &length);

   int a[length];

   for(i=0; i<length; ++i)
      scanf("%d", &a[i]);

   max_segmento(a,length);
}

void max_segmento(int a[], int l){

    int min,max,i,j,sum;

    for(i=0; i<l; ++i)
       min=i;
       sum=a[i];
       for(j=i+1; j<=l; ++j)
          max=j;
          sum+=a[j];
          if(sum==0){
             printf("Min = %d   Max = %d", min, max);
             exit(1);
          }
}

Il problema è che non stampa niente dandogli come input l'array dell'esempio. Eppure mi sembra che non sforo mai il range dell'array.

[max246]

Originariamente inviato da Manugal

Ciao a tutti!

Un segmento nullo in un vettore t[0,..,n-1] è un segmento del vettore
t[min,...,max] tale che la somma dei suoi elementi è 0.

Devo scrivere un programma per calcolare la posizione min e max
del massimo segmento nullo in un vettore di interi.

Esempio: t =[-3,-2-1,0,3,5,8] min = 1, max = 4.

Io ho provato a creare un'algoritmo:

#include <stdio.h>
#include <stdlib.h>

void max_segmento(int [], int);

int main(void){

   int length,i;

   printf("Inserisci lunghezza vettore: ");
   scanf("%d", &length);

   int a[length];

   for(i=0; i<length; ++i)
      scanf("%d", &a[i]);

   max_segmento(a,length);
}

void max_segmento(int a[], int l){

    int min,max,i,j,sum;

    for(i=0; i<l; ++i)
       min=i;
       sum=a[i];
       for(j=i+1; j<=l; ++j)
          max=j;
          sum+=a[j];
          if(sum==0){
             printf("Min = %d   Max = %d", min, max);
             exit(1);
          }
}

Il problema è che non stampa niente dandogli come input l'array dell'esempio. Eppure mi sembra che non sforo mai il range dell'array.

Fai questo:

-Inserimento dei numeri
-Variabile max
-Ciclo che se max è maggiore del prossimo allora metti la il valore in max se no continui
-stessa cosa con min.. pero devi dirgli se è minore

piu semplice

[Manugal]

Scusa ma non ho tanto capito. Min e max sono gli indici di un sottovettore, dove la somma dei suoi elementi è 0. Che intendi dire con " ciclo se max è maggiore del prossimo". Quale prossimo?

[cionci]

int main(void){

   int length,i;

   printf("Inserisci lunghezza vettore: ");
   scanf("%d", &length);

   int a[length];

Questo non lo puoi fare... Devi usare l'allocazione dinamica con malloc...oppure devi allocare il vettore staticamente...

C'è un algoritmo semplicissimo per trovare la soluzione...

Prova a fare la somma di tutto il vettore...e guarda un po' cosa devi fare per riportare la somma a 0...

[Manugal]

Grazie. Per quanto riguarda a[length] ti posso assicurare che funziona. E' la prima cosa che ho controllato quando ho visto che il programma non funzionava. Infatti appena dopo il riempimento dell'array avevo messo per prova un ciclo per stampare l'array e lo stampa correttamente. Forse mi hai detto così perché quello che ho fatto è una cattiva norma di programmazione?

Il mio algoritmo quindi non va bene? Ho provato a sommare tutto il vettore quello dell'esempio. Una cosa che ho pensato è questa:

-3 + -2 + -1 + 0 + 3 + 5 + 8 = 10 somma del vettore

10 - 8 - (-3) = 5 (sottraggo dalla somma il primo elemento dell'array e l'ultimo aggiornando gli indici)

5 - 5 = 0 (sottraggo solo l'elemento della parte destra visto che sono arrivato a 0 e aggiorno l'indice)

Potrebbe andare così?

[cionci]

Per quanto riguarda lenght ti assicuro che è sbagliato... L'allocazione di quel vettore avviene con un intero casuale contenuto in lenght prima dell'inizializzazione...

Sì...il discorso è quello... Prova a trovare le condizioni per cui devi sottrarre l'elemento più lontano a destra o l'elemento più lontano a sinistra...
Cioè: quando devi sottrarre a[min] e quando devi sottrarre a[max] ?

[Manugal]

Posso fare un while che dice finché la somma è diversa da 0 sottrai l'elemento più lontano a destra e l'elemento più lontano a sinistra aggiornando i rispettivi indici. Quando la somma diventa uguale a 0 a quel punto esce dal ciclo e gli indici aggiornati con le operazioni di sottrazione sono automaticamente il min e il max.

Sempre a proposito del length: come dovrei allocare il vettore dinamicamente (senza usare un puntatore). Si può fare?

[cionci]

Per allocare il vettore dinamicamente devi usare un puntatore...non c'è altro modo...

int *a = (int *) malloc(sizeof(int) * length);

Comunque il puntatore lo devi usare solo lì... Dopo lo usi come un normale vettore (a parte l'intestazione della funzione in cui devi sostituire "int a[]" con "int *a")

[Manugal]

L'algoritmo l'ho scritto....

void max_segmento(int *a, int l){

    int i,j,sum=0;

    for(i=0; i<l; ++i)
      sum+=a[i];

    j=l-1;
    i=0;
    while(sum!=0)
       sum-=a[j--]-a[i++];

    printf("Min = %d   Max = %d", i, j);
}

....ma anche ora non mi stampa niente

[Manugal]

modificato

void max_segmento(int *a, int l){

    int i,j,sum=0;

    for(i=0; i<l; ++i)
      sum+=a[i];

    j=l-1;
    i=0;
    sum-=a[j--]-a[i++];

    if(sum!=0)
       if(sum==a[j])
          sum-=a[j--];
       else if(sum==a[i])
          sum-=a[i++];
    else
       printf("Min = %d   Max = %d", i, j);
}

Solo che mi da min=1 e max=5 invece di min=1 e max=4

[cionci]

No, non ci siamo, questo è solo un caso particolare... Devi riflettere sul segno della somma...

Se la somma è pari a 10, cosa ci dovrai togliere per farla avvicinare a 0 ? E se la somma è uguale a -10 cosa ci dovrai togliere per farla avvicinare a 0 ?

[Manugal]

Se la somma è uguale a 10 dovrò sottrarre gli estremi come prima, se è -10 dovro aggiungere gli estremi. Forse non ho capito la condizione per la quale devo sottrarre gli estremi.

[cionci]

No...devi fare solo sottrazioni...
Una volta devi sottrarre un estremo e un volta l'altro... Pensa un po'...

[Manugal]

Scusa ma se devo sempre sottrarre quando ho una somma negativa e sottraggo una volta un estremo e una volta l'altro, alla fine non viene zero. Esempio:

[3,-8,-7,0,8,7,5,-6,-6] la cui somma è -4

Il segmento nullo in questo caso è [-8,-7,0,8,7].

Se sottraggo la somnma una volta per un estremo e una volta per l'altro non viene zero. Piuttosto dovrei trovare una condizione che mi dica quado devo sottrarre e quando no.

[cionci]

Io credevo che dovessero essere ordinati...sono stato tratto in inganno dal tuo esempio...

[Manugal]

Ahhh lo sai mi hai fatto venire il dubbio anche a me....

Comunque credo che debbano essere ordinati. In questo caso però devo cmq trovare una condizione che mi dice quando posso sottrarre e quando no. Oppure non serve?

[Manugal]

void max_segmento(int *a, int l){

    int i,j,sum=0;

    for(i=0; i<l; ++i)
      sum+=a[i];

    j=l-1;
    i=0;

    while(sum!=0)
        sum-=a[i++]-a[j--];

    if(sum==0)
       printf("Min = %d   Max = %d", i, j);
}

Questo dovrebbe andare bene (dato che sia se ho sum positiva o sum negativa devo sempre sottrarre gli estremi). Il problema è che dentro al while non mi modifica la sum e infatti alla fine non mi stampa niente.

[Manugal]

up