[Risolto][C] Matrice circolare

[Wolf1989]

Buonasera a tutti ,

dovrei creare una matrice circolare.
Cioè che le celle della prima riga (colonna) sono adiacenti alla cella dell'ultima riga (colonna).
Io mi devo poter muovere nelle 4 direzioni NORD/SUD/EST/OVEST senza mai avere i problemi sui bordi.
Per quanto riguarda la parte inferiore ho risolto il problema usando il modulo del numero delle righe (colonne) e tutto funziona bene.
Per quanto riguarda la parte superiore ho dei problemi perchè gli indici diventano negativi e il modulo non ha senso.
Come posso fare?

[M_A_W_ 1968]

L'operatore % del C è notoriamente implementation-dependent riguardo al segno del resto. Di fatto non fornisce il modulo (che sarebbe perfettamente definitivo su tutti gli interi relativi), ma semplicemente il resto della divisione intera tra numeri strettamente positivi.
Per ovviare a ciò, esistono appositi idiomi di decremento a saturazione, tali che quando si raggiunge il valore zero, il predecessore viene forzato ad essere il limite superiore dell'intervallo desiderato.

Riporto qui per mera comodità il codice di esempio che utilizza l'operatore % a scopo didattico, ma invito caldamente a leggere per intero il thread linkato sopra e le relative spiegazioni, che sarebbe inutile replicare qui.

Codice: Seleziona tutto

#include <stdio.h>

#define ARRAY_SIZE  31
#define TEST_VAL    (3 * ARRAY_SIZE)

int main()
{
    size_t cnt;
    size_t idx = 0;

    for (cnt = 0; cnt < TEST_VAL; ++cnt)
    {
        ++idx %= ARRAY_SIZE +1;
        printf("[1.%03d] idx = %d\n", cnt +1, idx);
    }

    puts("-.-.-.-.-.-.-.-.-.-");
    
    for (idx = ARRAY_SIZE /2, cnt = 0; cnt < TEST_VAL; ++cnt)
    {
        --idx %= ARRAY_SIZE +1;
        printf("[2.%03d] idx = %d\n", cnt +1, idx);
    }
    
    return(0);
}

[SuperStep]

allora, puoi risolvere in diversi modi:

MODO 1 ) o fai in modo che ogni elemento riga/colonna sia una struttura che abbia i puntatori relativamente a NORD,SUD,EST,OVEST e quindi ti trovi una marea di puntatori.

MODO 2) scrivi delle funzioni che restituiscono un puntatore e che prendono in ingresso la matrice la riga e la colonna dove fai gli adattamenti se stai sfornado per restituire l'elemento "Opposto".

qualcosa del tipo

Codice: Seleziona tutto

MatrixElement * nordElement(Matrix * matrixStruct, int row, int col){
    if(row == 0){
        return &(matrixStruct->matrix[matrixStruct->row_height - 1][col]);
    }
    return &(matrixStruct->matrix[row - 1][col]);
}

oppure:

Codice: Seleziona tutto

MatrixElement * nordElement(Matrix * matrixStruct, MatrixCoordinates coordinates){
    if(coordinates.row == 0){
        return &(matrixStruct->matrix[matrixStruct->row_height - 1][coordinates.col]);
    }
    return &(matrixStruct->matrix[coordinates.row - 1][coordinates.col]);
}

[gila75]

@M_A_W, siccome ho l'abitudine di provare e conservare i tuoi codici e di altri utenti segnalo in compilazione:

Codice: Seleziona tutto

3d.c:13:15: error: lvalue required as left operand of assignment
3d.c:21:15: error: lvalue required as left operand of assignment

[M_A_W_ 1968]

@M_A_W, siccome ho l'abitudine di provare e conservare i tuoi codici e di altri utenti segnalo in compilazione:

Codice: Seleziona tutto

3d.c:13:15: error: lvalue required as left operand of assignment
3d.c:21:15: error: lvalue required as left operand of assignment

Bravo Gila. E siccome il tuo compilatore preferito non accetta l'idioma

