Forum Sveta kompjutera

Nazad   Forum Sveta kompjutera > Test Run > Programiranje

Programiranje Programski jezici, tehnike, alatke...

Odgovor
 
Alatke vezane za temu Vrste prikaza
Stara 15.5.2012, 23:13   #1
PeTkO
Banned
 
Član od: 6.11.2005.
Lokacija: Iza tebe
Poruke: 2.242
Zahvalnice: 419
Zahvaljeno 298 puta na 192 poruka
Slanje poruke preko Skypea korisniku PeTkO
Određen forumom Uporedjivanje slova u 2 stringa (C++)

Pozdrav

Ceo dan lupam glavom, i nikako ne moze da mi padne ni jedna ideja kako da resim sledeci problem. Treba da uporedim 2 stringa (dve reci), tako da dobijem TRUE (or FALSE) ako se slova iz prve reci nalaze u drugoj.

Primer:

1.Rec: imati
2.Rec: informatika
Resenje: True

Kako ovo da uradim?

Inace, ovo vezbam za prijemni na PMF-u u Nisu, pa je ovo jedan od zadataka, za koje jednostavno nemam ideju. A ima ih jos, tako da ako je neko raspolozan da mi pomogne, bio bih mu zahvalan
PeTkO je offline   Odgovor sa citatom ove poruke
Stara 15.5.2012, 23:18   #2
voodoo_
V.I.P. GNU/Linux
 
Avatar korisnika voodoo_
 
Član od: 1.11.2005.
Poruke: 11.163
Zahvalnice: 2.082
Zahvaljeno 4.922 puta na 2.858 poruka
Određen forumom Re: Uporedjivanje slova u 2 stringa (C++)

Ono što tebi treba bi išlo na sledeću foru:

Kod:
std::string string1 = "imati";
std::string string2 = "informatika";
bool Sadrzi = true;

for (int i = 0; i < string1.length(); i++)
    Sadrzi = Sadrzi && (int(string2.find(string1[i])) >= 0);

std::cout << Sadrzi << std::endl;
Znači, prolazimo kroz string 1 slovo po slovo i tražimo svako slovo u stringu 2. Find vraća lokaciju tog slova (kao tip size_t, koji prebacujemo u int), od nule do length-1 ako ima tog slova u stringu 2, a ako ga nema, vraća -1. Zato će izraz (int(string2.find(string1[i])) >= 0) biti true ako ima slova (jer je rezultat >= 0) ili će biti false ako je -1. Da bi ceo string 1 bio sadržan u string 2, moraju biti SVA njegova slova u stringu 2, pa zato and-ujemo rezultate svake pretrage. Tvoj primer: i postoji (true) & m postoji (true) & a postoji (true) & t postoji (true) & i postoji (true) = true. Ako promeniš string1 u "imzti", biće true & true & false (z ne postoji, rezultat find-a je -1) & true & true = false.

"Sadrži" inicijalno mora biti true, jer ako je false, kasnije and-ovanje sa bilo čim će uvek biti false.

Poslednja ispravka: voodoo_ (16.5.2012 u 0:16)
voodoo_ je offline   Odgovor sa citatom ove poruke
Sledećih 2 korisnika se zahvaljuje korisniku voodoo_ na korisnoj poruci:
EclipsE (16.5.2012), PeTkO (16.5.2012)
Stara 16.5.2012, 0:57   #3
Belphegor
V.I.P. Programiranje
 
Član od: 29.8.2007.
Lokacija: Valjevo
Poruke: 1.349
Zahvalnice: 983
Zahvaljeno 371 puta na 280 poruka
Određen forumom Re: Uporedjivanje slova u 2 stringa (C++)

Mozda nije dozvoljeno koristiti string klasu?

Kod:
char* nadji_char(char c, char* begin, char* end)
{
    for(; begin != end; ++begin)
    {
        if(*begin == c)
            return begin;
    }
    return end;
}

bool sadrzi(char* s1, char* s2, bool poRedosledu = false)
{
    unsigned sz1 = strlen(s1);
    unsigned sz2 = strlen(s2);
    char* end = s2 + sz2;
    for(unsigned i = 0; i < sz1; ++i)
    {
        char* res = find_char(s1[i], s2, end);
        if(poRedosledu)
            s2 = res;
        if(end == res)
            return false;
    }
    return true;
}
...
char* str1 = "imati";
char* str2 = "informatika";

