Repository 32bit  Forum
Repository 64bit  Wiki

[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.

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

Messaggioda Blallo » lun feb 13, 2012 17:48

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 feb 13, 2012 21:48, modificato 1 volta in totale.
Io sono il detective Arsenio Magret, e porto sempre la camicia TATUATA!
Avatar utente
Blallo
Packager
Packager
 
Messaggi: 3212
Iscritto il: ven ott 12, 2007 10:37
Località: Torino / Torremaggiore (FG)
Nome Cognome: Savino Liguori
Slackware: 14.1 / 12.2
Kernel: 3.12.2-ck
Desktop: Openbox

Re: [C] Quadrato magico: si accettano suggerimenti

Messaggioda targzeta » lun feb 13, 2012 18:13

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
Linux Registered User #454438
Se pensi di essere troppo piccolo per fare la differenza, prova a dormire con una zanzara -- Dalai Lama
20/04/2013 - Io volevo Rodotà
Avatar utente
targzeta
Iper Master
Iper Master
 
Messaggi: 6147
Iscritto il: gio nov 03, 2005 14:05
Località: Carpignano Sal. (LE) <-> Pisa
Nome Cognome: Emanuele Tomasi
Slackware: current
Kernel: latest stable
Desktop: IceWM

Re: [C] Quadrato magico: si accettano suggerimenti

Messaggioda Blallo » lun feb 13, 2012 18:28

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..
Io sono il detective Arsenio Magret, e porto sempre la camicia TATUATA!
Avatar utente
Blallo
Packager
Packager
 
Messaggi: 3212
Iscritto il: ven ott 12, 2007 10:37
Località: Torino / Torremaggiore (FG)
Nome Cognome: Savino Liguori
Slackware: 14.1 / 12.2
Kernel: 3.12.2-ck
Desktop: Openbox

Re: [C] Quadrato magico: si accettano suggerimenti

Messaggioda targzeta » lun feb 13, 2012 18:52

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
Linux Registered User #454438
Se pensi di essere troppo piccolo per fare la differenza, prova a dormire con una zanzara -- Dalai Lama
20/04/2013 - Io volevo Rodotà
Avatar utente
targzeta
Iper Master
Iper Master
 
Messaggi: 6147
Iscritto il: gio nov 03, 2005 14:05
Località: Carpignano Sal. (LE) <-> Pisa
Nome Cognome: Emanuele Tomasi
Slackware: current
Kernel: latest stable
Desktop: IceWM

Re: [C] Quadrato magico: si accettano suggerimenti

Messaggioda targzeta » lun feb 13, 2012 19:56

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
Linux Registered User #454438
Se pensi di essere troppo piccolo per fare la differenza, prova a dormire con una zanzara -- Dalai Lama
20/04/2013 - Io volevo Rodotà
Avatar utente
targzeta
Iper Master
Iper Master
 
Messaggi: 6147
Iscritto il: gio nov 03, 2005 14:05
Località: Carpignano Sal. (LE) <-> Pisa
Nome Cognome: Emanuele Tomasi
Slackware: current
Kernel: latest stable
Desktop: IceWM

Re: [C] Quadrato magico: si accettano suggerimenti

Messaggioda Blallo » lun feb 13, 2012 19:57

Gentilissimo!
Finisco di mangiare e controllo :)
Io sono il detective Arsenio Magret, e porto sempre la camicia TATUATA!
Avatar utente
Blallo
Packager
Packager
 
Messaggi: 3212
Iscritto il: ven ott 12, 2007 10:37
Località: Torino / Torremaggiore (FG)
Nome Cognome: Savino Liguori
Slackware: 14.1 / 12.2
Kernel: 3.12.2-ck
Desktop: Openbox

Re: [C] Quadrato magico: si accettano suggerimenti

Messaggioda Blallo » lun feb 13, 2012 21:48

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
Io sono il detective Arsenio Magret, e porto sempre la camicia TATUATA!
Avatar utente
Blallo
Packager
Packager
 
Messaggi: 3212
Iscritto il: ven ott 12, 2007 10:37
Località: Torino / Torremaggiore (FG)
Nome Cognome: Savino Liguori
Slackware: 14.1 / 12.2
Kernel: 3.12.2-ck
Desktop: Openbox

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

Messaggioda targzeta » mar feb 14, 2012 13:35

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 71 volte
Linux Registered User #454438
Se pensi di essere troppo piccolo per fare la differenza, prova a dormire con una zanzara -- Dalai Lama
20/04/2013 - Io volevo Rodotà
Avatar utente
targzeta
Iper Master
Iper Master
 
Messaggi: 6147
Iscritto il: gio nov 03, 2005 14:05
Località: Carpignano Sal. (LE) <-> Pisa
Nome Cognome: Emanuele Tomasi
Slackware: current
Kernel: latest stable
Desktop: IceWM


Torna a Programmazione

Chi c’è in linea

Visitano il forum: Nessuno e 2 ospiti