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 (8) errore in calcolo minimo e qualche ingenuita'

//Esame di fondamenti di informatica A

//nome: Mattia  cognome:Pini   Matricola:149725   e_mail:claudiopini@libero.it

// data: 03/10/03  Corso di laurea in ingegneria Elettronica



#include <iostream.h>
#include <string.h>
#include <stdlib.h>

int main()
{

  const int MAXL=20; //definisce la massima lunghezza della stringa

  char s[MAXL+1];
  char t[MAXL+1];//inizializza le due stringhe da leggere

  int dl=0;//dichiara la costante di Levenshtein

  int n,m;
  int minimo=0;//inizializza minimo

  int costo;

  cout<<"\nInserisci la stringa s (massimo venti caratteri)\n";
  cin.getline(s,MAXL+1);                                         //legge stringa s


  cout<<"\nInserisci la stringa t (massimo venti caratteri)\n";
  cin.getline(t,MAXL+1);                                         //legge stringa t


  n=strlen(s);   //lunghezza di s

  m=strlen(t);   //lunghezza di t


  if (n==0)
  {
    dl=m;
    cout<<"\n\nLa distanza di levenshtein e "<<dl<<endl;
    exit(1); 
  }

  else if(m==0) //FIXME l'else e' inutile

  {
    dl=n;
    cout<<"\n\nLa distanza di levenshtein e "<<dl<<endl;
    exit(2);
  }      

  int d[MAXL][MAXL];  //inizializza la matrice  FIXME pero' coerentemente a quanto visto prima doveva utilizzare MAXL+2




  for (int h=0;h<=n;h++)
    d[0][h]=h;             //la prima riga contiene i valori da 0 a n


  for (int u=0;u<=m;u++)
    d[u][0]=u;             //la prima colonna contiene i valori da 0 a m




  //fase del confronto dei caratteri delle due stringhe


  for (int i=0;i<=(n-1);i++)
  {
    for(int j=0;j<=(m-1);j++)
    {
      if(t[j]==s[i]){ 
  costo=0;       //confronta i due caratteri    

      }

      else if(t[j]!=s[i]){  // FIXME se non e' vero che t[j]==s[i] deve essere vero l'opposto (principio del terzo escluso, in occidente c'erano gia' arrivati 2000 e passa anni addietro) 

  costo=1;
      }

      minimo=d[j+1][i]+1;//assegna a minimo il valore della cella           


      if ((d[j][i+1]+1)<minimo){

  minimo=d[j][i+1]+1;}   //sposta se il valore della cella e' piu' basso


      else if( (d[j][i]+costo)<minimo){ //FIXME questo else mi rende il calcolo del minimo sbagliato


  minimo=d[j][i+1]+1;}       //sposta se il valore della cella e' piu' basso


      d[j+1][i+1]=minimo;

      dl=d[m][n];//ultima fase:a questo punto dl contiene il valore desiderato FIXME andava fuori dai cicli, inutile calcolarselo m x n volte all'interno dei due cicli



    }

  }


  cout<<"\n\nLa distanza di Levenshtein e' "<<dl<<endl;

  return 0;
}