Codice: Seleziona tutto

++idx %= ARRAY_SIZE +1;

...tu come lo correggi per renderlo compilabile, senza peggiorarne le prestazioni?

[gila75]

A dire il vero M_A_W non compilandomi non so l'output che dovrebbe produrre.
Comunque da quello che ho capito, dovrebbe mettere dei numeri progressivi:

Codice: Seleziona tutto

[1.001] idx = 1
[1.002] idx = 2
[1.003] idx = 3
[1.004] idx = 4
[1.005] idx = 5
[1.006] idx = 6
[1.007] idx = 7
[1.008] idx = 8

il terzo decimale proggredisce, ma una volta arrivati al nostro limite cioè:

Codice: Seleziona tutto

ARRAY_SIZE  31

i decimali devono ancora progredire, ma l'indice deve tornare a 1
Considerando che il programma cicla per 3 volte tanto la dimensione dell'array.
Quindi io ci ho provato :

Codice: Seleziona tutto

#include <stdio.h>

#define ARRAY_SIZE  31
#define TEST_VAL    (3 * ARRAY_SIZE)

int main()
{
    size_t cnt;
    size_t idx = 0;

    for (cnt = 0; cnt < TEST_VAL; ++cnt)
    {    
            
         idx=idx%ARRAY_SIZE +1;
        printf("[1.%03d] idx = %d\n", cnt +1, idx);
    }

    puts("-.-.-.-.-.-.-.-.-.-");
    
    for (idx = ARRAY_SIZE /2, cnt = 0; cnt < TEST_VAL; ++cnt)
    {   
        
        idx=idx%ARRAY_SIZE +1;
        printf("[2.%03d] idx = %d\n", cnt +1, idx);
    }
    
    return(0);
}

e anche l'output dovrebbe andar bene, se ho capito in modo corretto ciò che deve fare il programma:

Codice: Seleziona tutto

