/*
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;
}
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).
###############################
#Programma realizzato da HacK #
###############################
Inserisci la prima parola :
abcde
Inserisci la seconda parola :
abc
Le due parole sono anagrammi!
sh: PAUSE: command not found
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
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...
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...
#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...
Parlare oscuramente lo sa fare ognuno, ma chiaro pochissimi. (G. Galilei)
Oh, finalmente una versione in tempo O(n+c)!
(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?
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:
#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;
}
Non ho mai incontrato un uomo così ignorante dal quale non abbia potuto imparare qualcosa. - G.Galilei
Con gli opporuni strumenti, tutto è più semplice (da ora li saprò usare anch'io )
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.
Parlare oscuramente lo sa fare ognuno, ma chiaro pochissimi. (G. Galilei)
###############################
#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.
)