Pagina 1 di 1

Anagrammi

Inviato: 25 apr 2007, 11:15
da hack
Questo semplice programmino, verifica, date in input 2 parole, se sono anagrammi.

Codice: Seleziona tutto

/* 
Powered by HacK 
www.methack.it 
*/ 

#include <stdio> 

#define DIM 256 

int main() 
{ 
  char p1[DIM] , p2[DIM]; 
  int c, d; // c è il contatore della prima parola, d della seconda 
  int t=0; 
  int ok=1; //variabile di flag 
  int eq=1; 
  printf ("\t###############################\n"); 
  printf ("\t#Programma realizzato da HacK #\n"); 
  printf ("\t###############################\n"); 
  printf ("Inserisci la prima parola : \n"); 
  scanf ("%s" , p1); 
  printf ("Inserisci la seconda parola : \n"); 
  scanf ("%s" , p2); 
  for ( c=0 ; c<=DIM && p1[c]!='\0'; ++c ) //scorro tutta la prima parola 
    { 
      for ( d=0 ; d<=DIM && p2[d]!='\0' ; ++d ) //scorro tutta la seconda 
        { 
          if ( p1[c] = p2[d] ) 
            { 
              p2[c] = '_'; 
              break; //esco dal loop 
            } 
        } 
     } 
  for ( c=0 ; c<=DIM && p2[c]!='\0' ; ++c ) 
    { 
      if ( p2[c]!='_' ) //condizione per cui le due parole non sono anagrammi 
        { 
          ok = 0; // variabile di flag 
          break; 
        } 
    } 
  if ( ok == 1 ) 
    { 
      printf ("Le due parole sono anagrammi!\n"); 
    } else { 
             printf ("Mi dispiace ma le due parole inserite non sono anagrammi!\n"); 
           } 
  system ("PAUSE"); 
  return 0; 
} 

Inviato: 25 apr 2007, 14:15
da MindFlyer
Pubblicità occulta, o...?
Per risollevare il thread, chiedo di trovare un algoritmo che risolva il problema in tempo ottimo (visto che O(n^2) non è il tempo ottimo).

Inviato: 25 apr 2007, 17:35
da fph
Ho qualche dubbio sul funzionamento...

Codice: Seleziona tutto

        ###############################
        #Programma realizzato da HacK #
        ###############################
Inserisci la prima parola : 
abcde
Inserisci la seconda parola : 
abc
Le due parole sono anagrammi!
sh: PAUSE: command not found

Inviato: 25 apr 2007, 17:57
da MindFlyer
Di fatto, assume che le stringhe abbiano la stessa lunghezza. Penso che sia un'assunzione lecita, dato che questo controllo si può fare in tempo lineare. Comunque sì, andrebbe magari scritto nel programma...

Inviato: 25 apr 2007, 18:39
da SkZ
per un verto verso meglio utilizzare la riga di comando

Codice: Seleziona tutto

int main(int argc, char **argv){
int i, j, l;

if(argc!=3) return -1;
for(l=0; argv[1][l]!='\0' && argv[2][l]!='\0'; l++);
if(argv[1][l]!=argv[2][l]) return -1;
for(i=l-1; i>=0; i--)
  for(j=0; j<l; j++)
    if(argv[1][i]==argv[2][j]) {argv[2][j]=argv[2][--l]; break;}
   
return (l)?1:0;
}
ritorna 0 se anagrammi, 1 se non lo sono, 255 se ci sono problemi.

Inviato: 25 apr 2007, 18:49
da MindFlyer
Ok, però è ancora in tempo quadratico nel caso pessimo!
O se vogliamo è pseudo-lineare se poniamo come costante la dimensione dell'alfabeto, ma la cosa non mi piace... :D

Inviato: 25 apr 2007, 19:36
da MateCa
Ok, ci provo io...
Con parole brevi non è il massimo, ma se le parole diventano lunghe dovrebbe essere abbastanza buono...

Codice: Seleziona tutto

#include <stdio>
#include <conio>
#include <stdlib>
#include <string>
#define DIM 100

void main(void)
{
 char parola1[DIM],parola2[DIM];
 int vettore_lettere[2][26],i,j,k;

 //azzeramento dati
 for(k=0;k<26;k++) {vettore_lettere[0][k]=0; vettore_lettere[1][k]=0;}

 //acquisizione parole
 printf("Prima parola: ");
 for(i=0;(parola1[i]=getch())!='\n'; vettore_lettere[0][int(parola1[i])-97]++,i++);
 parola1[i]='\0';
 printf("\nSeconda parola: ");
 for(j=0;(parola2[j]=getch())!='\n'; vettore_lettere[1][int(parola2[j])-97]++,j++);
 parola2[j]='\0';

 //controllo stessa lunghezza
 if(i!=j) {printf("\nNon sono anagrammi"); getch(); exit(0);}

 //controllo se sono anagrammi
 for(k=0;k<26;k++)
 if(vettore_lettere[0][k]!=vettore_lettere[1][k]) {printf("\nNon sono anagrammi"); getch(); exit(0);}

 printf("\nSono anagrammi"); getch(); exit(0);
}
Sono appena tornato dalla gita, spero di non averle sparate troppo grosse :?

