Informatică, întrebare adresată de oanaroxana3, 8 ani în urmă

Se dă un număr n și n + 1 cuvinte formate din litere mici ale alfabetului englez. Să se afle numărul de cuvinte (excluzându-l pe primul) care sunt anagrame ale primului cuvânt.

Un cuvânt e anagramă a altui cuvânt dacă ele conțin aceleași litere, nu neapărat în aceeași ordine.

Date de intrare
Pe prima linie se află numărul n. Pe următoarele n + 1 linii se află cuvintele.

Date de ieșire
Programul va afișa numărul cerut.

Restricții
1 ≤ n ≤ 50
Lungimea fiecărui cuvânt este mai mică sau egală cu 100 000.
Exemple
Date de intrare Date de ieșire
4 2
server
revers
serve
sserver
server

Acesta este codul meu :

#include
#include
using namespace std;

const int MAX_Lenght = 10000;
int frFrst[MAX_Lenght];
int frSecond[MAX_Lenght];

int main() {
int n, cont = 0;
cin >> n;
char firstWord[MAX_Lenght];
char secondWord[MAX_Lenght];
cin >> firstWord;
for(int i = 0; i < strlen(firstWord); ++i) {
++frFrst[firstWord[i]];
}
for (int i = 0; i < n; ++i) {
cin >> secondWord;
for(int j = 0; j < strlen(secondWord); ++j) {
++frSecond[secondWord[j]];
}
for (char c = 'a'; c <= 'z'; ++c){
if (frFrst[c] == frSecond[c]){
++cont;
}
}
}
cout << cont;
}
Nu fac citirea cum trebuie, ma puteti ajuta cum sa fac citirea astfel sa verific corect.


VxF: N-am înţeles ce încerci să faci acolo. :( Însă mai mult ca sigur că n-o să fie suficient. Pentru a afla dacă 2 șiruri sunt anagrame ai 2 posibilități:
1) generezi un array asociativ cu perechi de literă-număr (ex. „server” => {'s': 1, 'e': 2, 'r': 2, 'v': 1}
2) sortezi literele (ex. „server” => „eerrsv”)
Apoi compari aceste chestii generate.
Cum array asociativ n-aţi învățat, rămâne varianta 2.
andrei750238: Vector de frecventa pe literele din cuvant a incercat sa faca, dar nu prea i-a iesit...
VxF: Ah, cu un sparse array! Doh, m-a derutat dimensiunea MAX_Lenght. Mulţumesc.

Răspunsuri la întrebare

Răspuns de andrei750238
5

Citirea e ok.

► Problemele sunt urmatoarele:

  • Vectorul frSecond nu se reseteaza la fiecare citire a cuvantului secondWord, valoarea de dinainte inca ramane
  • "if (frFrst[c] == frSecond[c]){++cont;" → aici tu incrementezi contorul la fiecare potrivire din vectorii de frecventa. Gresit, trebuie incrementat la final, dupa ce parcurgem toate pozitiile corespunzatoare literelor, daca pana acum nu am avut niciun caz in care cele frFrst[c] sa fie diferit de frSecond[c].

► Sfaturi :

  • Evita folosirea variabilelor globale atunci cand nu sunt necesare. Poti declara vectorii ca numeVector[dimensiune] = {0} pentru a declara vectorul si a seta toate elementele pe 0.
  • Foloseste continue si break pentru a controla mai bine intrectiunile repetitive. Instructiunea continue trece instant la urmatoarea iteratie. Instructiunea break intrerupe ciclul si trece la urmatoare instructiune de dupa ciclul repetitiv.
  • Nu e nevoie sa folosim vectori cu 10000 de pozitii pentru memorarea unui vector de frecventa a literelor. In limba engleza alfabetul are 26 de litere.
  • Daca doua cuvinte nu au acelasi numar de litere atunci ele nu pot fi anagrame. In modul in care arata codul acum nu e o imbunatatire clara de performanta, dar daca am folosi std::string am vedea diferenta. In cazul stringurilor vechi invatate la liceu ar fi ok sa salvezi strlen(firstWord) si strlen(secondWord) in variabile pentru a avea un program ceva mai eficient.
  • Invata sa folosesti debuggerul din IDE pentru a gasi usor problemele cu programele scrise de tine.

