przesuniecie znakow w wyrazie C++

Question

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.

Answer 1

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;

 

Comments

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.

---

Możesz do tego używać tej samej funkcji, dla słowa niebędącego palindromem jako przesunięcie po prostu podasz 0.

Answer 2

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.

Comments

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

---

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

---

std::string to jest akurat błahostka. Wystarczy dodać przestrzeń nazw std. Tylko biblioteka algorithm, a w niej reverse. :)

---

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ć?

---

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.

Answer 3

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