[C] Quadrato magico: si accettano suggerimenti [RISOLTO]

Forum dedicato alla programmazione.

Moderatore: Staff

Regole del forum
1) Citare in modo preciso il linguaggio di programmazione usato.
2) Se possibile portare un esempio del risultato atteso.
3) Leggere attentamente le risposte ricevute.
4) Scrivere i messaggi con il colore di default, evitare altri colori.
5) Scrivere in Italiano o in Inglese, se possibile grammaticalmente corretto, evitate stili di scrittura poco chiari, quindi nessuna abbreviazione tipo telegramma o scrittura stile SMS o CHAT.
6) Appena registrati è consigliato presentarsi nel forum dedicato.

La non osservanza delle regole porta a provvedimenti di vari tipo da parte dello staff, in particolare la non osservanza della regola 5 porta alla cancellazione del post e alla segnalazione dell'utente. In caso di recidività l'utente rischia il ban temporaneo.
Rispondi
Avatar utente
Blallo
Packager
Packager
Messaggi: 3302
Iscritto il: ven 12 ott 2007, 11:37
Nome Cognome: Savino Liguori
Slackware: 14.2 / 12.2
Kernel: 4.4.14-smp
Desktop: DWM
Località: Torino / Torremaggiore (FG)
Contatta:

[C] Quadrato magico: si accettano suggerimenti [RISOLTO]

Messaggio da Blallo »

Offtopic: Tornare al C dopo Java è dura...
Sto facendo dei temi d'esame, e ho questo sul quadrato magico.
Per chi non lo sapesse, è un quadrato di dimensione N che contiene tutti i numeri da 1 a N^2
Con la particolarità che la somma di ogni riga, ogni colonna e ogni diagonale è N*(N^2 + 1)/2

Sto provando a farla ricorsivamente, ma sto impazzendo, davvero.

Codice: Seleziona tutto

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

int **alloc2d(int n);
int *alloc1d(int n);
int createSquare(int ***square, int **used, int n, int x);
int check(int **square, int n);
void print(int **square, int n);
void freeAll(int **square, int *used, int n);

int main()
{
    int **square, *used;
    int n;

    printf("Inserisci numero:");
    scanf("%d", &n);
    square = alloc2d(n);
    used = alloc1d(n);
    if (createSquare(&square, &used, n, 0) == 1)
        print(square, n);
    freeAll(square, used, n);
    return 0;
}

int **alloc2d(int n) {

    int **sq, i, j;

    if( (sq = (int **) malloc (sizeof(int *)*n)) == NULL ) {
        fprintf(stderr, "Errore allocazione memoria");
        exit(1);
    }

    for (i=0;i<n;i++) {
        if( (sq[i] = (int *) malloc (sizeof(int)*n)) == NULL ) {
            fprintf(stderr, "Errore allocazione memoria");
            exit(1);
        }
    }

    for (i=0;i<n;i++)
        for (j=0;j<n;j++)
            sq[i][j] = 0;

    return sq;
}

int *alloc1d(int n) {

    int *us, i;

    if( (us = (int *) malloc (sizeof(int)*(n*n))) == NULL ) {
        fprintf(stderr, "Errore allocazione memoria");
        exit(1);
    }

    for (i=0;i<(n*n);i++) {
        us[i] = 0;
    }

    return us;
}

int createSquare(int ***square, int **used, int n, int x) {

    int i;

    if ( x == (n*n) ) {
        return check ((*square), n);
    }

    for (i=1;i<(n*n);i++) {
        if (!(*used)[i-1]) {
            (*used)[i-1] = 1;
            (*square)[x/n][x%n] = i;

            if (createSquare(square, used, n, x+1))
                return 1;
            (*used)[i-1] = 0;
        }
    }
    return 0;
}

int check(int **square, int n) {

    int i, j;
    int sum = n*(n*n +1) / 2;
    int tmp = 0;

     //prima diagonale
    for (i=0;i<n;i++) {
        tmp += square[i][i];
    }
    if (tmp == sum) {
        tmp = 0;
    }
    else {
        return 0;
    }

    //seconda diagonale
    for (i=n-1;i>=0;i--) {
        tmp += square[i][i];
    }
    if (tmp == sum) {
        tmp = 0;
    }
    else {
        return 0;
    }

    //righe
    for (i=0;i<n;i++) {
        for (j=0;j<n;j++) {
            tmp += square[i][j];
        }
        if (tmp == sum) {
            tmp = 0;
        }
        else {
            return 0;
        }
    }
    for (i=0;i<n;i++) {
        for (j=0;j<n;j++) {
            tmp += square[j][i];
        }
        if (tmp == sum) {
            tmp = 0;
        }
        else {
            return 0;
        }
    }
    return 1;
}

