[C] Esercizio su shift di array

[sophkant]

Ciao a tutti, ho un dubbio esistenziale sugli array e i puntatori.
Il testo dell'esercizio e' il seguente: Scrivere un programma in linguaggio C che, acquisito da tastiera un vettore di N numeri, ne ruoti circolarmente il contenuto di M posizioni e visualizzi la configurazione finale. Il verso della rotazione ed il valore di M sono richiesti come input.

Ho tentato di risolvere il problema con un ciclo for:

if (verso == 1) { // SHIFT VERSO SINISTRA
        printf("Vettore shiftato verso sinistra: \n");
        for (i = 0; i < N; i++) {
            vet[i] = vet[i + posizioni];
            x = vet[i];
            printf("Elemento %d: %d\n", i + 1, x);
        }
    }

se per esempio decido di fare uno shift di 3 posizioni e il vettore e' di [6], gli ultimi 3 elementi del vettore vengono shiftati correttamente di 3 posizioni. i primi 3 invece non risultano shiftati e viene riportato nel print questo numero: -858993460

Scusate per il linguaggio non preciso, sono alle prime armi

PS ovviamente non ho riportato tutto il codice completo ma includeva la lettura delle dimensioni del vettore (N), l'acquisizione degli elementi del vettore, la richiesta all'utente del numero di posizioni da shiftare (posizioni), la richiesta all'utente del verso di rotazione (1 = sinistra, 2 = destra)

[oregon]

Quel codice non funzionerà mai.

Prova a scrivere due funzioni che facciano lo shift a sinistra e lo shift a destra di UN SOLO elemento.

Poi usa un ciclo fir per chiamare tante volte una delle due funzioni, a seconda di quale serve.

[MItaly]

se per esempio decido di fare uno shift di 3 posizioni e il vettore e' di [6], gli ultimi 3 elementi del vettore vengono shiftati correttamente di 3 posizioni. i primi 3 invece non risultano shiftati e viene riportato nel print questo numero: -858993460

Stai sforando l'array in lettura: immagina di avere un array di N=10 elementi e dover shiftare di 5 posizioni; con i >= 5 vai a leggere da oltre la fine dell'array.

Per far funzionare un approccio di questo tipo dovresti come minimo fare il lookup in modulo (ovvero, (i + posizioni) % N), in modo che quando vai a leggere oltre la fine dell'array di fatto ricominci da capo. Tuttavia, anche questo sistema non funziona, perché quando ricominci a leggere dall'inizio stai rileggendo elementi che hai già sovrascritto. Una soluzione semplice può essere fare una copia dell'array originale e usare quella come input:

int rotate(int arr[], int N, int places) {
    int *copy = malloc(N*sizeof(*arr));
    places = (places + N) % N; // riconduce sia rotazione a destra che a sinistra ad una rotazione a sinistra
    for(int i = 0; i < N; ++i) copy[i] = arr[i];
    for(int i = 0; i < N; ++i) arr[i] = copy[(i + places + N) % N];
    free(copy);
}

Questa soluzione è O(N) in tempo e O(N) in spazio. Con poco più sforzo si può renderla O(N) in tempo e O(places) in spazio, copiando solo gli elementi che ci servono:

int rotate(int arr[], int N, int places) {
    places = (places + N) % N; // riconduce sia rotazione a destra che a sinistra ad una rotazione a sinistra
    int *copy = malloc(places*sizeof(*arr));
    for(int i = 0; i < places; ++i) copy[i] = arr[i];
    for(int i = 0; i < N; ++i) {
        int srcIdx = (i + places + N) % N;
        if(srcIdx < i) arr[i] = copy[srcIdx];
        else             arr[i] = arr[srcIdx];
    }
    free(copy);
}

Viceversa, la soluzione proposta da oregon è O(N*places) in tempo, ma O(1) in spazio (non serve storage aggiuntivo).

Va detto però che esiste una soluzione ottimale O(N) in tempo e O(1) in spazio, prova a pensarci...