Corso IN110 Algoritmi e Strutture Dati

Gli esercizi

Testi e soluzioni di alcuni esercizi

Quadrato "magico"

Generare una matrice quadrata di dimensione n di numeri interi casuali. Scrivere una funzione che restituisca 1 se la matrice è un quadrato magico e zero altrimenti. Una matrice n×n è un quadrato magico se la somma degli elementi su ogni riga, su ogni colonna e sulle due diagonali principali è costante.

/*
**  quadrato_magico.c
**
**  Genera in modo casuale una matrice quadrata di dimensione n
**  e verifica se e` un quadrato magico.
**
**  Marco Liverani (liverani@mat.uniroma3.it) - Febbraio 1999
*/

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

#define MAX_N 10

/*
**  genera
**
**  assegna in modo random i valori alla sotto-matrice
**  quadrata di ordine n.
*/

int genera(int *m) {
  int n, i, j;

  srand((unsigned) time(NULL));
  n = rand() % (MAX_N-2) + 2;

  for (i=0; i<n; i++) {
    for (j=0; j<n; j++) {
      *(m+i*MAX_N+j) = rand() % 100;
    }
  }
  return(n);
}


/*
**  stampa_matrice
**
**  visualizza la matrice in output.
*/

void stampa_matrice(int *m, int n) {
  int i, j;
  for (i=0; i<n; i++) {
    for (j=0; j<n; j++) {
      printf("%3d", *(m+i*MAX_N+j));
    }
    printf("\n");
  }
  return;
}


/*
**  verifica
**
**  verifica se la matrice e` un quadrato magico: appena
**  trova una riga o una colonna o una diagonale con una
**  somma diversa esce dalla funzione.
*/

int verifica(int *m, int n) {
  int i, j, r, s, somma;

  r = 1;
  somma = 0;
  for (j=0; j<n; j++) {
    somma = somma + *(m+j);
  }

  /* controllo le righe */
  i = 1;
  while (i<n && r==1) {
    s = 0;
    for (j=0; j<n; j++) {
      s = s + *(m+i*MAX_N+j);
    }
    if (s != somma) {
      r = 0;
    }
    i++;
  }

  /* controllo le colonne */
  j = 0;
  while (j<n && r==1) {
    s = 0;
    for (i=0; i<n; i++) {
      s = s + *(m+i*MAX_N+j);
    }
    if (s != somma) {
      r = 0;
    }
    j++;
  }

  /* controllo la prima diagonale */
  s = 0;
  i = 0;
  while (i<n && r==1) {
    s = s + *(m+i*MAX_N+i);
    i++;
  }
  if (s != somma) {
    r = 0;
  }

  /* controllo la seconda diagonale */
  s = 0;
  i = 0;
  while (i<n && r==1) {
    s = s + *(m + i*MAX_N + (n-i-1));
    i++;
  }
  if (s != somma) {
    r = 0;
  }

  return(r);

}


/*
**  main
**
**  funzione principale che richiama le altre.
*/

int main(void) {
  int M[MAX_N][MAX_N], n;

  n = genera(&M[0][0]);
  if (verifica(&M[0][0],n) == 1) {
    printf("La matrice\n");
    stampa_matrice(&M[0][0], n);
    printf("e' un quadrato magico.\n");
  } else {
    printf("La matrice\n");
    stampa_matrice(&M[0][0], n);
    printf("non e' un quadrato magico.\n");
  }
  return(0);
}

Università degli Studi Roma Tre - Dipartimento di Matematica e Fisica - Corso di laurea in Matematica - Corso di Informatica 1 (IN110)

Author: Marco Liverani - Last modified: Saturday July 13, 2019 - URI: http://www.mat.uniroma3.it/users/liverani/IN1/19990205a.shtml