[1.001] idx = 1
[1.002] idx = 2
[1.003] idx = 3
[1.004] idx = 4
[1.005] idx = 5
[1.006] idx = 6
[1.007] idx = 7
[1.008] idx = 8
[1.009] idx = 9
[1.010] idx = 10
[1.011] idx = 11
[1.012] idx = 12
[1.013] idx = 13
[1.014] idx = 14
[1.015] idx = 15
[1.016] idx = 16
[1.017] idx = 17
[1.018] idx = 18
[1.019] idx = 19
[1.020] idx = 20
[1.021] idx = 21
[1.022] idx = 22
[1.023] idx = 23
[1.024] idx = 24
[1.025] idx = 25
[1.026] idx = 26
[1.027] idx = 27
[1.028] idx = 28
[1.029] idx = 29
[1.030] idx = 30
[1.031] idx = 31
[1.032] idx = 1
[1.033] idx = 2
[1.034] idx = 3
[1.035] idx = 4
[1.036] idx = 5
[1.037] idx = 6
[1.038] idx = 7
[1.039] idx = 8
[1.040] idx = 9
[1.041] idx = 10
[1.042] idx = 11
[1.043] idx = 12
[1.044] idx = 13
[1.045] idx = 14
[1.046] idx = 15
[1.047] idx = 16
[1.048] idx = 17
[1.049] idx = 18
[1.050] idx = 19
[1.051] idx = 20
[1.052] idx = 21
[1.053] idx = 22
[1.054] idx = 23
[1.055] idx = 24
[1.056] idx = 25
[1.057] idx = 26
[1.058] idx = 27
[1.059] idx = 28
[1.060] idx = 29
[1.061] idx = 30
[1.062] idx = 31
[1.063] idx = 1
[1.064] idx = 2
[1.065] idx = 3
[1.066] idx = 4
[1.067] idx = 5
[1.068] idx = 6
[1.069] idx = 7
[1.070] idx = 8
[1.071] idx = 9
[1.072] idx = 10
[1.073] idx = 11
[1.074] idx = 12
[1.075] idx = 13
[1.076] idx = 14
[1.077] idx = 15
[1.078] idx = 16
[1.079] idx = 17
[1.080] idx = 18
[1.081] idx = 19
[1.082] idx = 20
[1.083] idx = 21
[1.084] idx = 22
[1.085] idx = 23
[1.086] idx = 24
[1.087] idx = 25
[1.088] idx = 26
[1.089] idx = 27
[1.090] idx = 28
[1.091] idx = 29
[1.092] idx = 30
[1.093] idx = 31
-.-.-.-.-.-.-.-.-.-
[2.001] idx = 16
[2.002] idx = 17
[2.003] idx = 18
[2.004] idx = 19
[2.005] idx = 20
[2.006] idx = 21
[2.007] idx = 22
[2.008] idx = 23
[2.009] idx = 24
[2.010] idx = 25
[2.011] idx = 26
[2.012] idx = 27
[2.013] idx = 28
[2.014] idx = 29
[2.015] idx = 30
[2.016] idx = 31
[2.017] idx = 1
[2.018] idx = 2
[2.019] idx = 3
[2.020] idx = 4
[2.021] idx = 5
[2.022] idx = 6
[2.023] idx = 7
[2.024] idx = 8
[2.025] idx = 9
[2.026] idx = 10
[2.027] idx = 11
[2.028] idx = 12
[2.029] idx = 13
[2.030] idx = 14
[2.031] idx = 15
[2.032] idx = 16
[2.033] idx = 17
[2.034] idx = 18
[2.035] idx = 19
[2.036] idx = 20
[2.037] idx = 21
[2.038] idx = 22
[2.039] idx = 23
[2.040] idx = 24
[2.041] idx = 25
[2.042] idx = 26
[2.043] idx = 27
[2.044] idx = 28
[2.045] idx = 29
[2.046] idx = 30
[2.047] idx = 31
[2.048] idx = 1
[2.049] idx = 2
[2.050] idx = 3
[2.051] idx = 4
[2.052] idx = 5
[2.053] idx = 6
[2.054] idx = 7
[2.055] idx = 8
[2.056] idx = 9
[2.057] idx = 10
[2.058] idx = 11
[2.059] idx = 12
[2.060] idx = 13
[2.061] idx = 14
[2.062] idx = 15
[2.063] idx = 16
[2.064] idx = 17
[2.065] idx = 18
[2.066] idx = 19
[2.067] idx = 20
[2.068] idx = 21
[2.069] idx = 22
[2.070] idx = 23
[2.071] idx = 24
[2.072] idx = 25
[2.073] idx = 26
[2.074] idx = 27
[2.075] idx = 28
[2.076] idx = 29
[2.077] idx = 30
[2.078] idx = 31
[2.079] idx = 1
[2.080] idx = 2
[2.081] idx = 3
[2.082] idx = 4
[2.083] idx = 5
[2.084] idx = 6
[2.085] idx = 7
[2.086] idx = 8
[2.087] idx = 9
[2.088] idx = 10
[2.089] idx = 11
[2.090] idx = 12
[2.091] idx = 13
[2.092] idx = 14
[2.093] idx = 15

Si almeno un po' clemente

[M_A_W_ 1968]

Si almeno un po' clemente

Clemente è uscito.
Ma per come lo hai scritto tu non può produrre quell'output. L'indice va pure incrementato (risp. decrementato) da qualche parte. Tipicamente nella for(), anche se stiamo violando le regole di stile più diffuse.

Codice: Seleziona tutto

#include <stdio.h>

#define ARRAY_SIZE  31
#define TEST_VAL    (3 * ARRAY_SIZE)

int main()
{
    size_t cnt;
    size_t idx;

    for(idx = 6, cnt = 0; cnt < TEST_VAL; ++idx, ++cnt)
    {
        idx %= ARRAY_SIZE +1;
        printf("[1.%03d] idx = %d\n", cnt +1, idx);
    }

    puts("");

    for(idx = ARRAY_SIZE -8, cnt = 0; cnt < TEST_VAL; --idx, ++cnt)
    {
        idx %= ARRAY_SIZE +1;
        printf("[2.%03d] idx = %d\n", cnt +1, idx);
    }

    return(0);
}

