Help quadrato magico

Dominik

il 10 feb 2019, 11:02

38 risposte

38 Risposte - Pagina 2

Nippolo
Molto attivo
Iscritto da
mar, 2018
Messaggi:
1239
Re: Help quadrato magico
10 feb 2019, 19:51
enricoscarsissimo ha scritto:
... qui c'è il pezzo di codice che genera il numero
num = rand() % (DIM*DIM) + 1; while(confronto(num,mat)==1) num = rand() % (DIM*DIM) + 1;
Con un do/while potresti rendere il tutto meno ridondante.

In ogni caso quest'approccio al problema non mi sembra il massimo... a parte la poca efficienza, ma non potrebbe accadere che la sequenza di numeri pseudocasuali generata dalla funzione rand() sia tale che l'espressione
```
rand() % (DIM*DIM) + 1
```
non restituisca mai uno dei numeri compresi nell'intervallo [1,DIM]?!

Secondo me per raggiungere lo scopo, invece di ragionare in termini di generare numeri casuali tra loro diversi, sarebbe meglio riempire un vettore con i numeri che vanno da 1 a n^2 e poi "mischiarlo"!

@Dominik
- riguardo alla seguente riga di codice
```
prob = (cont/1000)*100;
```
conosci la differenza tra divisione intera e non?
- consideriamo invece la seguente riga
```
if(sum==sumcol==sumdiag==smd)
```
cosa rappresentano sum e sumcol?
- a tal proposito conosci la relazione che esiste tra "costante magica", ordine e somma degli elementi del quadrato magico?
E
enricoscarsissimo
Utente Attivo
Iscritto da
dic, 2018
Messaggi:
79
Re: Help quadrato magico
10 feb 2019, 20:18
Nippolo ha scritto:
In ogni caso quest'approccio al problema non mi sembra il massimo... a parte la poca efficienza, ma non potrebbe accadere che la sequenza di numeri pseudocasuali generata dalla funzione rand() sia tale che l'espressione

rand() % (DIM*DIM) + 1
non restituisca mai uno dei numeri compresi nell'intervallo [1,DIM]?!
A livello di efficienza non mi pronuncio perchè non ne ho veramente idea, ma di funzionare funziona, non riesco a capire come potrebbe non generare tutti i numeri dell'intervallo visto che prova un'infinità di tentativi (e comunque eseguendolo ci mette un attimo a trovare una tabella).

Comunque a proposito dell'efficienza modesta, ho provato a utilizzarlo per il sudoku e il pc è da 5 minuti che fa girare il programma senza trovare una soluzione
Nippolo
Molto attivo
Iscritto da
mar, 2018
Messaggi:
1239
Re: Help quadrato magico
11 feb 2019, 00:02
Neanche io sono un esperto e non ho mai studiato la complessità computazionale, ma con un pizzico di buon senso si intuisce che come strategia non è molto efficace!

Immagina di avere le 10 carte di denari di un mazzo di carte napoletane e di voler generare una sequenza casuale delle suddette 10 carte. Applicando la tua strategia avremmo le seguenti fasi:
- mischiare le carte;
- rivelare la carta in cima al mazzetto;
- controllare se essa è già presente nella nostra sequenza;
- se lo è pazienza, altrimenti aggiornare la sequenza;
- rimettere la carta nel mazzo e ripetere le fasi precedenti finché la sequenza non è completa.

Invece applicando la mia idea
Nippolo ha scritto:
... sarebbe meglio riempire un vettore con i numeri che vanno da 1 a n^2 e poi "mischiarlo"!
le fasi sarebbero:
- mischiare le carte;
- finito!

ma di funzionare funziona, non riesco a capire come potrebbe non generare tutti i numeri dell'intervallo visto che prova un'infinità di tentativi
La mia più che altro era una "provocazione", in ogni caso qualcuno più esperto saprà dirci se la mia preoccupazione potrebbe in teoria rivelarsi fondata!