std::cout << std::boolalpha << sadrzi(str1, str2) << std::endl;
Belphegor je offline   Odgovor sa citatom ove poruke
Sledećih 2 korisnika se zahvaljuje korisniku Belphegor na korisnoj poruci:
EclipsE (16.5.2012), PeTkO (16.5.2012)
Stara 16.5.2012, 17:45   #4
voodoo_
V.I.P. GNU/Linux
 
Avatar korisnika voodoo_
 
Član od: 1.11.2005.
Poruke: 11.163
Zahvalnice: 2.082
Zahvaljeno 4.922 puta na 2.858 poruka
Određen forumom Re: Uporedjivanje slova u 2 stringa (C++)

Optimizovana varijanta mog koda:

Kod:
std::string string1 = "imati";
std::string string2 = "informatika";
bool Sadrzi = true;

for (int i = 0; i < string1.length(); i++)
    if (int(string2.find(string1[i])) < 0)
    {
        Sadrzi = false;
        break;
    }

std::cout << Sadrzi << std::endl;
Nema potrebe da and-ujemo, čim naletimo na prvo slovo koje fali, automatski prekidamo traženje. Ako su sva slova prisutna, Sadrzi ostaje true do kraja.
voodoo_ je offline   Odgovor sa citatom ove poruke
Stara 18.5.2012, 19:31   #5
irreal
V.I.P. Programiranje
 
Član od: 9.1.2009.
Lokacija: Beograd, Banovo Brdo
Poruke: 1.157
Zahvalnice: 83
Zahvaljeno 448 puta na 303 poruka
Određen forumom Re: Uporedjivanje slova u 2 stringa (C++)

Citat:
voodoo_ kaže: Pregled poruke
Optimizovana varijanta mog koda:

Kod:
std::string string1 = "imati";
std::string string2 = "informatika";
bool Sadrzi = true;

for (int i = 0; i < string1.length(); i++)
    if (int(string2.find(string1[i])) < 0)
    {
        Sadrzi = false;
        break;
    }

std::cout << Sadrzi << std::endl;
Nema potrebe da and-ujemo, čim naletimo na prvo slovo koje fali, automatski prekidamo traženje. Ako su sva slova prisutna, Sadrzi ostaje true do kraja.
Mislim da ti ne valja resenje.
Nije da je specificno napisano u opisu zadatka u prvom postu, al prilicno sam siguran da ne treba da prihvatis sledecu situaciju:

[ Ananas ] se trazi
u reci
[ ans ]

tvoj program bi prosao kroz svako slovo reci "Ananas" i video da postoji svako od njih u reci [ ans ] jer jedno slovo iz druge reci moze da koristi da upari vise slova iz prve.

dakle, pored svega vec recenog, treba da vodis status za svako slovo reci u kojoj se trazi koji bi ti rekao da li je iskorisceno, ili jos lakse, da svako slovo koje uparis obrises iz reci u kojoj se trazi kako se ne bi naslo sledeci put.
irreal je offline   Odgovor sa citatom ove poruke
Sledećih 2 korisnika se zahvaljuje korisniku irreal na korisnoj poruci:
Belphegor (18.5.2012), voodoo_ (18.5.2012)
Stara 18.5.2012, 23:30   #6
voodoo_
V.I.P. GNU/Linux
 
Avatar korisnika voodoo_
 
Član od: 1.11.2005.
Poruke: 11.163
Zahvalnice: 2.082
Zahvaljeno 4.922 puta na 2.858 poruka
Određen forumom Re: Uporedjivanje slova u 2 stringa (C++)

Kod:
std::string string1 = "imati";
std::string string2 = "informatika";
bool Sadrzi = true;
int rezultat;

for (int i = 0; i < string1.length(); i++)
{
    rezultat = int(string2.find(string1[i]));
    if (rezultat < 0)
    {
        Sadrzi = false;
        break;
    }
    else string2[rezultat] = '#';
}

std::cout << Sadrzi << std::endl;
Kakvo jednostavno a efektno rešenje, bravo
voodoo_ je offline   Odgovor sa citatom ove poruke
Stara 20.5.2012, 16:53   #7
Geomaster
V.I.P. Programiranje
 
Član od: 28.6.2007.
Lokacija: Beograd
Poruke: 2.342
Zahvalnice: 2.836
Zahvaljeno 1.047 puta na 507 poruka
Slanje poruke preko MSN-a korisniku Geomaster Slanje poruke preko Skypea korisniku Geomaster
Određen forumom Re: Uporedjivanje slova u 2 stringa (C++)

