anagrame - cautare in sir

Rezolvarea problemelor de matematica prin realizarea unor programe.
XamWaZ
utilizator
utilizator
Mesaje: 9
Membru din: 08 Mar 2012, 02:47

anagrame - cautare in sir

Mesaj de XamWaZ » 09 Mar 2012, 02:01

Am o noua problema care trebuie rezolvata cat mai optim.
Problema e simpla, insa nu stiu daca e cea mai optima solutie.

"Sa se scrie o functie care sa decida daca 2 siruri de numere sunt sau nu anagrame (fiecare numar din primul sir sa se regaseasca in al 2-lea sir)."

Eu m-am gandit sa sortez ambele siruri dupa care sa fac o singura parcurgere pe ambele siruri deodata.
Stiti vreo solutie mai optima din punct de vedere al timpului si a memoriei?

morpheus
utilizator
utilizator
Mesaje: 25
Membru din: 09 Feb 2011, 19:44
Contact:

Re: anagrame - cautare in sir

Mesaj de morpheus » 09 Mar 2012, 14:29

Poti folosi un algoritm inspirat din counting sort, in O(n).

Tii 2 vectori de intregi V1 si V2 (initial ambii vectori contin doar valori egale cu 0).
Construiesti vectorul V1 astfel:
V1[0] -> tine de cate ori apare cifra 0 in sirul 1
V1[1] -> tine de cate ori apare cifra 1 in sirul 1
...
V1[9] -> tine de cate ori apare cifra 9 in sirul 1

Pentru asta, folosesti un algoritm simplu:
pentru fiecare cifra din sirul 1:
V1[cifra]++;

Similar, contruiesti vectorul V2, pentru sirul 2

Apoi compari cei 2 vectori intr-o singura trecere.

Cod: Selectaţi tot

#include <iostream>
#include <cstring>

bool areAnagrams&#40;const char* sir1, const char* sir2&#41;
&#123;
    unsigned int v1&#91;10&#93; = &#123;0&#125;;
    unsigned int v2&#91;10&#93; = &#123;0&#125;;

    for &#40;int i = 0; sir1&#91;i&#93; != '\0'; i++&#41;
    &#123;
        v1&#91;sir1&#91;i&#93; - '0'&#93;++;
    &#125;

    for &#40;int i = 0; sir2&#91;i&#93; != '\0'; i++&#41;
    &#123;
        v2&#91;sir2&#91;i&#93; - '0'&#93;++;
    &#125;

    return std&#58;&#58;memcmp&#40;v1, v2, 10 * sizeof&#40;unsigned int&#41;&#41; == 0;
&#125;

void test&#40;const char* sir1, const char* sir2&#41;
&#123;
    if &#40;areAnagrams&#40;sir1, sir2&#41;&#41;
        std&#58;&#58;cout << sir1 << " and " << sir2 << " are anagrams\n";
    else
        std&#58;&#58;cout << sir1 << " and " << sir2 << " are not anagrams\n";
&#125;

int main&#40;&#41;
&#123;
    // should return true
    test&#40;"123456789", "123456789"&#41;;
    test&#40;"123965487", "123456789"&#41;;
    test&#40;"987654321", "123456789"&#41;;
    test&#40;"9876543219989", "9989123456789"&#41;;

    // should return false
    test&#40;"1239654870", "123456789"&#41;;
    test&#40;"1", "12"&#41;;
    test&#40;"12", "122"&#41;;
    return 0;
&#125;

XamWaZ
utilizator
utilizator
Mesaje: 9
Membru din: 08 Mar 2012, 02:47

Mesaj de XamWaZ » 12 Mar 2012, 13:12

dar asta din cate inteleg eu merge doar daca ai un sir de cifre.
eu insa am numere.
sir1: 2 34 72 29 13
sir2: 34 13 29 2 72

si in cazul asta sunt anagrame. dar daca as avea elementele 12 si 2 in primul sir si 1 si 22 in al 2-lea sir dupa algoritmul de mai sus mi-ar da ca sunt tot anagrame.

morpheus
utilizator
utilizator
Mesaje: 25
Membru din: 09 Feb 2011, 19:44
Contact:

Mesaj de morpheus » 12 Mar 2012, 14:12

Daca ai siruri de intregi, ai mai multe solutii:

1. Poti folosi o structura de date de tip dictionar.
Parcurgi primul sir si adaugi fiecare numar in dictionar.
Parcurgi al doilea sir si cauti fiecare numar din el in dictionar.
Pentru a implementa structura de date poti folosi o tabela de dispersie, de exemplu.

2. Daca vrei o solutie simpla, sortezi cele doua siruri si le compari intr-o singura parcurgere.

XamWaZ
utilizator
utilizator
Mesaje: 9
Membru din: 08 Mar 2012, 02:47

Mesaj de XamWaZ » 12 Mar 2012, 20:05

asa ceva mi s-a mai zis si in alta parte. sa folosesc hash-uri, care sunt tot ca si tabelele de dispersie din cate am inteles eu.
insa nu le stiu folosi.
daca aveti vreun algoritm implementat cu asa ceva mi-ar prinde bine ca sa inteleg cum functioneaza.

morpheus
utilizator
utilizator
Mesaje: 25
Membru din: 09 Feb 2011, 19:44
Contact:

Mesaj de morpheus » 13 Mar 2012, 12:32

Pagina de pe wikipedia este foarte buna:
http://en.wikipedia.org/wiki/Hash_table

Un exemplu de implementare C gasesti pe pagina urmatoare:
http://c-algorithms.git.sourceforge.net ... thms-1.2.0

Uita-te peste:
hash-table.h
hash-table.c
hash-int.h
hash-int.c

Un exemplu de utilizare:
http://c-algorithms.git.sourceforge.net ... thms-1.2.0

Zeus
senior
senior
Mesaje: 424
Membru din: 10 Mai 2012, 17:22

Mesaj de Zeus » 30 Mai 2013, 22:36

Atat hashtable-ul cat si counting-sort sunt mare consumatoare de memorie. Problema asta e clasica... se rezolva cu radix-sort.

Scrie răspuns
  • Subiecte similare
    Răspunsuri
    Vizualizări
    Ultimul mesaj