slacky.eu

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?

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

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

Il mio problema è trovare una implementazione ricorsiva che funzioni, visto che questa non funziona..

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

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

Gentilissimo!
Finisco di mangiare e controllo

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!

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

slacky.eu

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

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

Re: [C] Quadrato magico: si accettano suggerimenti

Re: [C] Quadrato magico: si accettano suggerimenti

Re: [C] Quadrato magico: si accettano suggerimenti

Re: [C] Quadrato magico: si accettano suggerimenti

Re: [C] Quadrato magico: si accettano suggerimenti

Re: [C] Quadrato magico: si accettano suggerimenti

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