Correzione prova pratica del 3 ottobre 2003

Istruzioni:

• FIXME: segnalazione di un errore, non necessariamente sono tutti segnalati e non necessariamente sono tutti presi in considerazione per il voto finale
• TODO: segnala l'assenza di parti di codice
• XXX: segnala qualcosa di non chiaro o inutile ai fini del codice, commenti di ordine generale, errori di battitura o suggerimenti

//XXX (9) imprecisione di linguaggio ed errore implementativo in minimo()
// Singh Rajit Gill, Matricola:149947, email:ra832001@yahoo.it, postazione CAD16

// Data 3-10-2003 - esame di Fondamenti di Informatica A corso di laurea in Ingegneria Informatica


#include <iostream>
#include <string>
#include <cstdlib>
using namespace std;

int minimo(int a, int b, int c) //funzione int che mi srestituisce il minimo fra 3 parametri

{ if ((a<b) && (a<c)) return a;
  if ((b<a) && (b<c)) return b;
  if ((c<a) && (c<b)) return c;
  if (a==b==c) return a; //FIXME questa condizione e' sbagliata l'esame di oggi era informatica non analisi!

} //FIXME e se a==b e a<c ???


int main() {

  char s[21],t[21]; //le stringhe s e t contengono al messimo 20 caratteri.


  cout << " Inserisca 2 stringhe s e t: " << endl;// input delle stringhe s e t (passo 1) //XXX il messaggio non e' chiaro, una per riga?

  cin.getline(s,20);
  cin.getline(t,20);

  int n=strlen(s),m=strlen(t); // calcolo la lunghezza delle stringhe s e t (passo 2)


  if (n==0)  { cout << " La DL e': " << m << endl; exit(0); }
  if (m==0)  { cout << " La DL e': " << n << endl; exit(0); }

  int d[m+1][n+1],i,j; // inizializzazione della matrice d (passo 3)

  for (i=0,j=0; j<=n; j++) d[i][j]=j; //XXX corretto, ma bastava usare 1 variabile d[0][j]=j;

  for (i=1,j=0; i<=m; i++) d[i][j]=i;

  int costo; // passo 4


  for (i=0; i<=n-1; i++) {
    for (j=0; j<=m-1; j++) {

      if (t[j]==s[i]) costo=0; else costo=1; // passo 4.1

      d[j+1][i+1]=minimo(d[j+1][i]+1,d[j][i+1]+1,d[j][i]+costo); // passo 4.2 con richiamo della funzione minimo


    }
  }
  int dl=d[m][n]; // passo 5

  cout << " La distanza di Levenshtein e': " << dl << endl;

}