[vbextreme]

tu come lo correggi per renderlo compilabile

tecnicamente ha ragione il compilatore.
incremento prima idx e poi eseguo il modulo o prima eseguo il modulo e poi incremento idx?
penso che il tuo compilatore maw, prima incrementi idx e poi esegua il modulo ma non capisco cosa possa centrare con le ottimizzazioni?????
c'è un comando assembly che incrementa ed esegue il modulo in un colpo solo?
e a quel punto il compilatore non potrebbe riconoscerlo anche con un codice piu standard?

[M_A_W_ 1968]

tu come lo correggi per renderlo compilabile

tecnicamente ha ragione il compilatore.

Dopo il 1999, sì...

Ma come spesso avviene, quel codice è assai più arcaico e quell'idioma era lì per altri motivi. Spesso (specialmente in passato) occorreva davvero forzare la mano dei compilatori per ottenere semplicemente il risultato voluto.

[gila75]

MAW ok,ci ho provato e anche un Po di fretta e male.
Ma l' output che ho postato è quello che risulta, non l'ho scritto io a mano.oggi alle 14 guardo il tuo output
Idx si incrementa in base al risultato del modulo.
Può essere che non vada bene lo stesso ,non insisto,ma prova a compilare ed eseguire.
Poi,può essere che il programma non debba fare quello,ma ripeto,non potendo compilare
Il tuo esempio, non sono sicuro di ciò che deve fare con precisione

[vbextreme]

@gila :

Codice: Seleziona tutto

int main()
{
    size_t cnt;
    size_t idx = 0;

    for (cnt = 0; cnt < TEST_VAL; ++cnt)
    {
		++idx;
        idx %= ARRAY_SIZE +1;
        printf("[1.%03d] idx = %d\n", cnt +1, idx);
    }

    puts("-.-.-.-.-.-.-.-.-.-");
    
    for (idx = ARRAY_SIZE /2, cnt = 0; cnt < TEST_VAL; ++cnt)
    {
		--idx;
        idx %= ARRAY_SIZE +1;
        printf("[2.%03d] idx = %d\n", cnt +1, idx);
    }
    
    return(0);
}

@MAW Turbo c++ o Digital Mars?

[M_A_W_ 1968]

@MAW Turbo c++ o Digital Mars?

L'idea del riuso del codice si applica naturalmente anche agli esempi da forum. Quindi stimando rapidamente l'epoca del sorgente originale dal quale proviene quello snippet, direi che si trattava quasi certamente del glorioso Turbo C++ 3.1, eventualmente poi ricompilato con BCC5. Credo decisamente che né DM né OpenWatcom accettino (ancora) quella sintassi, che in effetti è stata oggetto di lunghe discussioni (ma mantiene comunque un suo fascino "offuscato", sebbene contrario alle norme di stile e oggi anche agli standard).

[M_A_W_ 1968]

Ma l' output che ho postato è quello che risulta, non l'ho scritto io a mano.oggi alle 14 guardo il tuo output
Idx si incrementa in base al risultato del modulo.

Sì, il tuo output è certamente coerente con quello che hai scritto, ma non è il medesimo output dell'esempio!

Hai dimenticato una coppia di parentesi e quindi il risultato è difforme da quello desiderato, ossia generare ciclicamente tutti e soli gli interi non segnati compresi tra zero e ARRAY_SIZE, estremi inclusi.

Codice: Seleziona tutto

