Programowanie - pytania, problemy, przykłady programów

[Harrolfo 0]

Czyli co konkretnie mam zrobić?

[Nufiko 0]

Dnia 03.06.2010 o 19:27, Harrolfo napisał:

Czyli co konkretnie mam zrobić?

Bierzesz kolejne znaki z pierwszego wyrazu i jeśli dany znak zgadza się się ze znakiem z wyrazu drugiego to sprawdzasz czy kolejny znak z wyrazu pierwszego zgadza się z następnym znakiem kolejnego wyrazu i tak aż do końca któregoś stringa jak skończy ci się string 2 to znaczy, że znalazłeś cały wyraz, jak string pierwszy to możesz zakończyć szukanie. Jak się znak nie zgodzi z następnym to sprawdzasz czy się zgadza z pierwszym drugiego stringa a jak nie to bierzesz kolejny i rozpoczynasz szukanie od początku.

[Harrolfo 0]

Ok, ale jakie polecenie za to odpowiada?

[Nufiko 0]

Dnia 03.06.2010 o 19:52, Harrolfo napisał:

Ok, ale jakie polecenie za to odpowiada?

Za co ma odpowiadać jak za sprawdzenie czy znak to koniec stringa to zwykłe porównanie z ''\0'' a jak chodzi o długość stringa to sizeof() - dokładną składnię sobie wyszukaj bo funkcja potrafi podać różne rzeczy w zależności co będzie jej parametrem.

[Harrolfo 0]

Mi chodzi jak brac kolejne znaki ze stringa?

[ziptofaf 2]

Dnia 03.06.2010 o 19:57, Harrolfo napisał:

Mi chodzi jak brac kolejne znaki ze stringa?

String to tak naprawdę rozbudowana tablica char. Czyli (taki pseudokod):

string slowo="krowa";
slowo[0]="k";
slowo[1]="r";

Musisz zrobić dwukrotną pętle for - najpierw wyszukuje w danym ciągu pierwszą literę z podanego przez ciebie wyrazu, a potem sprawdza czy pozostałe również się zgadzają. Można by w środku umieścić coś pokroju licznika, którego wartość rośnie o 1 z każdym odnalezionym znakiem. W momencie gdy licznik=wielkość_poszukiwanego_ciągu, znaczy to, że szukane słowo zostało znalezione. Dość prymitywne, ale zadziała.

[Nufiko 0]

Dnia 03.06.2010 o 19:57, Harrolfo napisał:

Mi chodzi jak brac kolejne znaki ze stringa?

Ja po prostu używam tablicy znaków (*char) i z niej czytam kolejne znaki jak ze zwykłej tablicy i z tego co wiem to tak działa też w typie string ale nie gwarantuję bo jego nigdy nie używałem.

[Harrolfo 0]

Nic z tego nie rozumiem. Mo○zecie mi po prostu wkleić te polecenia do mojego kodu źródłowego? Przeanalizuję sobie wtedy i chyba sie domyślę...

[ziptofaf 2]

Dnia 03.06.2010 o 20:12, Harrolfo napisał:

Nic z tego nie rozumiem. Mo○zecie mi po prostu wkleić te polecenia do mojego kodu
źródłowego? Przeanalizuję sobie wtedy i chyba sie domyślę...

Nie chciałem ci psuć zabawy nad twoim kodem, więc:

#include <cstdlib>
#include <iostream>
#include <string>
using namespace std;

int main()
{
string slowo;
cin >> slowo;
string szukane;
cin >> szukane;
int sprawdzenie=0;
int licznik=0;
for (int a=0; a<=slowo.size(); a++){ // wyszukiwanie pierwszego wystapienia pierwszego znaku -
// dosc prostackie, ale dziala
if (szukane[0]==slowo[a]){licznik=a+1; sprawdzenie=1; break;}
}

for (int a=1; a<=szukane.size()-1; a++, licznik++)
{
cout << "szukane: " << szukane[a] << endl;
cout << "slowo: " << slowo[licznik] << endl;
if (szukane[a]==slowo[licznik]){sprawdzenie++;}
}
if (sprawdzenie==szukane.size()){cout << "poszukiwane slowo wystepuje w twoim ciagu";}
system("PAUSE");
return EXIT_SUCCESS;
}