L'unica cosa che eseguendolo mi ha lasciato perplesso è che anche su 10000 tentativi non ne trova uno corretto, però c'è da dire che il numero di combinazioni è 9^9>>10000>>numero di quadrati magici
Non sono sicuro di aver capito a pieno il discorso che fai sulle combinazioni, in ogni caso ragioniamo:
- per un cubo di ordine n dovrebbero esserci (n^2)! cubi diversi possibili. Infatti il seguente cubo di ordine 3

1 2 3
4 5 6
7 8 9

può essere "linearizzato" come

1 2 3 4 5 6 7 8 9

e per il suddetto vettore esistono 9! permutazioni;
- da un pdf ho letto che
E’ stato calcolato che, senza contare rotazioni e riflessioni, esistono:
- 1 quadrato magico di ordine 3;
- 880 quadrati magici di ordine 4;
- 275.305.224 quadrati magici di ordine 5.
dove le rotazioni sono 3 (90°, 180°, 270°) e le riflessioni sono 4 (simmetria orizzontale, simmetria verticale, simmetria rispetto alla diagonale principale, simmetria rispetto alla diagonale secondaria), ossia per ogni possibile quadrato ne esistono altri 7 "equivalenti". Quindi contando anche le rotazioni e le riflessioni avremo:
# 8*1 quadrati magici di ordine 3;
# 8*880 quadrati magici di ordine 4;
# 8*275.305.224 quadrati magici di ordine 5.

Da quanto detto in precedenza si deduce che la probabilità che un quadrato di ordine 3 sia magico è:
(8*1)/(3^2)!=0,0022% ossia in media 1/45360

Da quanto detto in precedenza si deduce che la probabilità che un quadrato di ordine 4 sia magico è:
(8*880)/(4^2)!=0,000000034% ossia in media 1/2971987200

Quindi per testare il programma potresti utilizzare i suddetti dati... per esempio ripetendo l'esperimento per 50000 volte su un quadrato di ordine 3 dovresti beccare almeno 1 quadrato magico!

P.S.
Fatemi sapere se ho scritto qualche sciocchezza!
E
enricoscarsissimo
Utente Attivo
Iscritto da
dic, 2018
Messaggi:
79
Re: Help quadrato magico
11 feb 2019, 02:26
Direi che ci siamo
Allegati:

25314_bca1a474b95cc50156634e3f3a84014b.png
D
Dominik
Utente Attivo
Iscritto da
mar, 2018
Messaggi:
67
Re: Help quadrato magico
11 feb 2019, 09:15
enricoscarsissimo ha scritto:

int confronto(int num,int mat[][DIM]){ int i,j; for(i=0; i<DIM; i++){ for(j=0; j<DIM; j++) if(num == mat[i][j]) return 1; } return 0; }
Questo codice a me non va, mi da errore nell' "if"
D
Dominik
Utente Attivo
Iscritto da
mar, 2018
Messaggi:
67
Re: Help quadrato magico
11 feb 2019, 09:27
Nippolo ha scritto:

@Dominik
- riguardo alla seguente riga di codice
prob = (cont/1000)*100;
conosci la differenza tra divisione intera e non?

- consideriamo invece la seguente riga
if(sum==sumcol==sumdiag==smd)
cosa rappresentano sum e sumcol?
- a tal proposito conosci la relazione che esiste tra "costante magica", ordine e somma degli elementi del quadrato magico?
Se parli dal punto di vista di linguaggio C non conosco la differenza tra divisione intera e non.
per quanto riguarda sum e sumcol sono rispettivamente la somma dei numeri lungo le righe e lungo le colonne.
E
enricoscarsissimo
Utente Attivo
Iscritto da
dic, 2018
Messaggi:
79
Re: Help quadrato magico
11 feb 2019, 12:27
Strano, sono due interi, forse hai dichiarato qualcos'altro in modo diverso?

enricoscarsissimo

Utente Attivo

Iscritto da: dic, 2018

Messaggi:: 79

Re: Help quadrato magico

11 feb 2019, 12:31

Qui c'è il codice completo se ti può essere utile:

