Strona 1 z 1
[c] liczenie wyrazow
: 3 mar 2009, o 10:12
autor: hellsing
Dane sa dwa napisy reprezentowane jako ciagi znakow ASCIIZ w tablicazch, przyczym pierwszy(slowo) jest krotszy niz drugi(tekst).
1)napisz procedure w c wyznaczajaca ilosc wystapien slowa w tekscie
2)oblicz zlzonosc obliczeniowa pesymistyczna i optymistyczna zalezna od wuch parametrow m-dlugosc slowa i n-dluosc tekstu.
[c] liczenie wyrazow
: 3 mar 2009, o 17:03
autor: matshadow
1) jak znajdziesz w tekście pierwszą literę słowa, to w forze od 1 do długości słowa sprawdzasz, czy się litery pokrywają. Jak tak, ilość++
w pseudokodzie
tekst w char tekst[], słowo w slowo[]
Kod: Zaznacz cały
bool ok=true;
int il=0;
for(int i=0 to dl_tekstu)
{
bool ok=true,sp=true;
if(tekst[i]==slowo[0])
{
if(i>0 && tekst[i-1]!=) sp=false;//pamiętaj, że znak poprzedzający słowo to znak interpunkcyjny, ja tylko uwzględniłem spację, chcesz to sobie wyifuj inne możliwości :)
for(int j=1 to dl_slowa)
if(slowo[j]!=tekst[i+j])
ok=false;
if(ok&&sp) il++;
}
}
[c] liczenie wyrazow
: 3 mar 2009, o 19:23
autor: hellsing
a co mnie badziej interesuje to jakie sa zlozonosci obliczeniowe tego algorytmu?
[c] liczenie wyrazow
: 3 mar 2009, o 19:49
autor: matshadow
Optymistyczna to \(\displaystyle{ O(n)}\), a pesymistyczna to \(\displaystyle{ O(m\cdot n)}\)