void print(int **square, int n) {

    int i, j;

    for (i=0;i<n;i++) {
        for (j=0;j<n;j++)
            printf("%2d", square[i][j]);
        printf("\n");
    }
}

void freeAll(int **square, int *used, int n) {

    int i;

    for (i=0;i<n;i++) {
        free(square[i]);
    }
    free(square);
    free(used);

}
Riuscite a darmi un suggerimento? :(
Ultima modifica di Blallo il lun 13 feb 2012, 21:48, modificato 1 volta in totale.

Avatar utente
targzeta
Iper Master
Iper Master
Messaggi: 6629
Iscritto il: gio 3 nov 2005, 14:05
Nome Cognome: Emanuele Tomasi
Slackware: 64-current
Kernel: latest stable
Desktop: IceWM
Località: Carpignano Sal. (LE) <-> Pisa

Re: [C] Quadrato magico: si accettano suggerimenti

Messaggio da targzeta »

Scusa, ma il tuo problema qual'è? Quello di costruire un quadrato con il C (quindi problema di allocazione di memoria o altro), oppure quello di capire un algoritmo che implementa la risoluzione del quadrato magico? Nel secondo caso c'è un algoritmo qui per la costruzione di quadrati magici in cui N è dispari. Per il resto il problema non è mica banale (devi escludere N = 2 perché non ha soluzione). Tu vuoi risolvere il quadrato magico con un algoritmo dell'ordine di N! e ci vuoi andare per tentativi?

Emanuele
Se pensi di essere troppo piccolo per fare la differenza, prova a dormire con una zanzara -- Dalai Lama

Avatar utente
Blallo
Packager
Packager
Messaggi: 3302
Iscritto il: ven 12 ott 2007, 11:37
Nome Cognome: Savino Liguori
Slackware: 14.2 / 12.2
Kernel: 4.4.14-smp
Desktop: DWM
Località: Torino / Torremaggiore (FG)
Contatta:

Re: [C] Quadrato magico: si accettano suggerimenti

Messaggio da Blallo »

Il mio problema non è nemmeno risolverlo, perché l'idea me la suggerisce il testo:
provare tutte le combinazioni (usando un vettore temporaneo per evitare ripetizioni, su cui effettuare poi backtrack) ricorsivamente, cella per cella.
So che è una cosa aberrante dal punto di vista computazionale, ma l'esercitazione verte sulla ricorsione :p
Il mio problema è trovare una implementazione ricorsiva che funzioni, visto che questa non funziona..

Avatar utente
targzeta
Iper Master
Iper Master
Messaggi: 6629
Iscritto il: gio 3 nov 2005, 14:05
Nome Cognome: Emanuele Tomasi
Slackware: 64-current
Kernel: latest stable
Desktop: IceWM
Località: Carpignano Sal. (LE) <-> Pisa

Re: [C] Quadrato magico: si accettano suggerimenti

Messaggio da targzeta »

Quindi il tuo problema si riduce nel trovare un modo per permutare tutti gli elementi di un array. Effettivamente il metodo che mi viene in mente è ricorsivo. Immagino una funzione che prenda in input un sacchetto con dei numeri, quindi ne pesca uno e lo inserisce nella prima cella libera di un array. Quindi richiama se stessa con lo stesso sacchetto meno il numero pescato. Se il sacchetto è vuoto si fa un controllo sull'array prodotto. Se il risultato è positivo la funzione ritorna OK, altrimenti pesca un altro numero (rimettendo quello pescato precedentemente nel sacchetto).

In pratica l'algoritmo sarebbe più o meno questo:

Codice: Seleziona tutto

function pesca(sacchetto, quadrato)
{
  preleva il primo numero dal sacchetto e mettilo nel primo posto libero del quadrato

  se sacchetto vuoto
    ritorna controlla sacchetto

  finché !pesca(sacchetto, quadrato)
    {
     se ho pescato tutti i numeri dal sacchetto
       break
     altrimenti
       preleva un altro numero e rimetti quello vecchio nel sacchetto
    }

  ritorna FALSO
}
In teoria dovrebbe funziona, in pratica... :)

Fammi sapere,
Emanuele
Se pensi di essere troppo piccolo per fare la differenza, prova a dormire con una zanzara -- Dalai Lama

Avatar utente
targzeta
Iper Master
Iper Master
Messaggi: 6629
Iscritto il: gio 3 nov 2005, 14:05
Nome Cognome: Emanuele Tomasi
Slackware: 64-current
Kernel: latest stable
Desktop: IceWM
Località: Carpignano Sal. (LE) <-> Pisa

Re: [C] Quadrato magico: si accettano suggerimenti

Messaggio da targzeta »