#include <stdlib.h>
#include <time.h>
#include <stdio.h>
#define DIM 3
void generazione(int mat[][DIM]);
void inizializza(int mat[][DIM]);
void stampa(int mat[][DIM]);
int confronto(int num,int mat[][DIM]);
int magica(int mat[][DIM]);
int main(){
	srand(time(NULL));
	int mat[DIM][DIM],i,flag=0,x,somma=0;
	long int cont=0;
	//int mat2[DIM][DIM]={ {2,7,6},{9,5,1},{4,3,8} };
	cont=0;
	flag=0;
	while(flag==0){
		generazione(mat);
		if(magica(mat)){
			stampa(mat);
			printf("\n");
			printf("cont = %d\n", cont);
			flag=1;
		}
		cont++;
	}
}

void generazione(int mat[][DIM]){
	int num,i,j;
	inizializza(mat);
	for(i=0; i<DIM; i++)
		for(j=0; j<DIM; j++){
			num = rand() % (DIM*DIM) + 1;
			while(confronto(num,mat)==1)
					num = rand() % (DIM*DIM) + 1;
			mat[i][j] = num;
		}
}


void inizializza(int mat[][DIM]){
	int i,j;
	for(i=0; i<DIM; i++)
		for(j=0; j<DIM; j++)
			mat[i][j]=0;
}

void stampa(int mat[][DIM]){
	int i,j;
	for(i=0; i<DIM; i++){
		for(j=0; j<DIM; j++)
			printf("%d ",mat[i][j]);
		printf("\n");
	}
}

int confronto(int num,int mat[][DIM]){
	int i,j;
	for(i=0; i<DIM; i++){
		for(j=0; j<DIM; j++)
			if(num == mat[i][j])
				return 1;
	}
	return 0;

}

int magica(int mat[][DIM]){
	int somma1=0, somma2=0,i,j;
	for(i=0; i<DIM; i++)
		somma1 = somma1 + mat[i][i]; // valori sulla diagonale
		
	for(i=0; i<DIM; i++){			//confronto righe con somma
		for(j=0,somma2=0; j<DIM; j++)
			somma2=somma2+mat[i][j];
		if(somma2!=somma1)
			return 0;
	}

	for(i=0; i<DIM; i++){			//confronto colonne con somma
		for(j=0,somma2=0; j<DIM; j++)
			somma2=somma2+mat[j][i];
		if(somma2!=somma1)
			return 0;
	}
	for(i=0,somma2=0,j=DIM-1; i<DIM; i++,j--)
		somma2=somma2+mat[i][j];
	if(somma2!=somma1)
		return 0;
	return 1;
}

Dominik

Utente Attivo

Iscritto da: mar, 2018

Messaggi:: 67

Re: Help quadrato magico

11 feb 2019, 12:43

enricoscarsissimo ha scritto:

Qui c'è il codice completo se ti può essere utile:

#include <stdlib.h>
#include <time.h>
#include <stdio.h>
#define DIM 3
void generazione(int mat[][DIM]);
void inizializza(int mat[][DIM]);
void stampa(int mat[][DIM]);
int confronto(int num,int mat[][DIM]);
int magica(int mat[][DIM]);
int main(){
	srand(time(NULL));
	int mat[DIM][DIM],i,flag=0,x,somma=0;
	long int cont=0;
	//int mat2[DIM][DIM]={ {2,7,6},{9,5,1},{4,3,8} };
	cont=0;
	flag=0;
	while(flag==0){
		generazione(mat);
		if(magica(mat)){
			stampa(mat);
			printf("\n");
			printf("cont = %d\n", cont);
			flag=1;
		}
		cont++;
	}
}

void generazione(int mat[][DIM]){
	int num,i,j;
	inizializza(mat);
	for(i=0; i<DIM; i++)
		for(j=0; j<DIM; j++){
			num = rand() % (DIM*DIM) + 1;
			while(confronto(num,mat)==1)
					num = rand() % (DIM*DIM) + 1;
			mat[i][j] = num;
		}
}