► Propunere cod:

#include <iostream>

#include <cstring>

using namespace std;

const int MAX_Lenght = 10000;

int main() {

   int n, contorAnagrame = 0;

   //Citeste numar de cuvinte

   cin >> n;

   //Declara primul si al doilea cuvant

   char firstWord[MAX_Lenght];

   char secondWord[MAX_Lenght];

   //Citeste primul cuvant, determina vectorul de frecventa

   cin >> firstWord;

   int frFrst[26] = { 0 };

   for (int i = 0; i < strlen(firstWord); ++i) {

       ++frFrst[firstWord[i]-'a'];

   }

   //Citeste urmatoarele cuvinte

   for (int i = 0; i < n; ++i) {

       cin >> secondWord;

       //Daca cuvintele au dimensiune diferita sigur nu sunt anagrame, treci la

       //cuvantul urmator

       if (strlen(firstWord) != strlen(secondWord))

           continue;

       //Calculeaza vectorul de frecventa pentru cuvantul curent

       int frSecond[26] = { 0 };

       for (int j = 0; j < strlen(secondWord); ++j) {

           ++frSecond[secondWord[j]-'a'];

       }

       //Verifica daca vectorii de frecventa se potrivesc

       bool suntAnagrame = true;

       for (int c = 0; c < 26; ++c) {

           //Daca pozitia curenta nu se potriveste cuv. nu sunt anagrame,

           //opreste verificarea

           if (frFrst[c] != frSecond[c]) {

               suntAnagrame = false;

               break;

           }

       }

       //Daca cuvintele sunt anagrame mareste contor

       if (suntAnagrame) {

           ++contorAnagrame;

       }

   }

   //Afiseaza rezultat

   cout << contorAnagrame;

}

________________

Daca vrei sa vezi o rezolvare asemanatoare a acestei probleme:

https://brainly.ro/tema/8848425

Anexe:

lucaciucandrei: sa ma bata tata, te-ai complicat nu gluma
Utilizator anonim: :-))
andrei750238: Am modificat codul pe ideea care era deja in intrebare, nu cred ca m-am complicat foarte tare.
Utilizator anonim: Cea mai elegantă rezolvare, părerea mea :)
oanaroxana3: Multumesc pentru rezolvare si explicatii.
oanaroxana3: Am testat si sunt 2 cazuri pe care nu le acopara codul...nu reusesc sa le gasesc..ai idee ce sa fie ?
oanaroxana3: Am descoperit ce era.!
oanaroxana3: m-ai putea ajuta te rog cu un raspuns la tema asta : https://brainly.ro/tema/10347000
Răspuns de VxF
4

Răspuns:

#include <iostream>

#include <cstring>

using namespace std;

const int MAX_Length = 10000;

void sorteaza(char cuvant[])

{

   for (int i = 0; cuvant[i]; i++) {

       char min = i;

       for (int j = i + 1; cuvant[j]; j++) {

           if (cuvant[min] > cuvant[j]) {

               min = j;

           }

       }

       char temporar = cuvant[i];

       cuvant[i] = cuvant[min];

       cuvant[min] = temporar;

   }

}

int main() {

   int n, contorAnagrame = 0;

   cin >> n;

   char firstWord[MAX_Length];

   char secondWord[MAX_Length];

   cin >> firstWord;

   sorteaza(firstWord);

  for (int i = 0; i < n; ++i) {

      cin >> secondWord;

      sorteaza(secondWord);

      if (! strcmp(firstWord, secondWord)) {

          ++contorAnagrame;

      }

  }

  cout << contorAnagrame;

}

Explicație:

Dacă tot am menţionat posibilitatea cu sortarea literelor, l-am implementat.


lucaciucandrei: ineficienta din cap pana-n picioare
Alte întrebări interesante