Ora non ho tempo per verificare. Ti ho scritto un codice in cinque minuti. Ci sono degli errori da correggere, comunque questo programma ti dovrebbe stampare a video tutte le permutazioni possibili:

Codice: Seleziona tutto

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

#define N 2
#define DIMENSIONE N*N

int crea_quadrato_magico(int *, int *, int);
void stampa_quadrato_magico(int *);

int main(int argc, char **argv)
{
   int *sacchetto, *quadrato, i;

   sacchetto = malloc(sizeof(int) * DIMENSIONE + 1);
   quadrato = malloc(sizeof(int) * DIMENSIONE + 1);

   for ( i = 0; i < DIMENSIONE; i++ )
      sacchetto[i] = i+1;
   sacchetto[i] = 0;

   crea_quadrato_magico(sacchetto, quadrato, 0);

   return 0;
}

int crea_quadrato_magico(int *sacchetto, int *quadrato, int pos)
{
   int i, pescato;

   for ( i = 0; i < DIMENSIONE; i++ )
      {
         if ( sacchetto[i] == 0 )
            continue;
         pescato = sacchetto[i];
         sacchetto[i] = 0;
         quadrato[pos] = pescato;
         crea_quadrato_magico(sacchetto, quadrato, pos+1);
         sacchetto[i] = pescato;
      }

   quadrato[DIMENSIONE] = 0;
   stampa_quadrato_magico(quadrato);

   return 1;
}

void stampa_quadrato_magico(int *quadrato)
{
   int i;

   for ( i = 0; quadrato[i] != 0; i++ )
      printf("%d", quadrato[i]);

   printf("\n");
}
ogni permutazione viene stampata due volte (errore da correggere).

Emanuele
Se pensi di essere troppo piccolo per fare la differenza, prova a dormire con una zanzara -- Dalai Lama

Avatar utente
Blallo
Packager
Packager
Messaggi: 3302
Iscritto il: ven 12 ott 2007, 11:37
Nome Cognome: Savino Liguori
Slackware: 14.2 / 12.2
Kernel: 4.4.14-smp
Desktop: DWM
Località: Torino / Torremaggiore (FG)
Contatta:

Re: [C] Quadrato magico: si accettano suggerimenti

Messaggio da Blallo »

Gentilissimo!
Finisco di mangiare e controllo :)

Avatar utente
Blallo
Packager
Packager
Messaggi: 3302
Iscritto il: ven 12 ott 2007, 11:37
Nome Cognome: Savino Liguori
Slackware: 14.2 / 12.2
Kernel: 4.4.14-smp
Desktop: DWM
Località: Torino / Torremaggiore (FG)
Contatta:

Re: [C] Quadrato magico: si accettano suggerimenti

Messaggio da Blallo »

Il tuo esempio del sacchetto mi è stato utilissimo
Facevo un errore di scorrimento del vettore di elementi.
Questo è il nuovo for:

Codice: Seleziona tutto

    for (i=0;i<(n*n);i++) {
        if (!(*used)[i]) {
            (*used)[i] = 1;
            (*square)[x/n][x%n] = i+1;

            if (createSquare(square, used, n, x+1)) {
                (*used)[i] = 0;
                return 1;
            }
            (*used)[i] = 0;
        }
    }
(non mi ricordo perché sono partito da i=1...)
in più facevo anche un errore di check nella seconda diagonale, che ora è:

Codice: Seleziona tutto