void inizializza(int mat[][DIM]){
	int i,j;
	for(i=0; i<DIM; i++)
		for(j=0; j<DIM; j++)
			mat[i][j]=0;
}

void stampa(int mat[][DIM]){
	int i,j;
	for(i=0; i<DIM; i++){
		for(j=0; j<DIM; j++)
			printf("%d ",mat[i][j]);
		printf("\n");
	}
}

int confronto(int num,int mat[][DIM]){
	int i,j;
	for(i=0; i<DIM; i++){
		for(j=0; j<DIM; j++)
			if(num == mat[i][j])
				return 1;
	}
	return 0;

}

int magica(int mat[][DIM]){
	int somma1=0, somma2=0,i,j;
	for(i=0; i<DIM; i++)
		somma1 = somma1 + mat[i][i]; // valori sulla diagonale
		
	for(i=0; i<DIM; i++){			//confronto righe con somma
		for(j=0,somma2=0; j<DIM; j++)
			somma2=somma2+mat[i][j];
		if(somma2!=somma1)
			return 0;
	}

	for(i=0; i<DIM; i++){			//confronto colonne con somma
		for(j=0,somma2=0; j<DIM; j++)
			somma2=somma2+mat[j][i];
		if(somma2!=somma1)
			return 0;
	}
	for(i=0,somma2=0,j=DIM-1; i<DIM; i++,j--)
		somma2=somma2+mat[i][j];
	if(somma2!=somma1)
		return 0;
	return 1;
}

Grazie mille per il codice, sei davvero gentilissimo, ma purtroppo ci sono cose che ancora non ho studiato.
Ti posto la parte iniziale del mio codice, con l'aiuto che mi avevi dato prima, se hai un po di tempo gli puoi dare uno sguardo, magari meglio di me capisci dove è l'errore.



#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0