Y:\>mod
[1.001] idx = 0
[1.002] idx = 1
[1.003] idx = 2
[1.004] idx = 3
[1.005] idx = 4
[1.006] idx = 5
[1.007] idx = 6
[1.008] idx = 7
[1.009] idx = 8
[1.010] idx = 9
[1.011] idx = 10
[1.012] idx = 11
[1.013] idx = 12
[1.014] idx = 13
[1.015] idx = 14
[1.016] idx = 15
[1.017] idx = 16
[1.018] idx = 17
[1.019] idx = 18
[1.020] idx = 19
[1.021] idx = 20
[1.022] idx = 21
[1.023] idx = 22
[1.024] idx = 23
[1.025] idx = 24
[1.026] idx = 25
[1.027] idx = 26
[1.028] idx = 27
[1.029] idx = 28
[1.030] idx = 29
[1.031] idx = 30
[1.032] idx = 31
[1.033] idx = 0
[1.034] idx = 1
[1.035] idx = 2
[1.036] idx = 3
[1.037] idx = 4
[1.038] idx = 5
[1.039] idx = 6
[1.040] idx = 7
[1.041] idx = 8
[1.042] idx = 9
[1.043] idx = 10
[1.044] idx = 11
[1.045] idx = 12
[1.046] idx = 13
[1.047] idx = 14
[1.048] idx = 15
[1.049] idx = 16
[1.050] idx = 17
[1.051] idx = 18
[1.052] idx = 19
[1.053] idx = 20
[1.054] idx = 21
[1.055] idx = 22
[1.056] idx = 23
[1.057] idx = 24
[1.058] idx = 25
[1.059] idx = 26
[1.060] idx = 27
[1.061] idx = 28
[1.062] idx = 29
[1.063] idx = 30
[1.064] idx = 31
[1.065] idx = 0
[1.066] idx = 1
[1.067] idx = 2
[1.068] idx = 3
[1.069] idx = 4
[1.070] idx = 5
[1.071] idx = 6
[1.072] idx = 7
[1.073] idx = 8
[1.074] idx = 9
[1.075] idx = 10
[1.076] idx = 11
[1.077] idx = 12
[1.078] idx = 13
[1.079] idx = 14
[1.080] idx = 15
[1.081] idx = 16
[1.082] idx = 17
[1.083] idx = 18
[1.084] idx = 19
[1.085] idx = 20
[1.086] idx = 21
[1.087] idx = 22
[1.088] idx = 23
[1.089] idx = 24
[1.090] idx = 25
[1.091] idx = 26
[1.092] idx = 27
[1.093] idx = 28

[2.001] idx = 23
[2.002] idx = 22
[2.003] idx = 21
[2.004] idx = 20
[2.005] idx = 19
[2.006] idx = 18
[2.007] idx = 17
[2.008] idx = 16
[2.009] idx = 15
[2.010] idx = 14
[2.011] idx = 13
[2.012] idx = 12
[2.013] idx = 11
[2.014] idx = 10
[2.015] idx = 9
[2.016] idx = 8
[2.017] idx = 7
[2.018] idx = 6
[2.019] idx = 5
[2.020] idx = 4
[2.021] idx = 3
[2.022] idx = 2
[2.023] idx = 1
[2.024] idx = 0
[2.025] idx = 31
[2.026] idx = 30
[2.027] idx = 29
[2.028] idx = 28
[2.029] idx = 27
[2.030] idx = 26
[2.031] idx = 25
[2.032] idx = 24
[2.033] idx = 23
[2.034] idx = 22
[2.035] idx = 21
[2.036] idx = 20
[2.037] idx = 19
[2.038] idx = 18
[2.039] idx = 17
[2.040] idx = 16
[2.041] idx = 15
[2.042] idx = 14
[2.043] idx = 13
[2.044] idx = 12
[2.045] idx = 11
[2.046] idx = 10
[2.047] idx = 9
[2.048] idx = 8
[2.049] idx = 7
[2.050] idx = 6
[2.051] idx = 5
[2.052] idx = 4
[2.053] idx = 3
[2.054] idx = 2
[2.055] idx = 1
[2.056] idx = 0
[2.057] idx = 31
[2.058] idx = 30
[2.059] idx = 29
[2.060] idx = 28
[2.061] idx = 27
[2.062] idx = 26
[2.063] idx = 25
[2.064] idx = 24
[2.065] idx = 23
[2.066] idx = 22
[2.067] idx = 21
[2.068] idx = 20
[2.069] idx = 19
[2.070] idx = 18
[2.071] idx = 17
[2.072] idx = 16
[2.073] idx = 15
[2.074] idx = 14
[2.075] idx = 13
[2.076] idx = 12
[2.077] idx = 11
[2.078] idx = 10
[2.079] idx = 9
[2.080] idx = 8
[2.081] idx = 7
[2.082] idx = 6
[2.083] idx = 5
[2.084] idx = 4
[2.085] idx = 3
[2.086] idx = 2
[2.087] idx = 1
[2.088] idx = 0
[2.089] idx = 31
[2.090] idx = 30
[2.091] idx = 29
[2.092] idx = 28
[2.093] idx = 27

