• 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
166 wizyt
pytanie zadane 10 października 2018 w C i C++ przez damian9901 Bywalec (2,140 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 VIP (101,860 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 (173,880 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 Bywalec (2,140 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 (154,200 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 (154,200 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 Bywalec (2,140 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 (173,880 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 Bywalec (2,140 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 (154,200 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 VIP (101,860 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ź 77 wizyt
pytanie zadane 22 stycznia 2018 w Algorytmy przez supergosc44 Początkujący (250 p.)
0 głosów
0 odpowiedzi 54 wizyt
pytanie zadane 18 maja 2018 w C i C++ przez jankowa1ski Gaduła (3,560 p.)
0 głosów
1 odpowiedź 117 wizyt
pytanie zadane 30 listopada 2017 w C i C++ przez smolik Nowicjusz (120 p.)
Porady nie od parady
Nie wiesz jak poprawnie zredagować pytanie lub pragniesz poznać którąś z funkcji forum? Odwiedź podstronę Pomoc (FAQ) dostępną w menu pod ikoną apteczki.FAQ

62,317 zapytań

108,447 odpowiedzi

226,391 komentarzy

35,101 pasjonatów

Przeglądających: 245
Pasjonatów: 13 Gości: 232

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.

...