Ta rešenja su sva u O(nm), možda mu treba nešto brže? Za velike stringove može mnogo da se otegne.
Kod:
#include <cstring>
#include <cstdio>

int main()
{
  char* string1 = new char[513], *string2 = new char[513];
  int occurrences[256], *occurrences_end = occurrences + 256;

  memset(occurrences, 0, sizeof(occurrences));
  memset(string1, 0, 513 * sizeof(char));
  memset(string2, 0, 513 * sizeof(char));

  fputs("unesite string 1: ", stdout);
  fscanf(stdin, "%512s", string1);

  fputs("unesite string 2: ", stdout);
  fscanf(stdin, "%512s", string2);

  char *p1 = string1, *p2 = string2;
  while (*p1 || *p2) {
    if (*p1) ++occurrences[*p1];
    if (*p2) --occurrences[*p2];
    ++p1, ++p2;
  }

  bool bad = false;
  for (int *p = occurrences; p < occurrences_end; ++p)
    if (*p > 0) {
      fputs("nema svih slova\n", stdout);
      bad = true;
      break;
    }

  if (!bad)
    fputs("sva slova su tu\n", stdout);

  return 0;
}
Složenost O(n + m).

EDIT: Sad tek videh od kad su poruke
Geomaster je offline   Odgovor sa citatom ove poruke
Stara 21.5.2012, 19:31   #8
irreal
V.I.P. Programiranje
 
Član od: 9.1.2009.
Lokacija: Beograd, Banovo Brdo
Poruke: 1.157
Zahvalnice: 83
Zahvaljeno 448 puta na 303 poruka
Određen forumom Re: Uporedjivanje slova u 2 stringa (C++)

Citat:
Geomaster kaže: Pregled poruke
Ta rešenja su sva u O(nm), možda mu treba nešto brže? Za velike stringove može mnogo da se otegne.
Kod:
mlogo koda
Složenost O(n + m).

EDIT: Sad tek videh od kad su poruke
Vrlo jasno i lepo je rekao da vezba zadatke za prijemni.
Dakle, i tebi je vrlo jasno da mu ne treba neka super optimizacija nego razumevanje osnovnih operacija i gradjenje jednostavnih algoritama, to je poenta prijemnog.

Slobodno reci "e, ljudi, vidite kako bi ja to ekstra napisao", nije sramota u tvojim godinama.
irreal je offline   Odgovor sa citatom ove poruke
Stara 21.5.2012, 20:11   #9
Geomaster
V.I.P. Programiranje
 
Član od: 28.6.2007.
Lokacija: Beograd
Poruke: 2.342
Zahvalnice: 2.836
Zahvaljeno 1.047 puta na 507 poruka
Slanje poruke preko MSN-a korisniku Geomaster Slanje poruke preko Skypea korisniku Geomaster
Određen forumom Re: Uporedjivanje slova u 2 stringa (C++)

Nisam obratio pažnju na to za šta mu treba, samo sam video pitanje i spora rešenja i predložio brže. Prost je algoritam, nema tu "vidite kako bih ja to ekstra napisao", moja je samo najbolja namera.
Geomaster je offline   Odgovor sa citatom ove poruke
Sledeći korisnik se zahvaljuje korisniku Geomaster na korisnoj poruci:
chaami (22.5.2012)
Odgovor

Bookmarks sajtovi

Alatke vezane za temu
Vrste prikaza

Vaš status
Ne možete postavljati teme
Ne možete odgovarati na poruke
Ne možete slati priloge uz poruke
Ne možete prepravljati svoje poruke

BB kod: uključeno
Smajliji: uključeno
[IMG] kod: uključeno
HTML kod: isključeno


Slične teme
tema temu započeo forum Odgovora Poslednja poruka
Vicevi Oblivion Cvet kompjutera 5481 27.5.2022 5:52
Prikaz kineskih slova Jovan Verbic Operativni sistemi 3 17.5.2011 12:10
PHP problem-kako izbaciti iz stringa sve karaktere osim slova kovacevicdr Programiranje 7 27.4.2010 1:11
Programi napisani u Clipperu 5.3 - naša slova u XP-u u grafičkom modu Odisejyu Programiranje 0 25.7.2008 22:25
Menjanje slova za hdd i dvd Pjanovic Operativni sistemi 5 3.3.2008 18:35


Sva vremena su po Griniču +2 h. Sada je 7:53.


Powered by vBulletin® verzija 3.8.7
Copyright ©2000–2024, vBulletin Solutions, Inc.
Hosted by Beograd.com