EDIT: per modificare la dimensione dell'alfabeto basta cambiare la costante, ma per una buona operatività con i caratteri bisogna sapere a priori quali sono quelli possibili...

Inviato: 26 apr 2007, 00:45
da MindFlyer
Oh, finalmente una versione in tempo O(n+c)! :D
(c è la cardinalità dell'alfabeto...)
Nota però che se c > n log n, conviene ordinare i vettori-stringa e confrontarli.
Tuttavia, con qualche piccola modifica del tuo algoritmo, puoi ridurti a O(n) anche nel caso in cui c > n log n. Riesci a farlo?

Inviato: 27 apr 2007, 19:53
da MateCa
Ce la posso fare, però adesso non ho tempo...appena posso ci provo!

Inviato: 28 apr 2007, 19:15
da MindFlyer
In realtà non so se ho visto bene i dettagli e non sono sicuro al 100% che si possa. Tu pensaci e fammi sapere!

Inviato: 28 apr 2007, 19:37
da MateCa
Questa versione non cambia sostanzialmente l'algoritmo, ma almeno si risparmia un po' su tempo di esecuzione e memoria impiegata...

Codice: Seleziona tutto

#include <stdio>
#include <conio>
#include <stdlib>
#include <string>

void main(void)
{
 char a;
 int vettore_lettere[26],i,j,k;

 //azzeramento dati
 for(k=0;k<26;k++) vettore_lettere[k]=0;

 //acquisizione parole
 printf("Prima parola: ");
 for(i=0;(a=getch())!='\n'; vettore_lettere[int(a)-97]++,i++);
 printf("\nSeconda parola: ");
 for(j=0;(a=getch())!='\n'; vettore_lettere[int(a)-97]--,j++);

 //controllo stessa lunghezza
 if(i!=j) {printf("\nNon sono anagrammi"); getch(); exit(0);}

 //controllo se sono anagrammi
 for(k=0;k<26;k++)
 if(vettore_lettere[k]!=0) {printf("\nNon sono anagrammi"); getch(); exit(0);}

 printf("\nSono anagrammi"); getch(); exit(0);
}
Continuo a pensare :wink:

Inviato: 07 mag 2007, 15:06
da =Betta=
Altrimenti, usando la STL, è sufficiente utilizzare due code con priorità nella quali vengono inserite le due parole e confrontare che siano uguali lettera per lettera:

Codice: Seleziona tutto

#include <stdlib>
#include <stdio>
#include <conio>
#include <queue>
using namespace std;

int main()
{
      priority_queue<char>A;
      priority_queue<char>B;
      char a;
      int i=0, n=0, n2=0;
      printf("Inserire la prima parola\n");
      while((a=getchar())!='\n')
      {
                A.push(a);
                n++;
      }
      printf("\nInserire la seconda parola\n");
      while((a=getchar())!='\n')
      {
                B.push(a);
                n2++;
      }
      if(n==n2)
      {
                while(i<n && A.top()==B.top())
                {
                          A.pop();
                          B.pop();
                          i++;
                }
                if(i==n)
                        printf("Le due parole sono anagrammi\n");
                else
                        printf("Le due parole non sono anagrmmi\n");
      }
      else
               printf("Le due parole sono di differente lunghezza quindi non sono anagrammi\n");
      system("PAUSE");
      return 0;
}

Inviato: 07 mag 2007, 18:05
da MateCa
Con gli opporuni strumenti, tutto è più semplice :D (da ora li saprò usare anch'io :P )
Così si evitano i giri a vuoto, non so se ci si riesce solo con gli array...

PS: ho visto adesso che in tutti i post sono saltati i ".h" nelle librerie. Chi volesse copiare il codice li deve aggiungere.

Inviato: 31 mag 2007, 17:42
da hack
fph ha scritto:Ho qualche dubbio sul funzionamento...

Codice: Seleziona tutto

        ###############################
        #Programma realizzato da HacK #
        ###############################
Inserisci la prima parola : 
abcde
Inserisci la seconda parola : 
abc
Le due parole sono anagrammi!
sh: PAUSE: command not found
il progr funzioa. per la complessità avete ragione.
non ci avevo pensato. :wink: