@Xiran

Почему неправильно решает задачу?

Задача:

Вам дана исходная строка: software developer. Каждый буквенный символ строки изменяется по следующему алгоритму:
1. Вычисляется его порядковый номер в алфавите (буквы в алфавите нумеруются с 1).
2. Найденный порядковый номер умножается на 2.
3. Если полученное число больше 26, то из него вычитается 26.
4. Вместо исходной буквы записывается буква с вычисленным порядковым номером.

Для каждого буквенного символа строки алгоритм был выполнен
2024 раза. Необходимо определить, сколько уникальных буквенных символов получилось в итоговой строке.
В ответ необходимо указать количество уникальных буквенных символов.

Мой код

#include <iostream>
#include <string>
#include <set>

void algorithm(std::string&);

int main() {
    std::string str { "software developer" };

    for (std::size_t i = 0; i < 2024; i++)
        algorithm(str);

    std::cout << str << std::endl;

    std::cout << std::set<char>(str.begin(), str.end()).size() << std::endl;
}

inline std::size_t position(char c) {
    return c - 'a' + 1;
}

inline char letter(std::size_t position) {
    return position - 1 + 'a';
} 

void algorithm(std::string &str) {
    for (auto &i : str) {
        auto pos = position(i);

        pos *= 2;

        if (pos > 26)
            pos -= 26;

        i = letter(pos);
    }
}


Правильный ответ: 10.
Вроде бы все верно, но выводит 11, я уже проверки на спецсимволы ставил, но никак не хочет правильно работать.
Может быть ошибка в letter или position?

P. S. Ошибка была в моей невнимательности, алгоритм применяется только к буквам, обидно, завалил задачу.
Правильный код

#include <iostream>
#include <string>
#include <set>

void algorithm(char&);

inline bool processable(char c) {
    return std::isalpha(static_cast<unsigned char>(c));
}

int main() {
    std::string str { "software developer" };

    for (auto &i : str)
        if (processable(i))
            for (std::size_t counter = 0; counter < 2024; counter++)
                algorithm(i);

    std::set<char> unique;

    for (const auto &i : str)
        if (processable(i))
            unique.insert(i);

    std::cout << unique.size() << std::endl;
}

inline std::size_t position(char c) {
    return c - 'a' + 1;
}

inline char letter(std::size_t position) {
    return position - 1 + 'a';
} 

void algorithm(char &i) {
    auto pos = position(i);

    pos *= 2;

    if (pos > 26)
        pos -= 26;

    i = letter(pos);
}

  • Вопрос задан
  • 101 просмотр
Пригласить эксперта
Ответы на вопрос 1
wataru
@wataru Куратор тега C++
Разработчик на С++, экс-олимпиадник.
Небольшое замечание: можно код сильно ускорить, применяя математику. Можно взять все номера букв по модулю 26, тогда a=1, ... y=25, z=0. Тогда операция будет - умножение на 2 и взятие по модулю 26 (для 'a' все также выдаст 'b', для 'z' все так же выдаст 'z'). До этого можно додуматься, потому что вот это вот "вычитание 26" - ну очень похоже на операцию взятия по модулю 26.

Применение этой операции 2024 раза равносильно умножению на 2^2024 по модулю 26. Воспользовавшисть теоремой эйлера, это равносильно умножению на 2^(2024 % 12) = 2^8 = 128. Далее, умножение на 128 по модулю 26 равносильно умножению на 24.

Т.е. можно умножать один раз на 24 вместо 2024 умножений на 2 (и в конце взять по модулю 26).
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы