• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

przesuniecie znakow w wyrazie C++

0 głosów
123 wizyt
pytanie zadane 10 października 2018 w C i C++ przez damian9901 Obywatel (1,610 p.)
edycja 10 października 2018 przez damian9901

Witam,

moim zadaniem jest utworzenie funkcji sprawdzającej, czy po przesunięciu liter w wyrazie o 'k' liter w prawo, powstanie palindrom. ( zadanie maturalne ).

#include <iostream>

using namespace std;

bool checkPalindrom(string w,int n, int k){
    int i,j;
    string pom;
    bool t = true;
    for(i=0,j=n;i<j;i++,j--){
        if(w[i] != w[j]){
            //
        }else {
            t=true;
            break;
        }
    }
    return (t == true) ? true : false;
}

int main()
{
    string w = "akkaj";
    int n = w.size()-1;

    //ile przesuniec
    int k= 3;

    cout<<checkPalindrom(w,n,k);


    return 0;
}
if(w[i] != w[j])

obecnie stanąłem na tym if'ie, bo zapewne w nim będzie trzeba dalej pracować... Jakaś podpowiedź?

Oczywiście po przesunięciu wyrazu akkaj o 3 litery w prawo, wyjdzie kajak.

3 odpowiedzi

+1 głos
odpowiedź 11 października 2018 przez mokrowski Szeryf (95,020 p.)

Aby sprawdzić czy napis jest palindromem, wystarczy porównywać znaki z początku i końca napisu aż do momentu gdy indeksy się zrównają.

Teraz wystarczy zauważyć że operacje indeksowania powinny być wykonywane z:

1. Przesunięciem o k

2. Modulo długość napisu.

Przy takich operacjach przydaje się trick z dodaniem samej wartości modulo by uniknąć wartości ujemnych. Czyli pseudo-kod wyliczenia indeksu będzie wyglądał tak:

indeks_dostepu = (indeks + msg.size() + k) % msg.size()
#include <iostream>
#include <string>
#include <iomanip>
#include <cstddef>

bool is_palindrome(const std::string& msg, std::size_t k = 0) {
    auto last_idx = msg.size() - 1;
    std::size_t first_idx = 0;
    while (first_idx != last_idx) {
        auto f_idx = (first_idx + msg.size() + k) % msg.size();
        auto l_idx = (last_idx + msg.size() + k) % msg.size();
        if (msg[f_idx] != msg[l_idx]) {
            return false;
        }
        ++first_idx;
        --last_idx;
    }
    return true;
}

int main() {
    std::string msg = "akkaj";
    std::cout << msg << " is palindrome? " << std::boolalpha << is_palindrome(msg, 2) << '\n';
}

Na koniec wystarczy spostrzec że sprawdzenie "zwykłego palindromu" to sprawdzenie napisu z przesunięciem 0.

Takie podejście oczywiście ma wadę/konsekwencje. Nie będzie działało dla napisów które będą dłuższe od std::size_t / 2. Nie sądzę jednak by to było tu istotne ograniczenie.

Alternatywnym rozwiązaniem jest bazujące na iteratorach, algorytmie std::rotate i std::equal.

#include <iostream>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cstddef>

bool is_palindrome(const std::string& msg, std::size_t k = 0) {
    std::string msg_data = msg;
    std::rotate(msg_data.begin(), msg_data.begin() + k, msg_data.end());
    return std::equal(msg_data.begin(), msg_data.begin() + msg_data.size() / 2, msg_data.rbegin());
}

int main() {
    std::string msg = "akkaj";
    std::cout << msg << " is palindrome? " << std::boolalpha << is_palindrome(msg, 2) << '\n';
}

 

 

0 głosów
odpowiedź 10 października 2018 przez adrian17 Mędrzec (157,440 p.)

obecnie stanąłem na tym if'ie, bo zapewne w nim będzie trzeba dalej pracować... Jakaś podpowiedź?

Jeśli znaki są różne, to tekst nie jest palindromem, więc możesz zwrócić false.

Jeśli są takie same, sprawdzaj pozostałe znaki aż do końca.

