Strona 1 z 1
[C++] anagramy.
: 30 lis 2020, o 22:46
autor: xdominika
Napisać funkcję
bool anagramy(char* s, char* t)
która zwraca true jeśli s i t to anagramy.
Kod: Zaznacz cały
#include <iostream>
#include <algorithm>
int dlugosc(char* s) {
int i;
for(i=0; s[i]; i++);
return i;
}
bool anagramy(char* s, char* t)
{
if (dlugosc(s)!=dlugosc(t)) return false;
else
{
for (int i = 0; i < dlugosc(s) - 1; i++)
{
for (int j = 0; j < dlugosc(t) - 1; j++)
{
if (s[i] > s[i+1])
swap(s[i], s[i+1]);
if (t[j] > t[j+1])
swap(t[j], t[j+1]);
}
}
return t == s;
}
}
int main ()
{
cout<<anagramy("bark", "krab");
}
Niestety nawet nie wiem czy ma to sens, ale wiem jedno: nie działa. Czy mogłabym prosić o pomoc?
Re: [C++] anagramy.
: 1 gru 2020, o 12:12
autor: Dasio11
Program jest sensowny, a błąd jest w ostatniej linijce:
Zmienne
s i
t są wskaźnikami na dwie tablice. Takie porównanie sprawdza, czy te wskaźniki są równe, a więc: czy dwie tablice podane jako argumenty fizycznie zaczynają się w tym samym miejscu w pamięci.
Ty zaś powinnaś sprawdzić, czy te tablice zawierają te same napisy, co oczywiście robi się porównując je litera po literze.
Re: [C++] anagramy.
: 1 gru 2020, o 17:30
autor: xdominika
Dasio11 pisze: 1 gru 2020, o 12:12
Program jest sensowny, a błąd jest w ostatniej linijce:
Zmienne
s i
t są wskaźnikami na dwie tablice. Takie porównanie sprawdza, czy te wskaźniki są równe, a więc: czy dwie tablice podane jako argumenty fizycznie zaczynają się w tym samym miejscu w pamięci.
Ty zaś powinnaś sprawdzić, czy te tablice zawierają te same napisy, co oczywiście robi się porównując je litera po literze.
Poprawiłam na coś takiego i też niestety nie działa
Kod: Zaznacz cały
bool anagramy(char* s, char* t)
{
if (dlugosc(s)!=dlugosc(t)) return false;
else
{
for (int i = 0; i < dlugosc(s) - 1; i++)
if (s[i] > s[i+1])
swap(s[i], s[i+1]);
for (int j = 0; j < dlugosc(t) - 1; j++)
if (t[j] > t[j+1])
swap(t[j], t[j+1]);
}
for(int i = 0; s[i]; i++){
if(s[i] != t[i]) return false;
else return true;}
}
Re: [C++] anagramy.
: 1 gru 2020, o 20:20
autor: Dasio11
To dlatego, że funkcja porównuje tylko pierwszy znak tych napisów.
Re: [C++] anagramy.
: 6 gru 2020, o 15:52
autor: xdominika
Dasio11 pisze: 1 gru 2020, o 20:20
To dlatego, że funkcja porównuje tylko pierwszy znak tych napisów.
A czy mogłabym prosić o jakąś wskazówkę, nie widzę błędu, według mnie porównuje wszystkie znaki.
Kod: Zaznacz cały
bool anagramy(char* s, char* t)
{
if (dlugosc(s)!=dlugosc(t)) return false;
else
{
int i, j;
for ( i = 0; i < dlugosc(s) - 1; i++)
if (s[i] > s[i+1])
swap(s[i], s[i+1]);
for ( j = 0; j < dlugosc(t) - 1; j++)
if (t[j] > t[j+1])
swap(t[j], t[j+1]);
}
for (int i=0; i<dlugosc(s); i++)
{
if (s[i]==t[i])
return true;
else return false;
}
}
Re: [C++] anagramy.
: 6 gru 2020, o 18:39
autor: Dasio11
xdominika pisze: 6 gru 2020, o 15:52
Kod: Zaznacz cały
for (int i=0; i<dlugosc(s); i++)
{
if (s[i]==t[i])
return true;
else return false;
}
Zastanów się, jak zadziała ten fragment. Po pierwszym porównaniu
s[0] == t[0] funkcja zwróci
true lub
false w zależności od tego, czy warunek będzie prawdziwy, więc program nie wykona kolejnych przebiegów pętli, czyli nie porówna drugiego i kolejnych znaków.
Poprawiony fragment wygląda tak:
Kod: Zaznacz cały
for( int i = 0; i < dlugosc(s); ++i )
{
if( s[i] != t[i] ) return false;
}
return true;
Nawiasem mówiąc - nie wiem, czy kompilator będzie na tyle mądry, żeby w ramach optymalizacji zastąpić wywołanie
dlugosc(s) zwracaną wartością. Możliwe że tego nie zrobi, a wtedy w każdym przebiegu pętli program będzie od nowa niepotrzebnie liczył długość napisu. Dlatego lepiej zrobić tak:
Kod: Zaznacz cały
int D = dlugosc(s);
for( int i = 0; i < D; ++i )
...
Re: [C++] anagramy.
: 6 gru 2020, o 19:07
autor: xdominika
Chyba nigdy tego nie zrobię
Kod: Zaznacz cały
bool anagramy(char* s, char* t)
{
if (dlugosc(s)!=dlugosc(t)) return false;
else
{
int i, j;
for ( i = 0; i < dlugosc(s) - 1; i++)
if (s[i] > s[i+1])
swap(s[i], s[i+1]);
for ( j = 0; j < dlugosc(t) - 1; j++)
if (t[j] > t[j+1])
swap(t[j], t[j+1]);
}
int D = dlugosc(s);
for( int i = 0; i < D; ++i )
{
if( s[i] != t[i] ) return false;
}
return true;
}
Nie wiem czy funkcja swap nie działa tylko przy stringach, więc spróbowałam już zmienić typ napisu, jednak nadal nie działa.
Kod: Zaznacz cały
bool anagramy2(string s, string t)
{
if (s.length()!=t.length()) return false;
else
{
int i, j;
for ( i = 0; i < s.length() - 1; i++)
if (s[i] > s[i+1])
swap(s[i], s[i+1]);
for ( j = 0; j < t.length() - 1; j++)
if (t[j] > t[j+1])
swap(t[j], t[j+1]);
}
int D = s.length();
for( int i = 0; i < D; ++i )
{
if( s[i] != t[i] ) return false;
}
return true;
}
Oczywiście dodałam odpowiednie biblioteki
Re: [C++] anagramy.
: 6 gru 2020, o 19:46
autor: Dasio11
std::swap działa chyba na dowolnych zmiennych typu L-value, czyli takich, dla których poprawny jest napis
x = x; - w szczególności instrukcja
std::swap( s[i], s[i+1] ); jest poprawna i ma spodziewany efekt. Natomiast kod nie działa, bo funkcja przy sortowaniu bąbelkowym wykonuje jeden przebieg, a powinna wykonać ich tyle co długość napisu minus jeden.
Proponuję tak:
Kod: Zaznacz cały
bool anagramy( std::string s, std::string t )
{
int D = s.length();
if( t.length() != D ) return false;
for( int i = 0; i < D-1; ++i )
for( int j = 0; j < D-1; ++j )
{
if( s[j] < s[j+1] ) std::swap( s[j], s[j+1] );
if( t[j] < t[j+1] ) std::swap( t[j], t[j+1] );
}
return s == t;
}
Tym razem wolno napisać
s == t, bo typ
std::string ma zdefiniowany operator porównywania, który zwraca prawdę dokładnie wtedy gdy napisy są takie same.