• 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
102 wizyt
pytanie zadane 10 października w C i C++ przez damian9901 Obywatel (1,120 p.)
edycja 10 października 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 przez mokrowski Szeryf (88,240 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 przez adrian17 VIP (145,640 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 przez damian9901 Obywatel (1,120 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 przez Eryk Andrzejewski VIP (148,080 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 przez Eryk Andrzejewski VIP (148,080 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 przez damian9901 Obywatel (1,120 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 przez adrian17 VIP (145,640 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 przez damian9901 Obywatel (1,120 p.)
std::string to jest akurat błahostka. Wystarczy dodać przestrzeń nazw std. Tylko biblioteka algorithm, a w niej reverse. :)
komentarz 11 października przez Eryk Andrzejewski VIP (148,080 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 przez mokrowski Szeryf (88,240 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ź 59 wizyt
0 głosów
0 odpowiedzi 49 wizyt
pytanie zadane 18 maja w C i C++ przez jankowa1ski Gaduła (3,350 p.)
0 głosów
1 odpowiedź 105 wizyt
pytanie zadane 30 listopada 2017 w C i C++ przez smolik Nowicjusz (120 p.)
Porady nie od parady
Forum posiada swój własny chat IRC, dzięki któremu będziesz mógł po prostu pogadać z innymi Pasjonatami lub zapytać o jakiś problem. Podstrona z chatem znajduje się w menu pod ikoną człowieka w dymku.IRC

56,370 zapytań

101,067 odpowiedzi

208,200 komentarzy

28,042 pasjonatów

Przeglądających: 354
Pasjonatów: 12 Gości: 342

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.

...