Il quadrato magico è una particolare matrice di dimensione N x N, con N dispari, e tutti valori distinti da 1 a N2, la cui proprietà consiste nell’avere la somma di ogni singola riga uguale, e in più tale somma è uguale alla somma di ogni singola colonna. Vediamo come realizzarne una con dimensione a scelta.
La spiegazione dei singoli passaggi è all’interno dei commenti del codice completo. In questo genere di esercizi dove l’algoritmo è un po’ criptico, consiglio agli alunni di disegnare su foglio una matrice di prova con tanto di coordinate e provare a risolvere il problema su carta, prima che sul pc. L’algoritmo in questione può essere formulato i due modi. Intanto si parte piazzando il numero 1 al centro della prima riga. Dopodiché, ci si sposta di una casella in alto a sinistra in diagonale. Se si strasborda, è come se si riniziasse dal lato opposto. Alcuni testi riportano analoga procedura, ma esattamente opposta, in diagonale in basso a destra. Cambia poco nelle considerazioni che possono essere trasposte facilmente. Noi scegliamo di muoverci in alto a sinistra.
L’esercizio prevede una matrice di base molto grande, con dim 100 ma se ne può usare una piccola parte selezionando la dimensione reale di interesse.
#include <iostream>
#include <iomanip> // std::setw
using namespace std;
#define DIM 100
void stampa(int [DIM][DIM], int);
int main()
{
int n;
int numero = 1;
int quadrato [DIM][DIM];
int riga, colonna;
cout << "Inserisci la dimensione del quadrato magico (numero dispari)" << endl;
cin >> n;
/* Parto dall'esempio 3x3
(0,0) (0,1) (0,2)
(1,0) (1,1) (1,2)
(2,0) (2,1) (2,2)
*/
//inserisco il numero iniziale in posizione prima riga, al centro ovvero (0,1) nella 3x3
quadrato[0][n/2]= 1;
//uso due variabili riga e colonna per spostarmi tra le celle, parto da quella iniziale
riga = 0;
colonna = n/2;
//devo piazzare tutti i numeri all'interno della matrice
for (int i=0; i < (n*n); i++)
{
//sulla riga mi sposto a sinistra
riga = riga - 1;
//controllo se sto sforando con la riga
if (riga < 0)
{
riga = n - 1;
}
//sulla colonna mi sposto in alto
colonna = colonna - 1;
//controllo se sto sforando con la colonna
if (colonna < 0)
{
colonna = n - 1;
}
//potrebbe creare un loop, quindi mi creo uno spostamento ulteriore
//se ho già scritto il numero
if (quadrato[riga][colonna] != 0)
{
//mi devo spostare in diagonale alta verso sinistra
riga = riga + 2;
colonna = colonna + 1;
//controlli per saltare da una diagonale all'altra
if (riga == n+1)
{
riga=1;
}
//controlli per saltare da una diagonale all'altra
if (colonna == n)
{
colonna = 0;
}
numero++;
quadrato[riga][colonna]= numero;
}
else
{
//ok, posso scrivere semplicemente il numero
numero++;
quadrato[riga][colonna]= numero;
}
}
stampa(quadrato, n);
return 0;
}
void stampa(int _matrice[DIM][DIM], int n)
{
for (int i=0; i < n; i++)
{
cout << setw(2);
for (int j=0; j < n; j++)
{
cout << setw(2) << _matrice[i][j] << " ";
}
cout << endl;
}
}
Ultima modifica 14 Gennaio 2022