Nie potrzebujesz tu żadnych stringów pomocniczych - "przesunięcie o x znaków" możesz zrealizować przez przesuwanie indeksów i, j.

BTW, ten potworek

return (t == true) ? true : false;

można zapisać prościej:

return t == true;

Albo po prostu:

return t;

 

komentarz 10 października 2018 przez damian9901 Obywatel (1,610 p.)

I tutaj dla mnie zaczynają się schody, bo moim zadaniem jest sprawdzić, jeśli w początkowej fazie słowo nie jest palindromem, czyt. 

string w = "akkaj";

to czy w drugim etapie, po przesunięciu o 3 litery, będzie palindronem.

komentarz 10 października 2018 przez Eryk Andrzejewski Mędrzec (151,340 p.)
Możesz do tego używać tej samej funkcji, dla słowa niebędącego palindromem jako przesunięcie po prostu podasz 0.
0 głosów
odpowiedź 10 października 2018 przez Eryk Andrzejewski Mędrzec (151,340 p.)

Nie chcę Ci dawać gotowych rozwiązań, ale widzę, że sam wkładasz jakiś wysiłek w pracę, więc proszę bardzo, może się przyda.

#include <iostream>
#include <algorithm>
#include <string>

int main() {
    std::string str = "akkaj";
    unsigned offset = 3;

    str += str.substr(0, str.size() - offset);
    str.erase(0, (str.size() - offset) / 2);
    
    std::string strCopy = str;
    std::reverse(strCopy.begin(), strCopy.end());

    if (strCopy == str) {
        std::cout << "Palindrom!\n";
    } else {
        std::cout << "Nie palindrom!\n";
    }
}

Nie gwarantuję bezbłędności, pisane na szybko po ciężkim dniu. wink

komentarz 10 października 2018 przez damian9901 Obywatel (1,610 p.)
dzięki za pomoc, ale nie jestem pewny do końca, czy to przejdzie.Ztego co wiem, to na maturze nie można dołączać bibliotek innych niż <iostream>.
komentarz 10 października 2018 przez adrian17 Mędrzec (157,440 p.)

Ztego co wiem, to na maturze nie można dołączać bibliotek innych niż <iostream>.

Jeśli tak, to już jest słabo, bo std::string jest w <string>. Twój kod może nie zadziałać na wszystkich kompilatorach bez #include <string> :P

komentarz 10 października 2018 przez damian9901 Obywatel (1,610 p.)
std::string to jest akurat błahostka. Wystarczy dodać przestrzeń nazw std. Tylko biblioteka algorithm, a w niej reverse. :)
komentarz 11 października 2018 przez Eryk Andrzejewski Mędrzec (151,340 p.)

Ztego co wiem, to na maturze nie można dołączać bibliotek innych niż <iostream>.

A skąd masz takie informacje, jeśli mogę spytać?

komentarz 11 października 2018 przez mokrowski Szeryf (95,020 p.)
Można używać nagłówków biblioteki standardowej z wyjątkiem jasno wskazanych wykluczeń w danym zadaniu. Np. jeśli w zadaniu należy zaimplementować sortowanie, zrozumiałe jest że nie możesz zastosować std::sort.

Podobne pytania

0 głosów
1 odpowiedź 69 wizyt
pytanie zadane 22 stycznia 2018 w Algorytmy przez supergosc44 Początkujący (250 p.)
0 głosów
0 odpowiedzi 52 wizyt
pytanie zadane 18 maja 2018 w C i C++ przez jankowa1ski Gaduła (3,480 p.)
0 głosów
1 odpowiedź 112 wizyt
pytanie zadane 30 listopada 2017 w C i C++ przez smolik Nowicjusz (120 p.)
Porady nie od parady
Wynikowy wygląd pytania, odpowiedzi czy komentarza, różni się od tego zaprezentowanego w edytorze postów. Stosuj więc funkcję Podgląd posta znajdującą się pod edytorem, aby upewnić się, czy na pewno ostateczny rezultat ci odpowiada.Podgląd posta

59,199 zapytań

104,616 odpowiedzi

216,478 komentarzy

31,589 pasjonatów

Przeglądających: 174
Pasjonatów: 1 Gości: 173

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...