Corso IN110 Algoritmi e Strutture Dati

Gli esercizi

Testi e soluzioni di alcuni esercizi

Matrici incastrate

Generare in modo casuale una matrice A di ordine 10×15, con valori interi 0 e 1. Sia B la seguente matrice quadrata di ordine 3:

    | 0 1 0 |
B = | 1 1 1 |
    | 0 1 0 |

Verificare se in A è possibile collocare B in modo tale che nessun elemento di valore 1 di B si vada a sovrapporre ad un elemento di valore 1 in A. In caso affermativo stampare le coordinate di riga e di colonna in A in cui verrebbe collocato l'elemento B(0,0).

/*
**  matrici.c
**
**  Generare in modo casuale una matrice A di ordine 10x15, con valori
**  interi 0 e 1. Sia B la seguente matrice quadrata di ordine 3:
**            | 0 1 0 |
**        B = | 1 1 1 |
**            | 0 1 0 |
**  Verificare se in A e' possibile collocare B in modo tale che nessun
**  elemento di valore 1 di B si vada a sovrapporre ad un elemento di
**  valore 1 in A. In caso affermativo stampare le coordinate di riga e
**  di colonna in A in cui verrebbe collocato l'elemento B(0,0).
**
**  Marco Liverani (liverani@mat.uniroma3.it) - Giugno 2001
*/

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

#define RIGHE 10
#define COLONNE 15

void genera(int A[RIGHE][COLONNE]) {
  int i, j;

  srand((unsigned)time(NULL));
  for (i=0; i<RIGHE; i++) {
    for (j=0; j<COLONNE; j++) {
      A[i][j] = rand()%2;
    }
  }
  return;
}

int verifica(int A[RIGHE][COLONNE], int B[3][3], int *x, int *y) {
  int i, j, h, k, flag;

  flag = 0;
  for (i=0; i<RIGHE-2 && flag==0; i++) {
    for (j=0; j<COLONNE-2 && flag==0; j++) {
      flag = 1;
      for (h=0; h<3 && flag==1; h++)
        for (k=0; k<3 && flag==1; k++)
          if (B[h][k] == 1 && A[i+h][j+k] == 1)
            flag = 0;
    }
  }
  if (flag) {
    *x = j;
    *y = i;
  }
  return(flag);
}

void stampa_matrice(int A[RIGHE][COLONNE]) {
  int i, j;

  for (i=0; i<RIGHE; i++) {
    for (j=0; j<COLONNE; j++)
      printf("%d ", A[i][j]);
    printf("\n");
  }
  return;
}

int main(void) {
  int A[RIGHE][COLONNE], B[3][3], x, y;

  B[0][0] = 0; B[0][1] = 1; B[0][2] = 0;
  B[1][0] = 1; B[1][1] = 1; B[1][2] = 1;
  B[2][0] = 0; B[2][1] = 1; B[2][2] = 0;
  genera(A);
  stampa_matrice(A);
  if (verifica(A, B, &x, &y)) {
    printf("La matrice B si incastra in A collocandola");
    printf("a partire dalla posizione (%d,%d).\n", y, x);
  } else {
    printf("La matrice B non si incastra nella matrice A.\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/20010615a.shtml