[TEMĂ] Determinare anagrame
Last Updated: May 23 2015 11:42, Started by
sftpdt
, May 23 2015 07:06
·
0
#1
Posted 23 May 2015 - 07:06
Salut. Se dă un şir de caractere ce conţine cuvinte formate din litere mici ale alfabetului englez, separate prin unul sau mai multe spații. Să se determine câte cuvinte din sir sunt anagrame ale ultimului cuvânt, fără a fi identice cu acesta.
Exemplu: Intrare said: arc ingrat din granit car argint arc rating rac argint Iesire said: 3 Ce am făcut arată cam aşa: #include <iostream> #include <algorithm> #include <cstring> using namespace std; typedef char matrice_cuvinte[100][30]; int determinare_anagrame(matrice_cuvinte matrice, int numar_cuvinte) { int suma = 0; char copie_ulitimul_cuvant[40]; strcpy(copie_ulitimul_cuvant, matrice[numar_cuvinte - 1]); sort(copie_ulitimul_cuvant, copie_ulitimul_cuvant + strlen(copie_ulitimul_cuvant)); for (int i = 0; i < numar_cuvinte - 1; i++) { if (strcmp(matrice[i], matrice[numar_cuvinte - 1]) != 0) // nu este deja identic cu ultimul cuvant din matrice { sort(matrice[i], matrice[i] + strlen(matrice[i])); suma += (strcmp(matrice[i], copie_ulitimul_cuvant) == 0); } } return suma; } void construire_matrice_cuvinte(matrice_cuvinte &matrice, char sir_cuvinte[], int &numar_cuvinte) { numar_cuvinte = 0; char *p = strtok(sir_cuvinte, " "); while (p != NULL) { strcpy(matrice[numar_cuvinte++], p); p = strtok(NULL, " "); } } int main(void) { char sir_cuvinte[300]; matrice_cuvinte matrice; int numar_cuvinte; cin.get(sir_cuvinte, 255); construire_matrice_cuvinte(matrice, sir_cuvinte, numar_cuvinte); cout << determinare_anagrame(matrice, numar_cuvinte); return 0; } Însă primesc 60 puncte (pic un test). Edited by sftpdt, 23 May 2015 - 07:08. |
#4
Posted 23 May 2015 - 07:28
eu din codul tau nu reusesc sa inteleg unde determini daca un cuvant este anagrama altui cuvant.
|
#5
Posted 23 May 2015 - 07:30
Le sortez pe amândouă şi verific dacă sunt identice.
int determinare_anagrame(matrice_cuvinte matrice, int numar_cuvinte) { int suma = 0; char copie_ulitimul_cuvant[40]; strcpy(copie_ulitimul_cuvant, matrice[numar_cuvinte - 1]); sort(copie_ulitimul_cuvant, copie_ulitimul_cuvant + strlen(copie_ulitimul_cuvant)); // aici sortez copia ultimului cuvant for (int i = 0; i < numar_cuvinte - 1; i++) { if (strcmp(matrice[i], matrice[numar_cuvinte - 1]) != 0) // nu este deja identic cu ultimul cuvant din matrice { sort(matrice[i], matrice[i] + strlen(matrice[i])); // sortez cuvantul actual suma += (strcmp(matrice[i], copie_ulitimul_cuvant) == 0); // verific daca sunt identice } } return suma; } Edited by sftpdt, 23 May 2015 - 07:31. |
#6
Posted 23 May 2015 - 07:43
aia e functia care iti numara,
return sumaeu vreau doar partea care deterinama daca doua cuvinte sunt anagrame mai pe romaneste, separa o problema de alta |
#7
Posted 23 May 2015 - 07:54
bool Cuvinte_anagrame(char cuvant1[], char cuvant2[]) { char copie1[100], copie2[100]; strcpy(copie1, cuvant1); strcpy(copie2, cuvant2); sort(copie1, copie1 + strlen(copie1)); sort(copie2, copie2 + strlen(copie2)); return ( strcmp(copie1, copie2) == 0 ); } |
#8
Posted 23 May 2015 - 09:47
Faci prea multe copii inutile. Eu as salva tot inputul intr-un singur string, si intr-un alt array pozitiile inceputurilor cuvintelor (daca cuvintele sunt mereu despartite de un singur caracter) inca din timpul citirii.
Pentru claritatea algoritmului, as salva si pozitiile ultimelor litere ale tuturor cuvintelor intr-un alt array. Dupa ce am scanat ultimul cuvant, stiu exact unde sa sar in interiorul acestui string citit si ce caractere sa compar cu care caractere. Totul manual, fara functii. Daca vrei ceva mai avansat, te poti gandi la un algoritm de hashing bazat pe numere prime. Nu ar trebui sa ai coliziuni. Nu e un algoritm neaparat mai eficient, doar mai provocator dpv intelectual. Daca vrei si mai avansat, te poti inspira de aici: https://github.com/s...aster/bitgram.c Edited by OriginalCopy, 23 May 2015 - 10:38. |
#10
Posted 23 May 2015 - 11:11
OriginalCopy, on 23 mai 2015 - 09:47, said: Mai fac copii deoarece nu se ştie când mai am nevoie de respectiva variabilă.. Mersi de sfat . Se pare că nu luam 100p din cauza dimensiunilor tablourilor. Le-am mai mărit şi e ok. dani.user, on 23 mai 2015 - 11:03, said:
De ce nu folosesti std::string? Să mai exersez cu char*. Am anul viitor bacalaureatul şi nu cred că am voie cu string (sau vector/map/algorithm/etc) ... din comoditatea multor profesori cărora le este lene să înveţe lucruri noi şi se bazează pe aceeaşi materie. |
|
#11
Posted 23 May 2015 - 11:40
Citind codul tau ma tot intreb ce-i matricea de cuvinte. Mai degraba e un vector de cuvinte.
Rezolvarea mi se pare mult mai eleganta urmand niste pasi simpli:
#include <iostream> #include <sstream> #include <vector> #include <cstring> using namespace std; bool isAnagram(const string& first, const string& second) { if ((first == second) || (first.size() != second.size())) { return false; } int letterOccurences[256] = {0}; int reference[256] = {0}; for (auto& c : first) { ++letterOccurences[c]; } for (auto& c : second) { --letterOccurences[c]; } return memcmp(letterOccurences, reference, sizeof(reference)) == 0; } vector<string> getWords(const string& sentence) { vector<string> result; istringstream stream(sentence); string word; while (getline(stream, word, ' ')) { result.push_back(word); } return result; } int count_anagrams_of_last_word(const string& sentence) { int result = 0; auto words = getWords(sentence); auto& lastWord = words[words.size() - 1]; for (int i = 0; i < words.size() - 1; i++) { if (isAnagram(words[i], lastWord)) { ++result; } } return result; } int main() { cout << count_anagrams_of_last_word("arc ingrat din granit car argint arc rating rac argint") << endl; return 0; } |
#12
Posted 23 May 2015 - 11:42
Anunturi
Bun venit pe Forumul Softpedia!
▶ 0 user(s) are reading this topic
0 members, 0 guests, 0 anonymous users