[gila75]

Ok capito M_A_W.
Inizialmente avevo implementato anche io un incremento di idx nel ciclo.
Poi mi pareva si ottenesse lo stesso risultato col "trucco" che ho proposto...,ma non ho considerato gli estremi dell'array.

[M_A_W_ 1968]

In ogni caso, a prescindere dalle idiosincrasie sintattiche pre e post C'99 (uno standard assolutamente fallimentare dal punto di vista dell'unificazione e dell'adozione generalizzata, ora reso obsoleto dal C'11 che per il momento riesce ad essere perfino meno incisivo e pervasivo), il concetto è che sulla schiacciante maggioranza delle CPU l'indice viene mantenuto in un registro entro i vari loop, e il tutto si risolve in:

- Incremento (risp. decremento) unitario dell'indice - singola istruzione atomica;
- AND con costante immediata, calcolata a tempo di compilazione, che azzera tutti i bit più alti non pertinenti - altra istruzione atomica;
- Indirizzamento indicizzato dell'array, secondo le modalità ammesse della ISA. Terza e ultima istruzione atomica, eventualmente penalizzata da un allungamento dei tempi di esecuzione sulle piattaforme con scarsa ortogonalità del set di istruzioni (inclusi x86 e suoi cloni AMD).

Il tutto, naturalmente, sotto l'ipotesi che il decremento di un registro con valore nullo ne comporti il rollover al massimo valore esprimibile con l'ampiezza di registro, il che è un requisito di design del silicio con validità pressoché universale, a prescindere dal comportamento di flag accessori.

[gila75]

Però,non capisco, poi quando si farà vivo l'utente sentiamo che dice ma:
Il codice da te proposto, ora ho capito, ne abbiamo parlato (me lo sono salvato) ecc...
Però, per un array circolare, non si può utilizzare una semplice memmove() ?
3 elementi
100,25,81
inserisco 28 e diventa: 28,100,25
Con memmove() credo sia fattibilissimo. Mi pare di aver parlato con Vb tempo fa di una cosa simile, ma non ricordo il 3d,magari lui si ricorda
M_A_W, non prendermi per quello che non vuole imparare idiomi nuovi, ma non ho capito bene rispetto ad una memmove()

[M_A_W_ 1968]

L'OP deve solo muoversi su una matrice esistente senza soluzione di continuità, in modo tale che la prima riga appaia contigua all'ultima, e così per le colonne. Come se avvolgessimo attorno ad un cilindro la matrice, ordinatamente per ciascuna dimensione, in modo da poterla percorrere appunto circolarmente (la circonferenza ha la meravigliosa caratteristica di essere finita ma non limitata).

Quindi incrementando l'indice sull'ultima riga deve "magicamente" saltare alla prima, decrementando la colonna zero il risultato deve essere l'ultima colonna, eccetera. Ovviamente senza annegare nelle if() e senza assurde penalità prestazionali.

[gila75]

capito, grazie

[Wolf1989]

Grazie mille a tutti per le risposte, sono state utilissime.
Sopratutto quella di SuperStep che ha risolto il mio problema .
Ancora Grazie

[SuperStep]

figurati, però in genere qui si usa che [RISOLTO] si mette prima del titolo, a destra si nota poco.