Ten program (zdaję sobie sprawę z jego ułomności :)) szuka danego słowa w ciągu. Najpierw sprawdza, gdzie znajduje się pierwsza poszukiwana litera. Potem w kolejnej pętli sprawdza, czy reszta liter też się zgadza. I, jak widać, działa.

[Harrolfo 0]

No ale jak wpisuję np
lala
la
to pokazuje
a
a

[ziptofaf 2]

Dnia 03.06.2010 o 21:21, Harrolfo napisał:

No ale jak wpisuję np
lala
la
to pokazuje
a
a

No tak, ale na końcu wyświetla, czy całe poszukiwane słowo występuje w ciągu. Te a a to zrobiłem tylko tak dla ułatwienia, żeby pokazać jak działa pętla. Widać, że porównuje tam drugą literę ciągu z drugą poszukiwanego wyrazu.

[Harrolfo 0]

Ech, napisz mi po prostu jak ma wyglądać ten kod źródłowy, aby rozwiązał mi zadanie, bo ja już nie mam do tego siły. Staram się to zrobić od poniedziałku i mi nie wychodzi...

[ziptofaf 2]

Dnia 03.06.2010 o 21:39, Harrolfo napisał:

Ech, napisz mi po prostu jak ma wyglądać ten kod źródłowy, aby rozwiązał mi zadanie,
bo ja już nie mam do tego siły. Staram się to zrobić od poniedziałku i mi nie wychodzi...

To może tak - co konkretnie ma robić ten program? Bo jakoś nie mogłem się tego nigdzie w twoich postach doczytać ;)

[Harrolfo 0]

Ma pobierać dwa napisy (np. "lalala" i "la"). Nastepnie wyszukać drugi napis w pierwszym i wypisać po przecinku numery linii, w których jest ten napis. Czyli dla podanych w tym nawiasie napisów powinno być:
0, 2, 4, bo znaki w napisie sa numerowane od 0

[Psych0 0]

Dnia 03.06.2010 o 22:33, Harrolfo napisał:

Ma pobierać dwa napisy (np. "lalala" i "la"). Nastepnie wyszukać drugi napis w pierwszym
i wypisać po przecinku numery linii, w których jest ten napis. Czyli dla podanych w tym
nawiasie napisów powinno być:
0, 2, 4, bo znaki w napisie sa numerowane od 0

Może spróbuj zastosować KMP, choć nie wiem czy to jedyne wyjście.

[ziptofaf 2]

Dnia 03.06.2010 o 22:33, Harrolfo napisał:

Ma pobierać dwa napisy (np. "lalala" i "la"). Nastepnie wyszukać drugi napis w pierwszym
i wypisać po przecinku numery linii, w których jest ten napis. Czyli dla podanych w tym
nawiasie napisów powinno być:
0, 2, 4, bo znaki w napisie sa numerowane od 0

#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main()
{
size_t znaleziono;
string slowo;
cin >> slowo;
string szukane;
cin >> szukane;
int chwilowa_pozycja=0;
int popychacz=0;


for (int a=0; a<=(slowo.size()/szukane.size()); a++){
if (slowo.size()-chwilowa_pozycja<szukane.size()){break;}
znaleziono=slowo.find(szukane, chwilowa_pozycja);
chwilowa_pozycja=int(znaleziono);
if (chwilowa_pozycja==popychacz){chwilowa_pozycja++;}
popychacz=int(znaleziono);
if (chwilowa_pozycja!=popychacz){cout << "Slowo " << szukane << " znalezione na pozycji " << int(znaleziono) << endl;}
}
system("PAUSE");
return EXIT_SUCCESS;
}

[Harrolfo 0]

Jesteś wielki!
Dzięki, tylko jeszcze jedno pytanie:
Gdzie wstawić
cout << "NIE":
żeby podawało komunikat NIE jak wyrazu 2 nie ma w pierwszym, np dla k i l?

[ziptofaf 2]

Dnia 04.06.2010 o 00:04, Harrolfo napisał:

Jesteś wielki!
Dzięki, tylko jeszcze jedno pytanie:
Gdzie wstawić
cout << "NIE":
żeby podawało komunikat NIE jak wyrazu 2 nie ma w pierwszym, np dla k i l?

