Newsgroup: it.comp.lang.c++
Titolo: Che ha che non va questo programma?

Questa è la consegna del problema, è il tema d'esame di fondamenti di
informatica A per la facoltà di ingegneria informatica di parma:
-------------------
La "Distanza di Levenshtein" (DL) è un parametro che indica quanto due
stringhe siano simili. In
particolare, date due stringhe s e t, esso rappresenta il numero di
caratteri che devono essere inseriti,
cancellati o modificati in s per renderla identica a t.
L'algoritmo per il calcolo della distanza di Levenshtein è noto dal
1965; i passi risolutivi sono:
1. si prendano in ingresso due stringhe s e t
2. si calcolino n=lunghezza(s) e m=lunghezza(t)
2.1. se n=0 si ha DL=m, stampare DL e terminare
2.2. se m=0 si ha DL=n, stampare DL e terminare
3. inizializzare una matrice d di n+1 colonne e m+1 righe:
3.1. la prima riga della matrice deve contenere i valori da 0 a n
3.2. la prima colonna della matrice deve contenere i valori da 0 a m
4. si prendano in considerazione ciascun carattere di s (s[i] con i
che varia da 0 a n-1) e ciascun
carattere di t (t[j] con j che varia da 0 a m-1)
4.1. se t[j]=s[i] allora costo=0 altrimenti costo=1
4.2. si imposti il valore della cella della matrice d di coordinate
(j+1,i+1) pari al minimo valore di:
· valore della cella di coordinate (j+1,i) + 1
· valore della cella di coordinate (j,i+1) + 1
· valore della cella di coordinate (j,i) + costo
5. DL è uguale al valore della cella della matrice d di coordinate
(m,n); stampare DL e terminare.
Scrivere un programma in C++ che implementi l'algoritmo descritto. Si
ipotizzi una lunghezza
massima ragionevole per le stringhe in ingresso.
Esempio di utilizzo del programma (input in neretto):
Inserire stringa s: ROMBO
Inserire stringa t: TROMBA
La distanza di Levenshtein è 2
------------------------
a parte il fatto che come esame è molto inusuale, perchè richiede un
algoritmo piuttosto complesso ma poi praticamente viene risolto dalla
consegna... non facevano prima a dare un algoritmo meno complesso dove
si ragionasse con la propria testa?
ad ogni modo... io ho scritto un programma seguendo le istruzioni ma
non va... leggete i commenti e rispondete
thx
------------
#include <iostream>
using namespace std;
int lev(char s[], char t[]);//la funzione che contiene l'algoritmo
risolutore
int min(int a, int b, int c);//giusto per semplificare il codice
all'interno di lev(s,t)
int min(int a, int b, int c)
{
 int ris = a;
 if (b < ris)
  ris = b;
 if (c < ris)
  ris = c;
 return ris;
}
int lev(char s[], char t[])
{
 int n = strlen(s), m = strlen(t), matrix[m+1][n+1];
 if (!n)
  return m;
 if (!m)
  return n; //e fin qui va bene, la funzione ritorna il valore
corretto
 for(int i = 0; i < m + 1; i++)
  for(int k = 0; k < n + 1; k++) //c'è un modo più semplice di
inizializzare un array e settare tutti i suoi valori a 0?
   matrix[i][k] = 0;
 for(int i = 0; i < n + 1; i++)
  matrix[0][i] = i;
 for(int i = 0; i < m + 1; i++)
  matrix[i][0] = i;
 int i = 0, j = 0;
 while(1)
 {
  int costo = 0;
  if (s[i] == t[i])
   costo = 0;
  else
   costo = 1;
  matrix[j+1][i+1] = min(matrix[j+1][i] + 1, matrix[j][i+1] + 1,
matrix[j][i] + costo);
  if((i == n-1) && (j == m-1))
   break;
  if(i < n - 1)
   i++;
  if(j < m - 1)
   j++;
 }
 return matrix[m][n]; //la funzione ritorna sempre il valore 1,
perchè????
}
 
int main()
{
 char stringa1[30], stringa2[30];
 cout << "Inserire 2 stringhe separate da un a capo\n";
 gets(stringa1),gets(stringa2);
 cout << "La distanza di Levenshtein è " << lev(stringa1, stringa2) <<
endl;
 system("PAUSE");
 return 0;
}
-----------------------
---
Membro numero 85 del Luigino Fans Club.
Luigino sei tutti noi!
Anche se ti ho plonkato il tuo ricordo sarà per sempre!

  int n = strlen(s), m = strlen(t), matrix[m+1][n+1];
intanto non puoi creare una matrice in questo modo in quanto m e n vengono
calcolati a run time, quindi dovresti crearla dinamicamente con l'operatore
new. Comunque il testo dice di considerare una lunghezza delle stringhe
ragionevole (infatti tu hai scelto 30) per cui penso che sia meglio creare
la matrice con le dimensioni massime (31x31) per poi usare solo la parte
effettivamente richiesta: per cui int matrix[31][31]; (magari invece di
scrivere 30 direttamente nel codice puoi definire un const int MAX_LEN=30; e
usare quello)
-- 
Pela


wrote:

niente da fare... secondo me sbaglio ad interpretare il testo del
problema, il codice mi sembra giusto... anche con #define MAXLEN 30 il
problema è sempre lo stesso, la funzione ritorna sempre il valore 1...


 wrote:
Ciao,
ho provato ad interpretare il testo dell'algoritmo per vedere se
funzionava...
Ovviamente io ho più libertà e non so se questo listato ha una forma che al
tuo professore va bene, ma (es. usa l'algoritmo min_element(), se non puoi
usarlo te lo fai "a manina"!), ma il bello di programmare è proprio
questo... te lo puoi adattare comunque alle tue esigenze stilistiche...
#include <algorithm>
unsigned int Levenshtein(const char* s,const char* t)
{
        unsigned int n=strlen(s), m=strlen(t);
        unsigned int **d, i, j, costo;
        if (!n || !m) return n+m;
        // inizializzare una matrice d di n+1 colonne e m+1 righe:
        d=new unsigned int*[m+1];
        for (i=0;i<m+1;i++) d[i]=new unsigned int[n+1];
        for (i=0;i<n+1;i++) d[0][i]=i;
        for (i=0;i<m+1;i++) d[i][0]=i;
        for (i=0;i<n;i++)
                for (j=0;j<m;j++)
                {
                        if (t[j]==s[i]) costo=0;else costo=1;
                        unsigned int s[] = {
                                d[j+1][i]+1, d[j][i+1]+1, d[j][i]+costo
                        };
                        d[j+1][i+1]= *std::min_element(s,s+3);
                }
        unsigned int dl=d[m][n];
        for (i=0;i<m+1;++i) delete [] d[i];
        delete [] d;
        return dl;
}
L'ho provato con un test come il seguente e mi sembra che funzioni:
#include <iostream>
#include <cstdlib>
#include <string>
using namespace std;
int main(int argc, char* argv[])
{
        string s,t;
        cout << "Calcola la distanza di Levenshtein di due stringhe.\n";
        cout << "Inserisci 1a parola: "; getline(cin,s);
        cout << "Inserisci 2a parola: "; getline(cin,t);
        cout << "La distanza di Levenshtein per s e t e' : "
                << Levenshtein(s.c_str(),t.c_str()) << endl;
        system("pause");
        return 0;
}
Ciao da Paolo e in bocca al lupo per i prossimi esami!
P.S. ti ringrazio, questo algoritmo non lo conoscevo!