for (i=n-1,j=0;i>=0 && j<n;i--,j++) {
        tmp += square[i][j];
Ti ringrazio per la tempestività, gentilissimo! :D

Avatar utente
targzeta
Iper Master
Iper Master
Messaggi: 6629
Iscritto il: gio 3 nov 2005, 14:05
Nome Cognome: Emanuele Tomasi
Slackware: 64-current
Kernel: latest stable
Desktop: IceWM
Località: Carpignano Sal. (LE) <-> Pisa

Re: [C] Quadrato magico: si accettano suggerimenti [RISOLTO]

Messaggio da targzeta »

Ho trovato 5 minuti ed ho implementato per bene quello che ti ho scritto ieri:

Codice: Seleziona tutto

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

#ifdef MCHECK
#include <mcheck.h>
#endif

#ifndef N
#define N 3
#endif
#define DIMENSIONE N*N
#define COSTANTE_MAGICA N*(DIMENSIONE+1)/2

int crea(int *, int *, int);
int controlla_riga(const int *, int);
int somma_e_controlla(const int *, int, int, int);
int controlla_colonna(const int *, int);
int controlla_diagonali(const int *);
void stampa(const int *);
void debug(const char *, ...);

int main(int argc, char **argv)
{
   int *sacchetto, *quadrato, i;

#ifdef MCHECK
   mtrace();
#endif

   sacchetto = malloc(DIMENSIONE * sizeof(int));
   quadrato = malloc(DIMENSIONE * sizeof(int));

   for ( i = 0; i < DIMENSIONE; i++ )
      sacchetto[i] = i+1;

   crea(sacchetto, quadrato, 0);

   free(sacchetto);
   free(quadrato);

#ifdef MCHECK
   muntrace();
#endif

   return 0;
}

int crea(int *sacchetto, int *quadrato, int pos)
{
   int i, pescato;

   for ( i = 0; i < DIMENSIONE; sacchetto[i++] = pescato )
      {
         pescato = sacchetto[i];
         if ( pescato == 0 )
            continue;
         sacchetto[i] = 0;

         quadrato[pos] = pescato;

         if ( (pos+1) % DIMENSIONE == 0 && ! controlla_riga(quadrato, pos+1) )
            continue;

         if ( (pos+1) > DIMENSIONE - N && ! controlla_colonna(quadrato, pos+1) )
            continue;

         if ( (pos+1) == DIMENSIONE )
            if ( controlla_diagonali(quadrato) )
               {
                  stampa(quadrato);
                  return 1;
               }
            else
               {
                  sacchetto[i] = pescato;
                  return 0;
               }
         else
            if ( crea(sacchetto, quadrato, pos+1) )
               return 1;
      }

   return 0;
}

int controlla_riga(const int *quadrato, int num_elem)
{
   int riga = num_elem / N;

   debug("Controllo riga: ");
   return somma_e_controlla(quadrato, (riga-1) * N, riga * N, 1);
}

int controlla_colonna(const int *quadrato, int num_elem)
{
   int colonna = ( (num_elem) % N != 0 ) ? (num_elem) % N : N;

   debug("Controllo colonna: ");
   return somma_e_controlla(quadrato, colonna-1, DIMENSIONE + colonna - N, N);
}

int controlla_diagonali(const int *quadrato)
{
   debug("Controllo diagonale (principale): ");
   if ( somma_e_controlla(quadrato, 0, DIMENSIONE, N+1) )
      {
         debug("Controllo diagonale (secondaria): ");
         if ( somma_e_controlla(quadrato, N-1, N*(N-1)+1, N-1) )
            return 1;
      }
   return 0;
}

int somma_e_controlla(const int *quadrato, int inizio, int fine, int passo)
{
   int somma, i;

   for ( somma = 0, i = inizio; i < fine; i += passo )
      {
         debug("%d ", quadrato[i]);
         somma += quadrato[i];
      }
   debug("\n");

   if ( somma == COSTANTE_MAGICA )
      {
         debug("ok\n");
         return 1;
      }
   return 0;
}

void stampa(const int *quadrato)
{
   int i;

   for ( i = 0; i < DIMENSIONE; i++ )
      {
         if ( DIMENSIONE > 10 && quadrato[i] < 10 )
            printf(" ");

         printf("%d ", quadrato[i]);

         if ( (i+1)%DIMENSIONE == 0 )
            printf("\n");
      }
   printf("\n");
}

void debug(const char *format, ...)
{
 #ifdef DEBUG
   va_list argv;

   va_start(argv, format);
   vprintf(format, argv);
   va_end(argv);
#endif
}
dato che è lunghetto lo inserisco anche come allegato. Fa un po' di cosette:
  • controlli su memory leak (vedi man di mtrace) se compilato con '-DMCHECK'
  • stampe di debug se compilato con '-DDEBUG'
  • cambiamento della dimensione del quadrato a tempo di compilazione se compilato con '-DN=dimensione' dove dimensione è un numero (se ci metti un numero >= 5 puoi andare a giocare a calcetto prima che finisca)
Se compilato semplicemente con (consiglio sempre di usare le opzioni -Wall e -pedantic del gcc):

Codice: Seleziona tutto

gcc -Wall -pedantic quadrato_magico.c
si ottiene un quadrato magico a 9 celle:

Codice: Seleziona tutto

$> a.out
2 7 6
9 5 1
4 3 8
Il problema è molto stuzzicante e sicuramente si possono trovare dei modi per eliminare un sacco di ramificazioni che moriranno sicuramente. Se guardi il codice, io faccio un controllo ogni qualvolta viene riempita una riga o una colonna, in modo da fermarmi subito, ad esempio, dopo la prima riga se questa già non soddisfa i requisiti.

Emanuele
Allegati
quadrato_magico.c
Programma ricorsivo per la costruzione di un quadrato magico
(3.24 KiB) Scaricato 292 volte
Se pensi di essere troppo piccolo per fare la differenza, prova a dormire con una zanzara -- Dalai Lama

Rispondi