int main ()
{
    int array[10][10];
    int i, j, n, y, l, sum,sumcol, sumdiag,smd=0;
    int prob;
    int cont;
    int num;
    int confronto;
     printf("inserisci le dimensioni della matrice\n");
     scanf("%d", &n);

    cont = 0;
    l= n*n;
for (y=0;y<1000;y++) {
    srand(time(NULL));

	while(confronto(num, array)==1)
    num = rand() % l+ 1;
    int confronto(int num,int array[][]){
	for(i=0; i<n; i++){
		for(j=0; j<n; j++)
			if(num == array[i][j])
				return 1;
	}
	return 0;

}

Mi scuso se ho scritto delle stupidate, ma come già accennato sono un neofita alle prime armi, senza alcun background in materia.

Nippolo
Molto attivo
Iscritto da
mar, 2018
Messaggi:
1239
Re: Help quadrato magico
11 feb 2019, 12:58
Dominik ha scritto:
Se parli dal punto di vista di linguaggio C non conosco la differenza tra divisione intera e non.
Per quanto riguarda la divisione:
- se entrambi gli operandi (dividendo e divisore) sono interi, essa restituisce un intero che coincide con la parte intera del quoziente. Si parla in questo caso di divisione intera;
- se invece almeno uno degli operandi è un valore in virgola mobile (float, double, ...), essa restituisce un valore in virgola mobile che coincide con il quoziente reale. Si parla in questo caso di divisione non intera.

Poi ovviamente una variabile intera non può contenere un valore decimale.

Lancia il seguente codice per renderti conto di quello che intendo:
```
#include <stdio.h>

int main()
{
    int a = 123;
    int b;
    float c;

    b = a/1000*100;
    printf("%d\n", b);

    b = (float)a/1000*100; //Quel (float) si chiama CAST e converte "a" da int a float
    printf("%d\n", b);

    c = a/1000*100;
    printf("%f\n", c);

    c = a/1000.0*100; //In questo caso non ho convertito il dividendo in float, ma il divisore (mettendo .0)
    printf("%f\n", c);
}
```
Dominik ha scritto:
per quanto riguarda sum e sumcol sono rispettivamente la somma dei numeri lungo le righe e lungo le colonne.
Il problema è che qualsiasi sia l'ordine n del quadrato, di diagonale principale e secondaria ce n'è sempre una, ma lo stesso non si può dire delle righe e delle colonne che saranno invece n... nel tuo codice sume sumcol rappresentano rispettivamente la somma dell'ultima riga e dell'ultima colonna, le precedenti righe e colonne invece non vengono proprio prese in considerazione!

In ogni caso quando ti chiedevo

- a tal proposito conosci la relazione che esiste tra "costante magica", ordine e somma degli elementi del quadrato magico?

era proprio per semplificare la parte di codice che si occupa di determinare se il quadrato considerato è magico o meno.
Si dimostra che nel caso di un quadrato magico perfetto la somma magica vale

M = [n(n^2+1)]/2

quindi basta verificare che la somma della generica riga/colonna/diagonale sia uguale ad M, altrimenti possiamo già affermare che il quadrato non è magico.

@enricoscarsissimo
Scusa, ma non ho capito come andrebbero interpretati i dati presenti nell'immagine che hai postato!
In che senso "direi che ci siamo"?
E
enricoscarsissimo
Utente Attivo
Iscritto da
dic, 2018
Messaggi:
79
Re: Help quadrato magico
11 feb 2019, 13:03
Il tuo codice purtroppo non ha proprio senso, come dicevi tu sicuramente ci sono concetti che non conoscevi (le funzioni per prime) per cui le hai messe nel tuo codice un po' alla rinfusa. Ti consiglio di ignorare il mio codice e ripartire da dove eri arrivato, oppure utilizzandolo solo per farti venire delle idee che poi riscrivi da 0. Cerca di guardare le funzioni singolarmente implementandole nel tuo codice all'interno del main. Ti spiego brevemente cosa fanno le funzioni che ho scritto:
```
void generazione(int mat[][DIM]);  //genera la matrice randomica,insieme a "confronto" si assicura sia composta da tutti elementi diversi
void inizializza(int mat[][DIM]);	          //ogni volta che viene chiamata mette nella matrice degli zeri
int confronto(int num,int mat[][DIM]); // guarda num (il numero generato randomicamente tra 1 e 9) e lo confronta con i valori nella matrice, 	 
                                                          //restituisce 0 se il valore non è presente, 1 nel caso opposto
int magica(int mat[][DIM]);                  // controlla se la matrice è magica (cioè guarda se righe colonne e diagonale hanno tutti la somma uguale)
```
@Nippolo Sorry credevo si capisse, semplicemente ti confermavo che facendo la media sui tentativi necessari per trovare una matrice magica ne servono circa 50.000
D
Dominik
Utente Attivo
Iscritto da
mar, 2018
Messaggi:
67
Re: Help quadrato magico
11 feb 2019, 13:23
@Nippolo
Grazie mille Nippolo, sempre il top con le tue spiegazioni.

Per quanto riguarda il ciclo do...while in riferimento alla generazione di numeri casuali all'interno della matrice, potresti darmi qualche dritta, su come impostarlo?
D
Dominik
Utente Attivo
Iscritto da
mar, 2018
Messaggi:
67
Re: Help quadrato magico
11 feb 2019, 13:25
enricoscarsissimo ha scritto:
Il tuo codice purtroppo non ha proprio senso, come dicevi tu sicuramente ci sono concetti che non conoscevi (le funzioni per prime) per cui le hai messe nel tuo codice un po' alla rinfusa. Ti consiglio di ignorare il mio codice e ripartire da dove eri arrivato, oppure utilizzandolo solo per farti venire delle idee che poi riscrivi da 0. Cerca di guardare le funzioni singolarmente implementandole nel tuo codice all'interno del main. Ti spiego brevemente cosa fanno le funzioni che ho scritto:

void generazione(int mat[][DIM]); //genera la matrice randomica,insieme a "confronto" si assicura sia composta da tutti elementi diversi void inizializza(int mat[][DIM]); //ogni volta che viene chiamata mette nella matrice degli zeri int confronto(int num,int mat[][DIM]); // guarda num (il numero generato randomicamente tra 1 e 9) e lo confronta con i valori nella matrice, //restituisce 0 se il valore non è presente, 1 nel caso opposto int magica(int mat[][DIM]); // controlla se la matrice è magica (cioè guarda se righe colonne e diagonale hanno tutti la somma uguale)
Grazie mille, sono sicuramente d'aiuto queste spiegazioni sulle varie funzioni, anche se credo di procedere scrivendo un unica funzione per questo esercizio.

Nippolo

Molto attivo

Iscritto da: mar, 2018

Messaggi:: 1239

Re: Help quadrato magico

11 feb 2019, 14:10

Ho provato a svolgerlo anche io:

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

#define N 10
#define T 50000

void scambia(unsigned int *a, unsigned int *b)
{
    unsigned int temp = *a;
    *a = *b;
    *b = temp;
}

void mischia_quadrato(unsigned int m[N][N], unsigned int v[N * N], unsigned int n)
{
    unsigned int i;
    for(i = n * n - 1; i > 0; --i)
    {
        scambia(&v[i], &v[rand() % (i + 1)]);
    }
    for(i = 0; i < n; ++i)
    {
        for(unsigned int j = 0; j < n; ++j)
        {
            m[i][j] = v[i * n + j];
        }
    }
}

int magico(unsigned int m[N][N], unsigned int n, unsigned int M)
{
    unsigned int i;
    unsigned int j;
    unsigned int somma;
    for(i = 0; i < n; ++i)
    {
        somma = 0;
        for(j = 0; j < n; ++j)
        {
            somma += m[i][j];
        }
        if(somma != M)
        {
            return 0;
        }
    }
    for(j = 0; j < n; ++j)
    {
        somma = 0;
        for(i = 0; i < n; ++i)
        {
            somma += m[i][j];
        }
        if(somma != M)
        {
            return 0;
        }
    }
    somma = 0;
    for(i = 0; i < n; ++i)
    {
        somma += m[i][i];
    }
    if(somma != M)
    {
        return 0;
    }
    somma = 0;
    for(i = 0; i < n; ++i)
    {
        somma += m[n - i - 1][i];
    }
    if(somma != M)
    {
        return 0;
    }
    return 1;
}

void mostra_quadrato(unsigned int m[N][N], unsigned int n)
{
    unsigned int j;
    printf("\n");
    for(unsigned int i = 0; i < n; ++i)
    {
        for(j = 0; j < n; ++j)
        {
            printf("%d ", m[i][j]);
        }
        printf("\n");
    }
}

int main()
{
    srand(time(0));
    unsigned int m[N][N];
    unsigned int v[N];
    unsigned int i;
    unsigned int n;
    do
    {
        printf("n: ");
        scanf("%d", &n);
    }
    while(n > N);
    unsigned int M = n * (n * n + 1) / 2;
    unsigned int cont = 0;
    for(unsigned int i = 0; i < n * n; ++i)
    {
        v[i] = i + 1;
    }
    for(i = 0; i < T; ++i)
    {
        mischia_quadrato(m, v, n);
        if(magico(m, n, M))
        {
            ++cont;
            mostra_quadrato(m, n);
        }
    }
    printf("\nSONO STATI GENERATI %d QUADRATI MAGICI SU %d\n", cont, T);
    return 0;
}

magari puoi trarne qualche spunto. Se qualcosa non ti è chiaro chiedi pure.

@enricoscarsissimo
intendevo questo con "mischiare"!

D
Dominik
Utente Attivo
Iscritto da
mar, 2018
Messaggi:
67
Re: Help quadrato magico
11 feb 2019, 14:26
Nippolo ha scritto:

Mi sembra giustissimo il tuo utilizzo di "mischiare" più che "generare", visto che matematicamente i numeri all'interno della matrice sono strettamente correlati alla dimensione n^2.

Devi accedere o registrarti per scrivere nel forum

38 risposte