[C++] anagramy.

xdominika
Użytkownik
Użytkownik
Posty: 81
Rejestracja: 14 lis 2019, o 22:59
Płeć: Kobieta
wiek: 19
Podziękował: 23 razy

[C++] anagramy.

Post 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?
Ostatnio zmieniony 1 gru 2020, o 09:41 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10204
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2358 razy

Re: [C++] anagramy.

Post autor: Dasio11 »

Program jest sensowny, a błąd jest w ostatniej linijce:

Kod: Zaznacz cały

return t == s;
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.
xdominika
Użytkownik
Użytkownik
Posty: 81
Rejestracja: 14 lis 2019, o 22:59
Płeć: Kobieta
wiek: 19
Podziękował: 23 razy

Re: [C++] anagramy.

Post autor: xdominika »

Dasio11 pisze: 1 gru 2020, o 12:12 Program jest sensowny, a błąd jest w ostatniej linijce:

Kod: Zaznacz cały

return t == s;
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;}
} 
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10204
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2358 razy

Re: [C++] anagramy.

Post autor: Dasio11 »

To dlatego, że funkcja porównuje tylko pierwszy znak tych napisów.
xdominika
Użytkownik
Użytkownik
Posty: 81
Rejestracja: 14 lis 2019, o 22:59
Płeć: Kobieta
wiek: 19
Podziękował: 23 razy

Re: [C++] anagramy.

Post 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;
    }

}
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10204
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2358 razy

Re: [C++] anagramy.

Post 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 )
    ...
xdominika
Użytkownik
Użytkownik
Posty: 81
Rejestracja: 14 lis 2019, o 22:59
Płeć: Kobieta
wiek: 19
Podziękował: 23 razy

Re: [C++] anagramy.

Post 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
Ostatnio zmieniony 6 gru 2020, o 19:19 przez Dasio11, łącznie zmieniany 1 raz.
Powód: Nie cytuj poprzedniej wiadomości w całości.
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10204
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2358 razy

Re: [C++] anagramy.

Post 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.
ODPOWIEDZ