Funzione in c

[NInchee]

Salve ragazzi, non riesco a risolvere questo esercizio. Mi potreste aiutare?
Scrivere la funzione in c che riceve in ingresso in lista collegata con puntatori L di valori int e restituisce tra i parametri formali un array V ottenuto nel modo seguente: • Inizialmente, la funzione rimuove dalla lista L gli elementi la cui posizione corrisponde ad un numero della successione di Fibonacci (ipotizzare che il primo elemento della lista abbia posizione 1 e che i primi due valori della successione di Fibonacci siano F0=1, F1=2, con l’elemento generico della successione dato da Fn=Fn-1+Fn-2); • Gli elementi rimossi da L sono inseriti nell’array V in modo che l’ultimo elemento rimosso da L sia l’elemento in testa di V (l’array V deve essere allocato internamente alla funzione. Come dimensione può essere usata la lunghezza della lista L). Ogni elemento della lista L, ha la forma seguente: struct list {
int value;
Int pos;
Struct list * next_ptr;
};
dove la posizione occupata dall’elemento nella lista non cambia nel corso della esecuzione. Scrivere anche la funzione di costo e la complessità della funzione.

[apatriarca]

In cosa incontri esattamente difficoltà? Hai capito che cosa deve fare la funzione? Sai come lavorare con liste e array?

[NInchee]

Trovo difficoltà soprattutto nell’ultima parte dove chiede di copiare gli elementi sull’array ma In ordine inverso.

[apatriarca]

Per quella parte ci sono tre soluzioni:
1. Inserirli nell'ordine in cui sono stati rimossi e poi invertire gli elementi dell'array.
2. Inserire il nuovo elemento all'inizio dell'array spostando quindi tutti gli altri elementi ogni volta.
3. Calcolare in anticipo la lunghezza dell'array e quindi inserire gli elementi direttamente nella loro posizione finale.

[NInchee]

la prima soluzione l'ho già svolta, mi servirebbe aiuto con il codice per la seconda soluzione.

[apatriarca]

Supponendo che "array" sia l'array, che il nuovo valore sia "value", che la dimensione sia "size" e che l'array sia già stato allocato in modo da poter contenere almeno "size+1" elementi, allora il codice per farlo è qualcosa come il seguente:

for (int i = size; i > 0; ++i) { array[i] = array[i-1]; }
array[0] = value;
++size;

La soluzione 1 è asintoticamente migliore in quanto ha complessità O(n) contro questa che è necessariamente O(n²)..

[NInchee]

grazie mille, se ti inviassi il resto della funzione gli potresti dare un'occhiata e magari correggermelo??

[vict85]

Vi è in realtà anche una 4 soluzione: spostare gli elementi eliminati in una seconda lista (inserendo sempre gli elementi all'inizio) e poi copiare la nuova lista nell'array.

[apatriarca]

@Andrea9802 c'è una ragione per cui tu non possa postarlo direttamente nel forum invece di inviarmelo?

@vist85 se si stesse parlando di un qualche linguaggio in cui è facile usare le liste avrebbe potuto forse aver senso, ma così mi sembra solo più complicata da implementare e fa uso di più memoria. La soluzione più efficiente e facile da implementare è la 1. Qualsiasi altra soluzione ha senso solo se si vuole inserire gli elementi nell'ordine inverso per principio.

[vict85]

In realtà è più facile da fare in c che usando le std::list del c++. E se lo fai usando nuova memoria allora lo stai facendo nel modo sbagliato.
Devi prendere l'elemento della lista e spostarlo (non copiarlo!) nell'altra lista. Poi ovviamente dei cancellare la memoria della seconda lista.
Di fatto invece di cancellare l'elemento lo tieni in vita quel che basta per aiutarti ad ordinare gli elementi.

[Xemitron]

Scusate, dato che sono interessato anch'io a tale funzione, come potrei aggiustare (in merito allo stesso esercizio) il seguente codice? Grazie in anticipo

boolean function(struct list **L, int **V, int N) {

    int i, j, value;
    int *F;
    struct list *tmp_ptr;

    F = (int *) malloc (sizeof (int) * N);
    F[0] = 1;
    F[1] = 2;

    for (i = 2; i < N && F[i - 1] < N; i++) {
        F[i] = F[i - 1] + F[i - 2];
    }

    *V = (int *) malloc (sizeof (int) * N);
    j = 0;
    while (*L != NULL) {
        if ((*L)->pos == F[i]) {
            (*V)[j] = (*L)->value;
            tmp_ptr = *L;
            *L = (*L)->next_ptr;
            free (tmp_ptr);
            i++;
            j++;
        } else {
            L = &((*L)->next_ptr);
        }
    }

}

[vict85]

Devo dire che la soluzione, nonché il problema nella testa del professore, fa molte assunzioni strane. Infatti non solo introduce la variabile membro pos, ma suppone che la variabile posizione effettivamente descriva la posizione dell'elemento nella lista (assicurare questo aspetto quando si fanno operazioni di aggiungere o togliere elementi nella lista richiederebbe \(\displaystyle O(n) \) operazioni ). Per questa ragione trovo che una implementazione seria non dovrebbe fare uso di quella variabile per determinare se un elemento è in una certa posizione (anche perché ti basta materialmente contare).
La seconda cosa strana è che passa la dimensione della lista come parametro. Cosa assolutamente non necessaria.
La terza cosa senza senso è che non si richiede alla funzione di ritornare quanti elementi sono stati inseriti nell'array, perché la funzione dovrebbe tornare [inline]boolean[/inline]? Immagino che quest'ultimo aspetto sia un tuo errore.

Detto questo veniamo alle correzioni. L'uso di un array per pre-calcolare i numeri di Fibonacci è uno spreco di memoria. Ti conviene usare due variabili [inline]int Fib_pre = 1;[/inline] e [inline]int Fib_curr = 1;[/inline], quindi cambiare la condizione dell'[inline]if[/inline] all'interno del ciclo in [inline]if((*L)->pos == Fib_curr)[/inline] e quindi all'interno di esso aggiornare i valori:

if((*L)->pos == Fib_curr)
{
  // altre operazioni da fare all'interno di questo if
  {
    int temp = Fib_curr;
    Fib_curr += Fib_prev;
    Fib_prev = temp; 
  }
}

Al di là di questo suggerimento, il tuo errore è nel modo in cui scorri la lista per eliminare gli elementi. Prova a scrivere una funzione che riceve una lista come input e un intero \(n\) ed elimina l'elemento [inline]n[/inline]-esimo della lista. Confrontando i due codici dovresti riuscire a capire l'errore.

Inoltre ti manca completamente l'inversione dell'array.