To się ogranicza do dodania dwóch linii kodu. Jednej - jeśli szukane słowo jest większe od ciągu w którym szukamy.
I drugiej - zgodnie z opisem funkcji find, zwraca ona wartość -1, gdy nie znajduje danego słowa. W związku z tym:

#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main()
{
size_t znaleziono;
string slowo;
cin >> slowo;
string szukane;
cin >> szukane;
int chwilowa_pozycja=0;
int popychacz=0;

if (szukane.size()>slowo.size()){cout << "Brak poszukiwanego wyrazu w ciagu" << endl;
system("PAUSE");
return EXIT_SUCCESS;}

znaleziono=slowo.find(szukane, chwilowa_pozycja);
chwilowa_pozycja=int(znaleziono);

if (chwilowa_pozycja==-1){cout << "Brak poszukiwanego wyrazu w ciagu" << endl;
system("PAUSE");
return EXIT_SUCCESS;}
chwilowa_pozycja=0;

for (int a=0; a<=(slowo.size()/szukane.size()); a++){
if (slowo.size()-chwilowa_pozycja<szukane.size()){break;}
znaleziono=slowo.find(szukane, chwilowa_pozycja);
chwilowa_pozycja=int(znaleziono);
if (chwilowa_pozycja==popychacz){chwilowa_pozycja++;}
popychacz=int(znaleziono);
if (chwilowa_pozycja!=popychacz){cout << "Slowo " << szukane << " znalezione na pozycji " << int(znaleziono) << "\n";}
}
system("PAUSE");
return EXIT_SUCCESS;
}

No dobra, mogłem to zrobić w dwóch liniach kodu, wklejając po prostu nowe warunki do pętli for. Działałoby. Ale takie rozwiązanie oznacza dwa zupełnie niepotrzebne porównania w każdej kolejnej pętli. Co, jak sprawdziłem na stringu o długości miliona znaków i wyrazie mającym 100 znaków, fatalnie odbija się na wydajności. Wsadzenie tego przed pętlą sprawia, że kod jest dłuższy, ale znacznie (tak o 40%) wydajniejszy. Podmieniłem też << endl na << "\n" wewnątrz pętli, też jest minimalnie szybsze w działaniu.

[ziptofaf 2]

/.../
Aj, 2 błędy w kodzie, dopiero zauważyłem.

#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main()
{
size_t znaleziono;
string slowo;
cin >> slowo;
string szukane;
cin >> szukane;
int chwilowa_pozycja=0;
int popychacz=-2;

if (szukane.size()>slowo.size()){cout << "Brak poszukiwanego wyrazu w ciagu" << endl;
system("PAUSE");
return EXIT_SUCCESS;}

znaleziono=slowo.find(szukane, chwilowa_pozycja);
chwilowa_pozycja=int(znaleziono);

if (chwilowa_pozycja==-1){cout << "Brak poszukiwanego wyrazu w ciagu" << endl;
system("PAUSE");
return EXIT_SUCCESS;}
chwilowa_pozycja=0;

for (int a=0; a<=slowo.size(); a++){
if (slowo.size()-chwilowa_pozycja<szukane.size()){break;}
znaleziono=slowo.find(szukane, chwilowa_pozycja);
chwilowa_pozycja=int(znaleziono);
if (chwilowa_pozycja<popychacz){break;}
if (chwilowa_pozycja==popychacz){chwilowa_pozycja++;}
popychacz=int(znaleziono);
if (chwilowa_pozycja!=popychacz){cout << "Slowo " << szukane << " znalezione na pozycji " << int(znaleziono) << "\n";}
}
system("PAUSE");
return EXIT_SUCCESS;
}


Pierwszy błąd - nie sprawdzał zawsze do końca całego ciągu
Drugi - potrafił powtarzać informacje (np. słowo znalezione na miejscu 2, słowo znalezione na miejscu 2 itp.)
Teraz już jest dobrze.

[Harrolfo 0]

Jeszcze małe pytanko: Jak zrobić, żeby ten program dla podanych dwóch napisów działał tak jak działa, a dopóki są podawane kolejne dwa wyrazy przechodził do następnej linii i tam działał?